Consider an optimization problem in standard form:
with the variable . Let be the domain for , i.e. the intersection of the domains of the ‘s and the ‘s.
The Lagrangian associated with this problem is the function defined as
with domain . The Lagrange dual function is the function defined as the minimum value of the Lagrangian over :
The dual function is a very important function in optimization theory. One interesting fact about the dual function is that it is always concave, even if the original optimization problem is not convex. The proof can be stated in one-line: for each , is an affine function, and the point-wise infimum of a family of affine functions is always concave.
Here’s a more explicit version of the proof. Let . Fix and . For each ,
where the first equality uses the definition of (or the fact that is affine in ). Since this holds for all , we can take an infimum over to obtain , i.e. is concave.
- Boyd, S., and Vandenberghe, L. (2004). Convex Optimization. Chapter 5.
Pingback: Lagrange dual, weak duality and strong duality | Statistical Odds & Ends