Lagrangian duality (${\sup }_{\lambda \ge 0,\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 asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe 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.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. 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.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,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_{\ast }=p_{\ast }$, 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_{\ast }$ is finite.^[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.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

A nonconvex primal problem can have a positive duality gap even when both optima are attained. Choose the finite set $X=\{-2,0,2\}$, the objective function values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality optimization constraint $h(x)=x=0$. The only feasible point is $0$, so $p_{\ast }=3$.

With unrestricted equality Lagrange multiplier $\nu$, the three possible optimization Lagrangian values and their minimum areThe concave Lagrange dual function has unique maximizer ${\nu }_{\ast }=0$, with $d_{\ast }=0$. Thus the duality gap is $3$. At the optimal Lagrange multiplier, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.

Why can no slope close the gap? Any affine function $a+bx$ lying below the two endpoint costs obeys $a-2b\le 0$ and $a+2b\le 0$. Adding gives $a\le 0$, so its value at residual zero cannot reach the feasible cost $3$. A convex combination of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive duality gap: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.

Consider an objective function that is a quadratic polynomial, with a singular optimization constraint:Its only feasible point is $x_{\ast }=0$, giving $p_{\ast }=9$. For $\lambda \ge 0$, completing the square yieldsEvery finite Lagrange multiplier gives $q(\lambda )<9$, but $q(\lambda )\to 9$ as $\lambda \to \infty$. Thus $d_{\ast }=p_{\ast }=9$: strong duality holds, and the primal optimum is attained, yet dual attainment fails. The inner minimizers $3/(1+\lambda )$ approach $0$ without ever becoming feasible at finite $\lambda$.

Both the objective function and the constraint function are convex functions. However, Slater's condition fails because $x^2<0$ is impossible. At the optimum, stationarity would require $-6+\lambda \cdot 0=0$, which no finite Lagrange multiplier satisfies. Compare KKT regularity at a local minimum: a zero gradient of an active constraint can prevent a multiplier certificate. This example has zero duality gap without the Strong Lagrangian property.

For a finite constrained optimum value $\varphi (b)=\inf \{f(x):h(x)=b,x\in X\}$ and optimization Lagrangian $L_b(x,\lambda )=f(x)-{\lambda }^T(h(x)-b)$, the strong Lagrangian property means that some finite Lagrange multiplier attains the dual lower bound exactly: ${\inf }_X{L}_b=\varphi (b)$. It includes dual attainment, but need not include primal attainment. It is equivalent to a non-vertical supporting hyperplane of a value function: a supporting slope gives $f(x)\ge \varphi (h(x))\ge \varphi (b)+{\lambda }^T(h(x)-b)$, hence ${\inf }_X{L}_b\ge \varphi (b)$; weak duality gives the opposite inequality. Conversely the infimum identity bounds every $L_b(x,\lambda )$ below by $\varphi (b)$; taking the infimum over $h(x)=u$ gives the supporting inequality. No convexity assumption is needed for this equivalence.

The original mathematical optimization problem relative to a chosen Lagrangian dual problem. In convex perturbation duality, its objective is $\phi (x)=f(x,0)$ and its value is $p(0)$. Strong duality concerns optimal values; primal attainment additionally requires an actual minimizing point.