Weak duality

Every feasible dual objective value bounds every feasible primal objective value.

For the linear program maximizing $c^{T}x$ with $Ax\le b$, $x\ge 0$, a vector $y\ge 0$ with $A^{T}y\ge c$ proves $c^{T}x\le y^{T}b$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is weak duality written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.

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.

The Slater condition requires a feasible point at which every nonlinear convex inequality is strict and every affine equality holds. For a convex problem it implies strong duality and attainment of the dual optimum under standard finiteness assumptions.

An exact maximum-violation penalty replaces inequalities $g_i(x)\le 0$ by the unconstrained objective $f(x)+M\max (0,g_1(x),\dots ,g_m(x))$. If an optimal dual multiplier is ${\lambda }^{\ast }$, every $M>\Vert {\lambda }^{\ast }{\Vert }_1$ makes every penalized minimizer feasible and optimal.