For the primal maximization , and dual minimization , , a feasible pair has the nonnegative objective-gap decompositionThus equal objective values are equivalent toThese 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.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.5.2, complementary slackness; inequalities and equality of optimal objectives
For the linear program maximizing subject to , , let be optimal and let be an optimal dual linear program solution. Complementary slackness makes on every positive coordinate of . Any nonnegative supported on those coordinates therefore hasThe same is dual feasible when the right-hand side is changed to . Equality of feasible objectives and weak duality prove optimality of for that modified problem.
There is also a direct primal proof. If had and , then would remain feasible and nonnegative for sufficiently small . On zero coordinates of , support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of .
For the primal linear program maximising with , , and its dual linear program minimising with , , let be optimal. The complementary slackness identity gives . Thus a strict inequality in the th dual constraint forces . One optimal dual feasible solution can therefore force zero components in every primal optimum. The same argument with roles reversed says that forces the th primal constraint to be an equality.
Articles by others on the same topic
There are currently no matching articles.