Optimization

LP Duality

Every linear program has a dual whose optimum equals the primal optimum, providing bounds, certificates, and shadow prices.

Primal and dual

Given a primal LP, minimize c dot x subject to A x >= b, x >= 0, its dual is: maximize b dot y subject to A^T y <= c, y >= 0. The dual has one variable per primal constraint and one constraint per primal variable. The two problems are two views of the same underlying data.

Weak duality

For any primal-feasible x and dual-feasible y, b dot y <= c dot x. Every dual-feasible point gives a lower bound on the primal optimum, and every primal-feasible point gives an upper bound on the dual optimum. The gap between them measures distance from optimality.

Strong duality

For linear programs, if either problem has a finite optimum then both do and their optimal values are equal: the duality gap is zero. This is stronger than in general convex programs, where strong duality requires a constraint qualification. A matched primal-dual pair is a certificate of optimality.

Complementary slackness

At the optimum, for each constraint either the dual variable is zero or the primal constraint is tight.
Equivalently, for each variable either the variable is zero or its dual constraint is tight.
These conditions link primal and dual solutions and can be used to solve one from the other.

Shadow prices

The optimal dual variable for a constraint is its shadow price: the rate of change of the optimal objective per unit relaxation of that constraint's right-hand side. Shadow prices reveal which constraints are binding and how valuable additional resources would be, which drives sensitivity analysis in planning.

python

# If primal: min c^T x, Ax >= b, x >= 0
# Dual:     max b^T y, A^T y <= c, y >= 0
# Optimal values coincide (strong duality).

Duality supplies the lower bounds and optimality certificates that make branch-and-bound and sensitivity analysis tractable in large planning models.