Strong duality

Strong duality means that the primal and dual optimal values are equal. It holds for every feasible bounded linear program and for broad classes of convex optimization problems under a constraint qualification.

A jointly proper convex function $f(x,z)$ represents an optimization problem at perturbation $z=0$ and a family of nearby problems at other $z$. Its primal value function is $p(z)={\inf }_{x}f(x,z)$. Relaxing an inequality by $z$ gives the example $f(x,z)=J(x)+{\delta }_{(-\infty ,0]}(r(x)-\sigma -z)$, using an indicator functional. The resulting convex perturbation duality expresses multipliers as supporting subgradients of the value function.

For a convex perturbation function, defineThe primal and dual values are $p(0)$ and $q(0)$; the signed dual marginal $q$ is concave. The identity $p^{\ast }(y)=f^{\ast }(0,y)$ gives $q(0)=p^{\ast \ast }(0)$. If $p$ is proper and finite near zero, subgradients at zero prove strong duality with dual attainment. In finite dimensions the relative-interior condition $0\in \mathrm{ri}(\mathrm{dom}p)$ also suffices, provided $p(0)$ is finite. This does not itself prove primal attainment.

An optimal dual variable $y^{\ast }\in \partial p(0)$ bounds the effect of perturbing a convex value function:If $p$ is finite convex near zero, $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. A singleton subdifferential gives differentiability and a first-order expansion. For an upper-bound constraint relaxed by $z$, the derivative equals the negative of the nonnegative Lagrange multiplier; relaxing the bound can decrease the minimum value.

For a finite-dimensional convex optimization problem with affine equalities $Ax=b$ and convex inequalities $g_i(x)\le 0$, Slater's condition requires a point in the relative interior of the common effective domain that satisfies the equalities and makes every inequality strict. A refined version only requires strictness of the nonaffine inequalities; affine inequalities may hold with equality. If the primal optimal value is finite, these conditions imply strong duality and dual attainment.^[ref]

The relative-domain hypothesis matters. Minimize $-\sqrt{x}$ over its domain $x\ge 0$ subject to $x\le 0$. The only feasible point is zero, giving primal value zero. For multiplier $\lambda >0$, the dual function isIts supremum is zero but is not attained by a finite multiplier. The feasible point lies outside the relative interior $(0,\infty )$ of the objective domain, so the refined condition does not apply. Feasibility of affine constraints alone suffices only when the relevant domain hypothesis is also met.

Consider minimizing $f(x)$ over a specified domain with inequalities $g_i(x)\le 0$. Assume a primal minimizer exists and strong duality holds with an optimal nonnegative multiplier ${\lambda }^{\ast }$. Let $v(x)=\max (0,g_1(x),\dots ,g_m(x))$. For every $M>\Vert {\lambda }^{\ast }{\Vert }_1$, the exact maximum-violation penaltyhas the same minimum, and every penalized minimizer is feasible and primal optimal.

Indeed the optimal Lagrange dual function bound gives $f(x)+{\sum }_i{\lambda }_i^{\ast }{g}_i(x)\ge p^{\ast }$. Since ${\sum }_i{\lambda }_i^{\ast }{g}_i(x)\le \Vert {\lambda }^{\ast }{\Vert }_{1}v(x)$,A primal optimizer has $v=0$ and reaches $p^{\ast }$. Any infeasible point has strictly larger penalized value, proving the claim. The strict multiplier margin and zero-gap hypotheses explain why existence of an arbitrary optimal dual vector alone is insufficient.

Dual attainment means that a feasible choice of Lagrange multipliers achieves the optimal value of the Lagrangian dual problem. Equality of primal and dual optimal values alone does not imply dual attainment.