For the primal maximization , and dual minimization , , a feasible pair has the nonnegative objective-gap decomposition
Thus equal objective values are equivalent to
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.[ref]
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 has
The 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.

Ancestors (6)

  1. Linear programming duality
  2. Linear programming
  3. Mathematical optimization
  4. Area of mathematics
  5. Mathematics
  6. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.