[Math] Why is the lagrange dual function concave

lagrange multipliersupremum-and-infimum

In a book I'm reading (Convex Optimization by Boyd and Vandenberghe) it says
enter image description here

I'm struggling to understand the last sentence. Why can one conclude concavity from having a pointwise infimum of a family of affine functions?

Best Answer

Because the Lagrangian $L(x,\lambda,\mu)$ is affine in $\lambda$ and $\mu$, the Lagrange dual function $d(\lambda,\nu) = \inf_{x\in \mathcal{D}}L(x,\lambda,\nu)$ is always concave because it is the pointwise infimum of a set of affine functions, which is always concave. (You can also show that the supremum of a set of convex functions is convex.)

Related Question