Linear programming duality

Every linear maximization program has a dual minimization program whose feasible objective values bound the primal values.

For minimization with constraints $Ax=b$, $x\ge 0$, a dual-feasible vector $y$ obeys $A^{T}y\le c$, so $b^{T}y$ is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix $B$, the associated vector is $y^T=c_B^T{B}^{-1}$. Its basic reduced costs are zero and its nonbasic reduced costs are $c_N^T-c_B^T{B}^{-1}{A}_N$. Thus nonnegative reduced costs are exactly dual feasibility in this minimization convention; basic primal values may still be negative, as in the dual simplex algorithm.

Minimizing ${\max }_i(a_i^{T}x+b_i)$ over unrestricted $x$ is a linear program after introducing an epigraph variable $t$ and inequalities $a_i^{T}x+b_i\le t$. Its optimization Lagrangian has finite infimum over $x,t$ exactly when the nonnegative multipliers sum to one and their weighted slopes sum to zero. The displayed Lagrangian dual problem maximizes the resulting constant lower bound. It identifies the role of a zero-slope convex combination of the affine functions.

For a minimization problem with inequalities $g_i(x)\le 0$, the Lagrangian is $L(x,\lambda )=f(x)+{\sum }_i{\lambda }_i{g}_i(x)$ with ${\lambda }_i\ge 0$. The Lagrangian dual maximizes the concave dual function $q(\lambda )={\inf }_{x}L(x,\lambda )$.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A Lagrangian relaxation moves selected constraints into the objective with appropriately signed Lagrange multipliers. Maximizing the relaxed objective over a larger easy set gives an upper bound for a constrained maximization problem. Optimizing that bound need not solve the original integer problem.

Retaining integer assignment equations while dualizing extra capacity inequalities gives an easily evaluated upper bound for a maximization problem. With multipliers $\lambda \ge 0$ and capacities $b$, it is $\theta (\lambda )={\max }_{x\text{ assignment}}[c^{T}x+{\lambda }^T(b-Ax)]$. It is a convex maximum of affine functions. Minimizing it exploits the convex hull of assignments, so it can have a finite optimum when only a fractional mixture satisfies the side constraints and no integer assignment does. This separates a useful relaxation bound from a certificate of integer feasibility.

For binary knapsack optimization, $U(\lambda )$ is an upper bound for every $\lambda \ge 0$. Its minimum is computable from the finitely many profit-to-weight breakpoints and agrees with the fractional knapsack problem optimum. Zero-weight positive-profit terms are added independently.

For a primal maximization problem $Ax\le b$, $x\ge 0$, the dual minimizes $b^{T}y$ subject to $A^{T}y\ge c$, $y\ge 0$.

A dual variable is a multiplier associated with a primal constraint in a dual linear program. In a minimization linear program with equality constraints $Ax=b$ and nonnegative primal variables, the Lagrangian $c^{T}x+y^T(b-Ax)$ yields the dual objective $b^{T}y$ and inequalities $A^{T}y\le c$; the equality-constraint multipliers $y$ are unrestricted in sign. For a transportation problem, row and column dual variables give potentials $u_i,v_j$ satisfying $u_i+v_j\le c_{ij}$. Complementary slackness makes occupied routes attain equality.

The dual pairsatisfies weak duality because $b^{T}y\le y^{T}Ax=x^T{A}^{T}y\le c^{T}x$ for every feasible pair.

Every feasible dual objective value bounds every feasible primal objective value.

For the linear program maximizing $c^{T}x$ with $Ax\le b$, $x\ge 0$, a vector $y\ge 0$ with $A^{T}y\ge c$ proves $c^{T}x\le y^{T}b$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is weak duality written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.

Strong duality means that the primal and dual optimal values are equal. It holds for every feasible bounded linear program and for broad classes of convex optimization problems under a constraint qualification.

