For feasible points the duality gap decomposes asEach term in both sums is nonnegative. Therefore the gap is zero exactly when every product vanishes, namely the two sets of complementary slackness equations in the question (with or its negative making no difference to a zero product). If the equations hold, equality and weak duality prove optimality of both points. Conversely, if both are optimal and the optimal values are equal as assumed, the gap is zero, forcing each product to vanish. This proves both directions.
The expression presupposes that is invertible; positivity of the stated optimal coordinates alone would not prove that, so use the nonsingularity implicit in this expression. Let be the first components of and set . Then .
For any nonbasic column , introduce while changing the basic vector from to . This stays feasible for sufficiently small because every . Optimality at implies the objective slope . Therefore for every such column, and the basic columns satisfy equality. Thus is dual feasible, independently of the right-hand side.
For , the proposed is primal feasible andWeak duality, valid with unrestricted equality multipliers, proves . This also explains the stability of an optimal basis while its new basic coordinates remain nonnegative.
Project scheduling duality 2026-10-14
On the augmented precedence graph, the linear programming problemhas dual , with a unit source-to-sink flow. Equivalently, the dual is the negative of the optimal uncapacitated minimum-cost flow value with arc costs . The flow selects a longest path, while the time variables provide a matching weak duality bound.
// Target: mathematical-optimization.bigb
Shadow price of an inequality constraint 2026-10-14
A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use for in a minimization problem. With strong duality and a differentiable optimal value function, .[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.6.3, printed pp. 251–252, equation (5.58): local sensitivity
In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at is zero from both sides, although has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.
At , , and . Raising the bound to lowers the value to : the first-order prediction is a change of , while the exact change is . At , the same relaxation leaves and . At , tightening by costs , a second-order effect despite the zero Lagrange multiplier.
The derivative of the optimal value is the negative inequality multiplier
. Details. There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with , the Lagrange dual function changes by . Weak duality therefore givesAt this is , the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.
Strict feasibility for conic duality Created 2026-10-14 Updated 2026-10-31
For a proper cone , suppose a point satisfies and is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.9.1, printed p. 265: generalized Slater condition, strong duality and dual attainment
The two worked examples have strict primal points: has slack in the interior of the nonnegative orthant, and has slack in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.
Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.
In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.[ref]
A Primal-Dual Potential Reduction Method for Problems Involving Matrix Inequalities by Lieven Vandenberghe and Stephen Boyd. Publication record and authored abstract: A Primal-Dual Potential Reduction Method for Problems Involving Matrix Inequalities, Mathematical Programming, Series B, 69(1), 205–236 (1995)
Strong Lagrangian property Created 2026-10-14 Updated 2026-10-18
For a finite constrained optimum value and optimization Lagrangian , the strong Lagrangian property means that some finite Lagrange multiplier attains the dual lower bound exactly: . It includes dual attainment, but need not include primal attainment. It is equivalent to a non-vertical supporting hyperplane of a value function: a supporting slope gives , hence ; weak duality gives the opposite inequality. Conversely the infimum identity bounds every below by ; taking the infimum over gives the supporting inequality. No convexity assumption is needed for this equivalence.
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 hasThe 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 .
Transportation dual potentials 2026-10-14
Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: , since row sums are supplies and column sums are demands . The reduced costs are . 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.
Weak duality Created 2026-09-24 Updated 2026-11-05
Weak duality bounds every feasible primal objective by every feasible dual objective, with the direction set by the primal convention. For the primal maximization , , dual feasibility means and . HenceThe first inequality uses ; the last uses . For a minimization primal, feasible dual values instead provide lower bounds. The argument is algebraic and needs no assumption that optima exist or are equal.
If a feasible pair attains equal objective values, each side must already be optimal. If a maximization primal is unbounded above, no feasible finite-valued dual vector can exist. The converse of that last statement is not automatic: dual infeasibility can also occur when the primal is infeasible. Strong duality is the additional theorem asserting equality under suitable conditions.
