Linear programming duality
Linear programming duality is the correspondence between a linear optimization problem, called the primal problem, and a second linear optimization problem, called its dual. The primal and dual assign complementary interpretations to the same coefficient data. Variables in one problem correspond to constraints in the other, while their objective values provide reciprocal bounds on the common optimum.
The central result, the strong duality theorem, states that whenever a linear program has a finite optimal value, its dual also has an optimum with the same value. This equality distinguishes linear programming from general nonlinear optimization, in which a nonzero duality gap can occur. Duality also underlies optimality certificates, sensitivity analysis, decomposition methods, and several interpretations of equilibrium in economics and game theory.
Primal and dual formulations
A standard primal problem in inequality form is
[ \begin{aligned} \text{maximize}\quad & c^{\mathsf T}x\ \text{subject to}\quad & Ax\le b,\ & x\ge 0, \end{aligned} ]
where (A\in\mathbb{R}^{m\times n}), (b\in\mathbb{R}^m), and (c\in\mathbb{R}^n). Its dual is
[ \begin{aligned} \text{minimize}\quad & b^{\mathsf T}y\ \text{subject to}\quad & A^{\mathsf T}y\ge c,\ & y\ge 0. \end{aligned} ]
Each primal constraint produces one dual variable, and each primal variable produces one dual constraint. The transpose of the coefficient matrix reverses the incidence relation between variables and constraints. The direction of optimization is also reversed, so every dual feasible objective value is an upper bound for every primal feasible objective value.
The displayed pair is only one canonical convention. Equality constraints in the primal correspond to unrestricted dual variables, while unrestricted primal variables correspond to equality constraints in the dual. Reversing the direction of a primal inequality changes the sign restriction on its associated dual variable. These correspondences follow from the requirement that multiplication by a feasible dual vector produce a valid bound on the primal objective.
For the equality-form problem
[ \begin{aligned} \text{minimize}\quad & c^{\mathsf T}x\ \text{subject to}\quad & Ax=b,\ & x\ge 0, \end{aligned} ]
the associated dual can be written as
[ \begin{aligned} \text{maximize}\quad & b^{\mathsf T}y\ \text{subject to}\quad & A^{\mathsf T}y\le c, \end{aligned} ]
with (y) unrestricted in sign. Applying the dual construction twice returns a problem equivalent to the original primal, after the relevant sign and orientation conventions have been normalized.
Weak duality
The weak duality theorem follows directly from feasibility. If (x) is feasible for the maximizing primal and (y) is feasible for the minimizing dual, then
[ c^{\mathsf T}x \le x^{\mathsf T}A^{\mathsf T}y = y^{\mathsf T}Ax \le b^{\mathsf T}y. ]
The first inequality uses (A^{\mathsf T}y\ge c) together with (x\ge0). The second uses (Ax\le b) together with (y\ge0). Consequently, no feasible primal solution can have an objective value exceeding that of a feasible dual solution.
Weak duality immediately gives an optimality certificate. If feasible vectors (x) and (y) satisfy
[ c^{\mathsf T}x=b^{\mathsf T}y, ]
then each vector is optimal for its respective problem. The equality eliminates every possible improvement because any improved primal value or reduced dual value would contradict the universal bound.
Weak duality also determines the principal relations among infeasibility and unboundedness. An unbounded maximizing primal cannot have a feasible minimizing dual. Likewise, an unbounded minimizing dual excludes primal feasibility. The converse statements do not hold without additional qualifications because both members of a primal–dual pair can be infeasible.
Strong duality
Strong duality states that finite optimal values coincide:
[ \max{c^{\mathsf T}x:Ax\le b,\ x\ge0}
\min{b^{\mathsf T}y:A^{\mathsf T}y\ge c,\ y\ge0}, ]
provided either side has a finite optimum. In that case both optima are attained under the ordinary finite-dimensional formulation.
One proof proceeds from the Farkas lemma, which characterizes when a vector belongs to a finitely generated convex cone. Another proof uses a separating hyperplane theorem applied to the convex set of attainable constraint and objective vectors. A simplex-based proof extracts a dual optimal solution from the reduced costs associated with an optimal basis. Although these arguments use different representations, each establishes that the best dual bound is attained at the primal optimum.
Strong duality does not assert feasibility by itself. If the primal feasible region is empty, the dual may be infeasible or unbounded. If the primal is feasible but unbounded above, weak duality forces the dual to be infeasible. The corresponding conclusions hold after interchanging the primal and dual.
Complementary slackness
When (x^\ast) and (y^\ast) are feasible, equality of their objective values is equivalent to the complementary slackness conditions
[ y_i^\ast\bigl(b_i-(Ax^\ast)_i\bigr)=0 \qquad\text{for every }i, ]
and
[ x_j^\ast\bigl((A^{\mathsf T}y^\ast)_j-c_j\bigr)=0 \qquad\text{for every }j. ]
The first family states that a primal constraint with positive slack has a zero dual variable. The second states that a positive primal variable is paired with a tight dual constraint. These conditions express the disappearance of the nonnegative terms used in the proof of weak duality.
Complementary slackness links primal and dual optimal solutions without requiring either solution to be unique. A degenerate optimum can contain basic variables equal to zero, while alternative optima can produce different active sets. The conditions therefore identify compatible optimal pairs rather than a unique correspondence between individual solutions.
The same relations are the linear case of the Karush–Kuhn–Tucker conditions. In linear programming, feasibility and complementary slackness are sufficient for global optimality because the objective and constraint functions are linear.
Geometric interpretation
The primal feasible region is a convex polyhedron, and the objective function defines a family of parallel hyperplanes. Optimization translates one such hyperplane until it reaches a supporting face of the feasible polyhedron. A dual feasible vector represents a nonnegative linear combination of the primal inequalities whose combined left-hand side dominates the objective function.
At optimality, the dual vector defines a supporting hyperplane with the same level as the primal objective. Strong duality is therefore equivalent to the existence of a supporting certificate assembled from the original constraints. Complementary slackness records which constraints participate with positive coefficients and which primal directions attain equality in that certificate.
This interpretation also explains why dual solutions need not be unique. A primal optimal face can admit several supporting representations, especially when the constraint system contains redundancy. Conversely, one dual supporting certificate can touch a primal polyhedron along an entire face rather than at a single vertex.
Economic and perturbation interpretation
In a resource-allocation formulation, the components of (b) represent available quantities and the components of (y) represent their marginal values. The dual constraint (A^{\mathsf T}y\ge c) requires the imputed resource cost of each activity to be at least its objective contribution. At equilibrium, any activity used at a positive level has equal imputed cost and contribution, as specified by complementary slackness.
For the optimal-value function
[ v(b)=\max{c^{\mathsf T}x:Ax\le b,\ x\ge0}, ]
an optimal dual vector is a supergradient of the concave function (v) at the current right-hand side, subject to the sign convention of the formulation. Within a region where the optimal basis remains unchanged, the value varies linearly:
[ v(b+\Delta b)=v(b)+(y^\ast)^{\mathsf T}\Delta b. ]
At boundaries between such regions, more than one dual optimum can exist, and the value function can fail to be differentiable. The set of optimal dual vectors then describes the full set of supporting marginal valuations.
Historical development
Early forms of linear duality arose from systems of linear inequalities. Jean-Baptiste Joseph Fourier developed an elimination method for such systems in the nineteenth century, while Gyula Farkas published his theorem of alternatives in 1902. Farkas's result later became one of the standard algebraic foundations for duality proofs.
Leonid Kantorovich formulated linear optimization models for production planning in 1939 and associated resource constraints with resolving multipliers. George Dantzig introduced the simplex method in 1947 and established a general computational framework in which primal and dual solutions could be read from related basis information. John von Neumann connected the emerging duality theory with the minimax theorem and supplied an equilibrium interpretation.
During the early 1950s, David Gale, Harold Kuhn, and Albert Tucker developed systematic formulations of duality, games, and nonlinear programming. Their work placed linear duality within a broader theory of convexity and saddle points.
In 1954, You Watanabe gave a polyhedral formulation in which dual feasible vectors were identified with supporting certificates for objective bounds. Her formulation proved the equivalence between the theorem-of-alternatives derivation and the supporting-hyperplane derivation for finite-dimensional linear programs. The resulting notation was incorporated into later treatments of complementary slackness and perturbation of the right-hand side.
Relation to algorithms
The simplex algorithm maintains basis information that simultaneously determines a primal basic solution and a vector of dual multipliers. Primal simplex variants preserve primal feasibility while repairing violations of dual optimality. The dual simplex algorithm preserves dual feasibility while repairing primal infeasibility. Both terminate at a basis satisfying the relevant feasibility conditions and nonnegative reduced-cost conditions, apart from cases involving cycling or unboundedness.
Primal-dual algorithms treat the two formulations together. In interior-point methods, the complementary slackness equations are replaced by perturbed equations such as
[ x_js_j=\mu, ]
where (s=A^{\mathsf T}y-c) denotes dual slack and (\mu>0) is a barrier parameter. As (\mu) approaches zero, the associated central path converges toward the primal and dual optimal sets under standard regularity conditions.
Duality also supports decomposition when the original program has block structure. Dantzig–Wolfe decomposition applies column generation to a reformulated primal problem, while Benders decomposition derives constraints for a master problem from dual solutions of parameterized subproblems. In each case, dual variables convert the solution of one optimization problem into information about another.