A jointly proper convex function $f(x,z)$ represents an optimization problem at perturbation $z=0$ and a family of nearby problems at other $z$. Its primal value function is $p(z)={\inf }_{x}f(x,z)$. Relaxing an inequality by $z$ gives the example $f(x,z)=J(x)+{\delta }_{(-\infty ,0]}(r(x)-\sigma -z)$, using an indicator functional. The resulting convex perturbation duality expresses multipliers as supporting subgradients of the value function.

For a convex perturbation function, defineThe primal and dual values are $p(0)$ and $q(0)$; the signed dual marginal $q$ is concave. The identity $p^{\ast }(y)=f^{\ast }(0,y)$ gives $q(0)=p^{\ast \ast }(0)$. If $p$ is proper and finite near zero, subgradients at zero prove strong duality with dual attainment. In finite dimensions the relative-interior condition $0\in \mathrm{ri}(\mathrm{dom}p)$ also suffices, provided $p(0)$ is finite. This does not itself prove primal attainment.

An optimal dual variable $y^{\ast }\in \partial p(0)$ bounds the effect of perturbing a convex value function:If $p$ is finite convex near zero, $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. A singleton subdifferential gives differentiability and a first-order expansion. For an upper-bound constraint relaxed by $z$, the derivative equals the negative of the nonnegative Lagrange multiplier; relaxing the bound can decrease the minimum value.

The Slater condition requires a feasible point at which every nonlinear convex inequality is strict and every affine equality holds. For a convex problem it implies strong duality and attainment of the dual optimum under standard finiteness assumptions.

An exact maximum-violation penalty replaces inequalities $g_i(x)\le 0$ by the unconstrained objective $f(x)+M\max (0,g_1(x),\dots ,g_m(x))$. If an optimal dual multiplier is ${\lambda }^{\ast }$, every $M>\Vert {\lambda }^{\ast }{\Vert }_1$ makes every penalized minimizer feasible and optimal.

Dual attainment means that a feasible choice of Lagrange multipliers achieves the optimal value of the Lagrangian dual problem. Equality of primal and dual optimal values alone does not imply dual attainment.

For finite primal and dual optimal values in a minimization problem, the duality gap is $p_{\ast }-d_{\ast }\ge 0$. Strong duality means this difference is zero.

At a primal-dual optimum, each positive variable corresponds to a tight dual constraint and conversely for positive dual variables.

For the linear program maximizing $c^{T}x$ subject to $Ax=b$, $x\ge 0$, let $x^{\ast }$ be optimal and let $y^{\ast }$ be an optimal dual linear program solution. Complementary slackness makes $A_j^T{y}^{\ast }=c_j$ on every positive coordinate of $x^{\ast }$. Any nonnegative $\hat{x}$ supported on those coordinates therefore hasThe same $y^{\ast }$ is dual feasible when the right-hand side is changed to $\hat{b}=A\hat{x}$. Equality of feasible objectives and weak duality prove optimality of $\hat{x}$ for that modified problem.

There is also a direct primal proof. If $z\ge 0$ had $Az=A\hat{x}$ and $c^{T}z>c^T\hat{x}$, then $x^{\ast }+\epsilon (z-\hat{x})$ would remain feasible and nonnegative for sufficiently small $\epsilon >0$. On zero coordinates of $x^{\ast }$, support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of $x^{\ast }$.

For the primal linear program maximising $c^{T}x$ with $Ax\le b$, $x\ge 0$, and its dual linear program minimising $b^{T}y$ with $A^{T}y\ge c$, $y\ge 0$, let $x,y$ be optimal. The complementary slackness identity gives $x_j((A^{T}y{)}_j-c_j)=0$. Thus a strict inequality in the $j$th dual constraint forces $x_j=0$. One optimal dual feasible solution can therefore force zero components in every primal optimum. The same argument with roles reversed says that $y_i>0$ forces the $i$th primal constraint to be an equality.

