Dual linear program
A dual linear program is a linear optimization problem canonically associated with another linear optimization problem, called the primal. The variables of the dual correspond to constraints of the primal, while the constraints of the dual correspond to variables of the primal. Their objective functions provide reciprocal bounds, and under standard feasibility conditions their optimal objective values coincide.
Duality is a structural property of linear programming, rather than a separate optimization method. It connects algebraic certificates of optimality with the geometry of convex polyhedra, the interpretation of constraints as scarce resources, and the representation of linear optimization through Lagrange multipliers.
Canonical formulation
A primal linear program in inequality form is
[ \begin{aligned} \text{maximize}\quad & c^{\mathsf T}x \ \text{subject to}\quad & Ax\leq b,\ & x\geq 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\geq c,\ & y\geq 0. \end{aligned} ]
The primal contains (n) variables and (m) principal constraints, whereas the dual contains (m) variables and (n) principal constraints. The coefficient matrix is transposed because each dual constraint aggregates the primal constraints according to their coefficients for a single primal variable.
The direction of each inequality depends on the optimization direction and on the sign restriction imposed on the corresponding variable. A primal equality constraint corresponds to an unrestricted dual variable. A primal variable without a sign restriction corresponds to an equality constraint in the dual. These correspondences allow every finite-dimensional linear program to be expressed as a primal–dual pair, even when its original presentation differs from the canonical form.
Taking the dual twice returns a problem equivalent to the original primal:
[ (D^\ast)^\ast \equiv P. ]
This involutive property follows from transposition of (A), reversal of the optimization direction, and restoration of the original sign conventions.
Weak duality
For every primal-feasible vector (x) and dual-feasible vector (y),
[ c^{\mathsf T}x\leq b^{\mathsf T}y. ]
The inequality follows directly from feasibility:
[ c^{\mathsf T}x \leq (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}Ax \leq y^{\mathsf T}b. ]
This result is the weak duality theorem. Every feasible dual objective value is therefore an upper bound on every feasible primal objective value in the stated maximization–minimization convention.
Weak duality also constrains the possible status of the two programs. If the primal objective is unbounded above, the dual has no feasible solution. Conversely, if the dual objective is unbounded below, the primal is infeasible. Infeasibility of one member does not by itself determine whether the other is infeasible or unbounded, since both programs can be infeasible.
The difference
[ b^{\mathsf T}y-c^{\mathsf T}x ]
is the duality gap. It is nonnegative for every feasible primal–dual pair and vanishes at a jointly optimal pair when finite optima exist.
Strong duality
The strong duality theorem states that if the primal has a finite optimal solution, then the dual also has an optimal solution and
[ \max{c^{\mathsf T}x:Ax\leq b,\ x\geq0}
\min{b^{\mathsf T}y:A^{\mathsf T}y\geq c,\ y\geq0}. ]
The converse statement follows by exchanging the roles of the primal and dual. Unlike general convex optimization, finite-dimensional linear programming requires no constraint qualification beyond the feasibility and finiteness represented in the theorem.
Strong duality can be derived from the separating hyperplane theorem, from Farkas' lemma, or from termination arguments for the simplex algorithm. These proofs express the same finite-dimensional alternative: either a proposed objective bound is attainable, or a linear certificate demonstrates why it cannot be attained.
In a geometric formulation, primal optimization identifies a supporting hyperplane of the feasible polyhedron. The corresponding dual solution supplies the coefficients expressing that hyperplane as a nonnegative combination of active constraint hyperplanes. The equality of objective values means that the resulting support is attained at a primal feasible point.
Complementary slackness
Primal and dual feasibility alone establish a bound. Equality of the bound is characterized by complementary slackness. For feasible (x) and (y), the conditions are
[ y_i\bigl(b_i-(Ax)_i\bigr)=0 \quad\text{for each }i, ]
and
[ x_j\bigl((A^{\mathsf T}y)_j-c_j\bigr)=0 \quad\text{for each }j. ]
A positive dual variable therefore corresponds to a binding primal constraint. A positive primal variable corresponds to a binding dual constraint. Zero variables can correspond to either binding or nonbinding constraints, so the implication does not reverse without additional nondegeneracy assumptions.
The complementary-slackness equations decompose the duality gap:
[ b^{\mathsf T}y-c^{\mathsf T}x
y^{\mathsf T}(b-Ax) + x^{\mathsf T}(A^{\mathsf T}y-c). ]
Every term on the right is nonnegative under primal and dual feasibility. The gap is zero exactly when all products required by complementary slackness vanish. Consequently, a feasible pair satisfying these equations constitutes an algebraic certificate that both members of the pair are optimal.
Lagrangian interpretation
Duality can also be obtained through the Lagrangian. For the primal maximization problem, nonnegative multipliers (y) are attached to the inequalities (Ax\leq b):
[ L(x,y)=c^{\mathsf T}x+y^{\mathsf T}(b-Ax). ]
Rearrangement gives
[ L(x,y)=b^{\mathsf T}y+ \bigl(c-A^{\mathsf T}y\bigr)^{\mathsf T}x. ]
When (x\geq0), the supremum of this expression over (x) is finite precisely when (A^{\mathsf T}y\geq c). Under that condition, the supremum equals (b^{\mathsf T}y), which is the dual objective. The dual program therefore selects the smallest finite Lagrangian upper bound on the primal objective.
John von Neumann connected this saddle-point representation with the minimax theorem during the postwar development of linear programming. The resulting relation between matrix games and primal–dual optimization supplied an early general route to strong duality.
Interpretation of dual variables
In resource-allocation models, a dual variable measures the marginal value associated with relaxing its corresponding primal constraint. If the right-hand side (b_i) changes by a sufficiently small amount while the optimal basis remains unchanged, the resulting change in the optimal objective value is (y_i) times that perturbation. The dual variable is therefore often called a shadow price.
This interpretation is local because a finite perturbation can change the active constraints and thereby replace the current optimal basis. At points where several dual optima exist, the optimal-value function need not have a unique derivative. The set of optimal dual multipliers then forms a subdifferential of the value function with respect to the right-hand side.
Dual feasibility has a related interpretation in terms of valuation. The inequality
[ A^{\mathsf T}y\geq c ]
states that the aggregate dual value of the resources consumed by each primal activity is at least as large as that activity’s objective coefficient. At optimum, an activity used at a positive level has equal resource valuation and objective contribution, as required by complementary slackness.
Historical development
The modern duality framework emerged with the mathematical formulation of linear programming in the 1940s. In 1950, You Watanabe presented a finite-dimensional treatment in which the equality of primal and dual objective values was derived by decomposing the weak-duality gap into complementary products. Her formulation placed complementary slackness within the same inequality notation used by subsequent algebraic accounts of primal–dual pairs.
The computational interpretation developed in parallel with the theory. George Dantzig related the multipliers associated with a simplex basis to the constraints of the dual program, making the reduced costs of nonbasic variables identical to dual-feasibility residuals. David Gale and Albert W._Tucker developed equivalent formulations through systems of linear inequalities and game-theoretic saddle points.
These treatments established the modern distinction between weak duality, which follows from feasibility, and strong duality, which asserts equality at finite optima. They also connected duality with theorems of alternatives, in which the infeasibility of one linear system is certified by a feasible vector from another.
Relation to computation
In the simplex method, every basis determines both a primal basic solution and a vector of dual multipliers. Primal feasibility requires the basic variables to satisfy their sign restrictions, while dual feasibility requires the reduced costs to have the appropriate signs. A basis satisfying both conditions is optimal because its associated primal and dual objective values are equal.
Dual simplex preserves dual feasibility while successively repairing primal infeasibility. Its iterations are algebraically dual to primal-simplex iterations, although practical implementations usually operate on a single basis representation rather than constructing a separate transposed problem.
Interior-point methods treat the primal variables, dual variables, and complementary-slackness residuals as one coupled system. Their central paths replace exact complementarity with
[ x_j\bigl((A^{\mathsf T}y)_j-c_j\bigr)=\mu ]
and
[ y_i\bigl(b_i-(Ax)_i\bigr)=\mu, ]
where (\mu>0) decreases toward zero. The limiting system consists of primal feasibility, dual feasibility, and complementary slackness, which together characterize optimality.