Proving concavity of the Lagrange dual function

The Lagrange dual function for an optimization problem of form $$\min f_0(\boldsymbol x)\quad\text{subject to}\quad f_i(\boldsymbol x)\le0,h_j(\boldsymbol x)=0\quad i=1,2\dots m,j=1,2,\dots p$$ with domain $$D$$, is defined as $$g(\boldsymbol\lambda,\boldsymbol\nu)=\inf_{\boldsymbol x\in D}\left(f_0(\boldsymbol x)+\sum_{i=1}^m\lambda_if_i(\boldsymbol x)+\sum_{j=1}^p\nu_jh_j(\boldsymbol x)\right)$$

Consider 2 points $$(\boldsymbol \lambda_1,\boldsymbol \nu_1),(\boldsymbol \lambda_2,\boldsymbol \nu_2)$$. Let $$C_1=g(\boldsymbol \lambda_1,\boldsymbol \nu_1)$$ and $$C_2=g(\boldsymbol \lambda_2,\boldsymbol \nu_2)$$. A point between them is of the form $$(t\boldsymbol \lambda_1+(1-t)\boldsymbol\lambda_2,t\boldsymbol \nu_1+(1-t)\boldsymbol\nu_2)$$ with corresponding Langrage dual value $$g(t\boldsymbol \lambda_1+(1-t)\boldsymbol\lambda_2,t\boldsymbol \nu_1+(1-t)\boldsymbol\nu_2)$$.

Since $$g$$ is the pointwise infimum of a family of affine functions of $$(\boldsymbol \lambda,\boldsymbol \nu)$$, we have for any fixed $$\boldsymbol x$$ $$g(t\boldsymbol \lambda_1+(1-t)\boldsymbol\lambda_2,t\boldsymbol \nu_1+(1-t)\boldsymbol\nu_2)\ge tg(\boldsymbol\lambda_1,\boldsymbol\nu_1)+(1-t)g(\boldsymbol\lambda_2,\boldsymbol\nu_2)$$ which proves that $$g$$ is a concave curve.

Is this correct?

• Is it Deja Vu or someone really asked a similar question a few days ago? Apr 1 at 14:15
• @PNDas Just saw it too, but their confusion is regarding the differences in definition. Apr 1 at 18:00

You have the right intuition. Just remember that, for $$t \in (0,1)$$, $$g$$ is concave if: $$g(tx + (1-t)y) \geq tg(x) + (1-t)g(y),$$ and if $$g_1, g_2$$ are affine functions and $$g(x)=\min\{g_1(x),g_2(x)\}$$, then: $$\begin{array} &g(\alpha x)&=\min\{g_1(\alpha x),g_2(\alpha x)\}\\ &\geq \min\{\alpha g_1(x),\alpha g_2(x)\}\\ & \geq \alpha \min \{g_1(x),g_2(x)\} \\ & = \alpha g(x) \end{array}$$
Also, you need to define that $$t$$ is in the interval $$(0,1)$$ and for fixed $$t$$ (not $$x$$ as you mentioned) the inequality defining concavity holds.