The transportation problem minimizes linear shipping cost while matching prescribed row supplies and column demands.

This is the finite discrete optimal transport problem with prescribed supply and demand marginals.

When factory $i$ incurs unit production cost $p_i$ only on goods actually shipped, add that cost to every real shipping destination in its row. Unused capacity incurs no production cost; a dummy unused-capacity column therefore keeps zero cost rather than receiving $p_i$. This changes the optimal factory utilization when capacity exceeds total demand. Transportation dual certificate with capacity inequalities proves optimality without assuming every factory must produce at full capacity.

Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: ${\sum }_{ij}{c}_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$, since row sums are supplies $s_i$ and column sums are demands $d_j$. The reduced costs are $c_{ij}-u_i-v_j$. A feasible matrix using only zero-reduced-cost cells attains the lower bound, proving optimality by weak duality. The transportation simplex algorithm sets these potentials by equality on a transportation spanning tree, and enters a negative-reduced-cost cell if one exists.

For shipments $x_{ij}\ge 0$ with factory row sums at most capacities $s_i$ and shop column sums exactly demands $d_j$, the displayed dual potentials give $\sum c_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$. The sign $u_i\le 0$ ensures $u_i{\sum }_j{x}_{ij}\ge u_i{s}_i$. Equality proves optimality. It occurs when every used cell is tight and every row with spare capacity has $u_i=0$, the relevant complementary slackness conditions. A dummy demand column with zero costs converts unused capacity into a balanced transportation problem.

The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.

For a partial assignment problem, add its fixed cost to the sum, over remaining tasks, of each task's cheapest available machine cost. This is a lower bound because it relaxes the requirement that different tasks use distinct machines. It is an admissible bound for branch and bound, even though the minimizing choices may assign the same machine repeatedly.

// Target: mathematical-optimization.bigb

The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.

These feasible potentials give the lower bound ${\sum }_i{\lambda }_i-{\sum }_j{\mu }_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.

The transportation polytope is the set of nonnegative matrices with fixed row and column sums.

The positive cells of a nondegenerate transportation basis form a spanning tree in the bipartite graph of supply and demand vertices.

The transportation simplex computes row and column potentials, enters a negative-reduced-cost cell, and pivots around its induced alternating cycle.

The northwest-corner method repeatedly allocates the smaller remaining supply and demand in the current top-left cell to construct an initial transportation basis.

For transportation potentials, the reduced cost is ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$; a negative value identifies an improving entering cell.

Adding a nonbasic edge to a transportation tree creates one cycle; alternating equal additions and subtractions around it preserves every row and column sum.

Integer supplies and demands admit an integer optimum because an integer initial basis and every cycle pivot remain integer.

A matrix of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

A matrix is totally unimodular when every square subdeterminant is $0$, $1$, or $-1$; linear programs with such a constraint matrix and integer right side have integral vertices.

A matrix with entries in $\{0,1,-1\}$ is a totally unimodular matrix if every column has at most two nonzero entries, with opposite signs when both occur. To prove this, induct on the size of a square submatrix. A zero column gives determinant zero, a one-entry column reduces by cofactor expansion, and if every column has two entries then all column sums vanish, giving dependent rows. The total unimodularity of directed incidence matrices is a central instance.

The directed vertex-edge incidence matrix has one $+1$ and one $-1$ per nonloop column and a zero column for a loop. Every square subdeterminant belongs to $\{0,1,-1\}$. Induct on its size: a column with no nonzero entries makes the determinant zero; a column with one nonzero entry permits a cofactor expansion to a smaller determinant; and if every column has two nonzero entries, their opposite signs make the column sums zero, giving linearly dependent rows. Negating rows preserves absolute subdeterminants. Consequently the unsigned vertex-edge incidence matrix of a bipartite graph is totally unimodular: negate all rows in one part. The assignment problem is an instance, with row vertices and column vertices forming the two parts.