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.

References:

- Boyd, S., and Vandenberghe, L. (2004).
*Convex Optimization*. Chapter 5.

### Like this:

Like Loading...

*Related*

Pingback: Lagrange dual, weak duality and strong duality | Statistical Odds & Ends