= Lagrangian duality
{c}
{title2=$\sup_{\lambda\geq0,\mu}\inf_u L(u,\lambda,\mu)$}
A <feasible point> gives an upper bound on a <minimization problem>'s best value; a suitable <Lagrange multiplier> gives a lower bound. <Lagrangian duality> searches for the strongest bound obtainable this way. Matching bounds certify a <global minimum>.
Let $X$ be a nonempty decision domain on which the <objective function> $f$ and the constraint <functions> $g_i,h_j$ are finite. Write the <primal problem> and its <optimization Lagrangian> as
$$
p_* = \inf\{f(x):x\in X,\ g_i(x)\leq0,\ h_j(x)=0\},
\qquad
L(x,\lambda,\nu)=f(x)+\sum_{i=1}^m\lambda_i g_i(x)+\sum_{j=1}^r\nu_j h_j(x).
$$
The inequality <Lagrange multipliers> obey $\lambda_i\geq0$; the equality <Lagrange multipliers> $\nu_j$ are unrestricted <real numbers>. Define the <Lagrange dual function> and dual optimal value by
$$
q(\lambda,\nu)=\inf_{x\in X}L(x,\lambda,\nu),\qquad
d_* = \sup_{\lambda\geq0,\ \nu\in\mathbb R^r}q(\lambda,\nu).
$$
The inner <infimum> keeps $X$, but releases the displayed <optimization constraints>. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§§5.1.1–5.1.3, printed pp. 215–216: domain, Lagrangian, dual function and lower bounds]{ref}
Here is the entire <weak duality> argument. For any <feasible point> $z$ and allowable <Lagrange multipliers>,
$$
q(\lambda,\nu)\leq L(z,\lambda,\nu)\leq f(z).
$$
The first <inequality> is the definition of an <infimum>; the second uses $\lambda_i g_i(z)\leq0$ and $h_j(z)=0$. Taking the <infimum> over feasible $z$, then the <supremum> over allowable <Lagrange multipliers>, gives $d_*\leq p_*$. No <convexity> is used.
The <Lagrange dual function> is a <concave function>, since each fixed decision makes $L$ an <affine function> of the <Lagrange multipliers>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.1.2, printed p. 216: pointwise infimum of affine functions]{ref} Explicitly, write $y=(\lambda,\nu)$ and choose two points where $q$ is finite. For $0\leq t\leq1$ and every $x\in X$,
$$
L(x,ty_1+(1-t)y_2)
=tL(x,y_1)+(1-t)L(x,y_2)
\geq tq(y_1)+(1-t)q(y_2).
$$
Taking the <infimum> over $x$ proves the defining <concavity> <inequality>. Thus even a difficult <primal problem> supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.
For finite optimal values, <strong duality> means $d_*=p_*$, or zero <duality gap>. It need not imply <dual attainment>. For <convex optimization>, <Slater's condition> is a sufficient <constraint qualification> for both when $p_*$ is finite.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§§5.2.2–5.2.3, printed pp. 225–227: gap, strong duality and Slater dual attainment]{ref} The <Strong Lagrangian property> requires an actual finite <Lagrange multiplier> achieving equality. <Convex perturbation duality> interprets such a bound as a supporting slope of the perturbed <value function>.
Back to article page
