0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .