Complementary slackness (source code)

= Complementary slackness
{wiki}

For the primal maximization $Ax\le b$, $x\ge0$ and dual minimization $A^Ty\ge c$, $y\ge0$, a feasible pair has the nonnegative objective-gap decomposition
$$
b^Ty-c^Tx=y^T(b-Ax)+x^T(A^Ty-c).
$$
Thus equal objective values are equivalent to
$$
y_i[b_i-(Ax)_i]=0\quad\hbox{for every }i,\qquad
x_j[(A^Ty)_j-c_j]=0\quad\hbox{for every }j.
$$
These are <complementary slackness>. Combined with primal and dual feasibility they certify optimality by <weak duality>. Conversely, primal and dual optima satisfy them by <strong duality>.

A positive dual multiplier forces its primal constraint to be tight, and a positive primal variable forces its dual constraint to be tight. A tight constraint need not have a positive multiplier: both factors in a complementary product may be zero. This distinguishes ordinary complementary slackness from a stronger strict-complementarity assertion. In the example under <linear programming>, the third primal inequality is slack and its multiplier is zero.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.5.2, complementary slackness; inequalities and equality of optimal objectives]{ref}