Motivation
A feasible solution to a linear program gives one bound on the optimum. A feasible solution to its dual gives a bound in the other direction. Approximation algorithms often use the resulting certificate to compare a discrete solution with an LP relaxation. But why should the best two bounds coincide? The answer requires hypotheses: an infeasible program has no primal optimum, and an unbounded program has no finite optimum to match.
We will prove strong duality for a concrete, widely used standard form. The proof eliminates variables from inequalities, keeping track of which nonnegative combination produced each new inequality. A final upper bound on the objective becomes the dual solution. This establishes existence as well as equality; it is not merely a numerical observation that two algorithms happen to agree.
Definitions and weak duality
Definition 4.2.1
(Primal and dual programs)
Let , , and . The primal and dual programs are
Inequalities are coordinatewise. A feasible point satisfies every listed constraint. A finite optimum is attained if a feasible point actually achieves it. Empty variable or constraint sets may be interpreted by the usual empty sums; the main proof also works in those cases when the primal is feasible and bounded.
Theorem 4.2.2
(Weak duality)
If is feasible for the primal and is feasible for the dual, then .
Proof
(Chaining two sign-controlled inequalities)
For every feasible ,
The first inequality uses and ; the last uses and . This is weak duality. Every feasible dual point is an upper bound on every feasible primal objective.
Theorems
Theorem 4.2.3
(Strong duality with attainment)
If the primal is feasible and its objective is bounded above, then both programs attain finite optima and their optimal values are equal.
Theorem 4.2.4
(Exact elimination of one real variable)
For a finite system of non-strict linear inequalities in , one can construct finitely many non-strict inequalities in that hold exactly when there exists a real satisfying the original system. Each constructed inequality is a nonnegative linear combination of the original inequalities.
Proofs
Proof of the elimination lemma
Proof
(Pairing lower and upper bounds)
Write each inequality involving as either an upper bound or a lower bound , by dividing by the positive magnitude of its coefficient and reversing the comparison when needed. Carry every inequality with zero coefficient of unchanged. For each lower–upper pair, add the inequality . It is obtained by adding positive multiples of the two original inequalities, so it is a nonnegative combination. If there are no lower bounds or no upper bounds, add no pair inequalities.
Every original solution satisfies the constructed system. Conversely, if the constructed system holds, all lower bounds are at most all upper bounds. When both families are nonempty, choose between their finite maximum and minimum. If only lower bounds occur, choose at least their maximum; if only upper bounds occur, choose it at most their minimum. If neither occurs, choose any real . The unchanged inequalities also hold. Thus a compatible exists, proving exactness.
Repeated elimination preserves the certificate property: a nonnegative combination of inequalities that were themselves nonnegative combinations of the original system is another nonnegative combination of the original system. The number of inequalities can grow rapidly, so this proof is an existence argument, not a claim of an efficient LP algorithm.
Proof of strong duality
Proof
(Projecting the objective and reading off the dual)
Introduce a real objective variable and consider the system
Eliminate all coordinates of using the lemma. The result is a finite system of inequalities in the single variable . Exact projection says that a real satisfies this system exactly when some feasible primal point has .
The projected set is nonempty because the primal is feasible. It is bounded above because the primal objective is bounded above. Therefore at least one projected inequality has a positive coefficient of : otherwise all its inequalities are lower bounds or constants and the nonempty set extends indefinitely upward. Normalize each positive-coefficient inequality to and let be the smallest of these finitely many upper bounds. Every feasible is at most .
The projected set is also closed, because it is described by finitely many non-strict inequalities. It contains some value and every number below : the same primal witness works for smaller . Its positive-coefficient inequalities bound it above by , and its lower-bound inequalities hold at because . Hence itself satisfies the whole projected system. Exactness supplies a primal feasible with ; the upper bound forces equality. The primal optimum is therefore attained at .
Choose one derived inequality attaining the minimum. It is a nonnegative combination of the original inequalities. Let its multipliers for , , and be , , and . The coefficient of in the combination is exactly because only the last original inequality contains . Since the chosen inequality is normalized with coefficient one, . Its coefficients of vanish, giving
Thus , so is dual feasible and has objective . Weak duality shows no dual feasible point can have smaller value, completing the proof.
Proof X-ray
The final inequality remembers its origin
The multiplier of must be one after normalization. The remaining multipliers are nonnegative and cancel the coefficients. Their cancellation is exactly the dual constraint; their right-hand side is exactly the primal optimum.
Worked examples
Worked example 4.2.5
(One variable and an attained certificate)
Maximize subject to and . The primal optimum is at . The dual minimizes subject to and , so also has value . Multiplying by three and adding gives .
Worked example 4.2.6
(A redundant bound)
Maximize subject to , , . The dual minimizes subject to and . Choosing certifies the primal optimum two. The looser constraint can have multiplier zero; duality does not require every constraint to contribute.
Worked example 4.2.7
(A feasible program with a negative optimum)
Maximize subject to and . Its feasible region is , and the optimum is . The dual minimizes subject to , , so and attains . Negative coefficients and negative optimal values are permitted.
Worked example 4.2.8
(A zero objective)
For any nonempty feasible region and , every feasible has objective zero. The dual point is feasible and has objective zero, even when the primal feasible region is unbounded. Boundedness of the objective is different from boundedness of the feasible region.
Common mistakes
Counterexample mode
Dropping the hypotheses
Maximize subject only to . The objective is unbounded above. Its dual would require the impossible inequality , so no finite dual optimum exists. Strong duality does not say that every pair of syntactically valid programs has two finite optima.
Common mistake
(Two bounds are not yet an optimum)
Weak duality alone does not prove equality. For example, a primal feasible point of value two and a dual feasible point of value ten give a correct interval, but not an optimality certificate. If the two values agree, weak duality immediately certifies that both are optimal. Strong duality guarantees the existence of an agreeing pair under the stated hypotheses; finding it efficiently is a separate algorithmic question.
Common mistake
(Copying signs without checking them)
The sign constraints matter in the weak-duality multiplication. If a coordinate of could be negative, multiplying a coordinatewise inequality by it might reverse the comparison. A program with unrestricted variables can be converted to standard form by writing each free variable as a difference of two nonnegative variables, but its resulting dual signs must be derived from that conversion rather than copied without checking.
What the projection proof does and does not supply
The elimination proof establishes that a finite upper bound is attained even if the feasible polyhedron itself extends to infinity. This follows from the finite closed description of the projected objective set, not from compactness of the original feasible region. The one-variable negative-optimum example and the zero-objective example illustrate both possibilities.
The derived multipliers are exact certificates over the stated real data. For rational input, elimination uses rational additions, multiplications and divisions, so it yields rational witnesses in principle. The number and bit lengths of intermediate inequalities may grow rapidly. Nothing here establishes the polynomial running time of a particular LP solver or numerical reliability of floating-point output. A computational certificate should be checked against the original inequalities using a suitable exact or certified arithmetic model.
Common mistake
(LP duality does not close an integrality gap)
For integer optimization, even an exact LP optimum may be strictly larger than the optimum over integer solutions. Strong duality equates the two continuous LP values; it does not remove an integrality gap. Approximation proofs can still use the LP optimum as a bound, provided their rounding or primal–dual analysis accounts for that gap separately.
Following an elimination step
Consider , , and . Written as bounds on , these say , , and . Pairing the first upper bound with the two lower bounds gives and . After normalizing the latter, the projected restriction is . The coefficient of the objective inequality in this certificate becomes one only after we multiply by three. In the resulting original-inequality combination the multiplier of is three, exactly the dual optimal solution , whose objective matches the primal optimum.
Multiple upper bounds can lead to several projected inequalities. Their smallest right-hand side controls the maximum objective, while the others remain valid but weaker bounds. If two bounds tie, either one can supply a dual certificate; this is one reason an optimum may have more than one dual solution. Redundant intermediate inequalities may be retained without changing the projection, though they can make the elimination procedure much larger.
The certificate also explains complementary slackness for any pair of feasible points with equal objectives. In the weak-duality chain, the gap decomposes as
Both terms are sums of nonnegative products. If the objectives agree, every product in both sums is zero: a positive dual multiplier forces its primal inequality to be tight, and a positive primal variable forces the corresponding dual inequality to be tight. Conversely, those zero-product conditions for feasible points make the objectives equal and certify optimality. The conditions do not require every tight constraint to have a positive multiplier.
Concept lensGeometric
The objective as a combination of active normals
Since , we have , where is the th row of . By complementary slackness only constraints tight at an optimal carry positive weight. So lies in the cone of outward normals of the active constraints: no feasible direction at increases the objective.
As a concrete check, in the redundant-bound example the first multiplier is one and its bound is tight; the second multiplier is zero and its bound has slack three. The primal variable is positive and the dual inequality is tight. These are consequences of a zero gap, not extra assumptions needed for strong duality.
Summary
Eliminating variables from finitely many non-strict inequalities preserves exact feasibility and records nonnegative combinations. Projecting the primal objective to one dimension gives an attained finite upper bound. The multipliers producing that bound form a feasible dual solution of the same value. Weak duality then proves both solutions optimal.
Exercises
Quick check
(Maximize subject to and . Give primal and dual optimal solutions and their common value.)
Write the dual first.
Solution · Answer
The primal point has value six. The dual minimizes with and ; has value six. Weak duality certifies both.
Quick check
(Eliminate from and . For which does a compatible exist?)
Compare the two bounds.
Solution · Answer
The pair is compatible exactly when , or . For such , choosing satisfies both inequalities.
Quick check
(A feasible primal point has value seven and a feasible dual point has value seven. Explain why neither can be improved.)
Use weak duality in both directions.
Solution · Answer
Weak duality bounds every primal value above by seven and every dual value below by seven. The displayed feasible points attain both bounds.
Quick check
(Maximize subject to and . Does the theorem apply? Explain.)
Check the hypothesis of the theorem first.
Solution · Answer
The constraints are inconsistent, so the primal is infeasible. The strong-duality theorem stated here assumes primal feasibility and does not apply.