These feasible potentials give the lower bound on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.
Complementary slackness Created 2026-09-24 Updated 2026-11-05
For the primal maximization , and dual minimization , , a feasible pair has the nonnegative objective-gap decomposition
Thus equal objective values are equivalent to
These are complementary slackness. Combined with primal and dual feasibility they certify optimality by weak duality. Conversely, primal and dual optima satisfy them by strong duality.
A positive dual multiplier forces its primal constraint to be tight, and a positive primal variable forces its dual constraint to be tight. A tight constraint need not have a positive multiplier: both factors in a complementary product may be zero. This distinguishes ordinary complementary slackness from a stronger strict-complementarity assertion. In the example under linear programming, the third primal inequality is slack and its multiplier is zero.[ref]
Conic primal-dual gap 2026-10-14
For a feasible point and a feasible dual variable , weak duality follows from one identity:
The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:
Both optima are finite when such a pair exists. Consequently,
These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.
For the nonnegative-orthant optimality certificate example, is feasible and costs . Pairing it with gives , so its cost exceeds the optimum by at most . Here the optimum is known to be , and the bound is exact. Pairing the same with the weaker certificate gives : a valid but less informative guarantee.
The identity assumes exact primal and dual feasibility. With a dual linear-system residual , it becomes
The second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when is large; a separate bound follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.
For an exact arithmetic example, minimize subject to . The point is optimal. A proposed multiplier is nonnegative and gives zero cone dot product because the slack is zero, but violates by . Its purported lower bound is , exceeding the optimum. The missing term explains the failure.
Cut capacity Created 2026-10-07 Updated 2026-10-18
The cut capacity of , with the complement of a set, is
Only outward directed edges contribute; incoming and internal edges contribute nothing.[ref]
Here is the accounting behind the bound, using nonnegative original edge amounts in a finite flow network. Sum the divergence of a flow over the vertices in :
An edge with both endpoints in appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since , and every other vertex satisfies flow conservation, the left side is the flow value. Thus
The inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.
For in the running example, explicitly add the two divergences of a flow:
The internal edge cancels. The edge is a genuine original directed edge entering , so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains .
Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, because
and every term is nonnegative. For the two outward edges are saturated and there are no incoming edges, so the gap is zero. For all outward edges are still saturated, but the incoming flow of gives a gap of . This explains exactly why the second cut of a flow network is not a minimum cut.
On , give an adjacent edge capacity equal to the larger endpoint distance from the diagonal. The set has outgoing edges: two at each interior diagonal vertex and one at each endpoint. Every such edge has capacity one. Thus any flow from above to below the diagonal is at most ; a feasible path decomposition attaining this value certifies optimality by weak duality.
Farkas certificate for linear inequalities Created 2026-10-07 Updated 2026-10-14
Let and . For unrestricted , the system of linear inequalities has no feasible point if and only if there is a vector with
The entries are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition cancels every variable, leaving the contradiction
This is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.
Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates , drawn as in the diagram, must satisfy
Write every row in the same direction:
Then and . The nonnegative weighted sum, with Lagrange multipliers , is visibly
Each individual requirement defines a half-space in the plane. Even every pair has a feasible point: satisfies the first two, the first and third, and the second and third. Their common intersection is empty, because the first two force , while the third demands at most .
Figure 1.
Each half-plane is nonempty, but their three constraints add to the contradiction
. The first three panels shade each half-space separately. The final panel compares the simultaneous requirements with ; the two regions are disjoint. The points , and satisfy only pairs of constraints. Details.
Why cancellation is necessary for unrestricted variables. A nonzero linear functional can be made arbitrarily positive or negative by varying unrestricted , so alone would not yield a contradiction. Equality is essential here. If is also imposed, the sufficient certificate becomes , , , because then . This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows and use the equality certificate on the enlarged system. Reversing all constraints to reverses the scalar sign to , as in the normalized integer Farkas infeasibility gap.
Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute and , and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by normalizes to . With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual is a diagnostic rather than an exact cancellation: unrestricted can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.
The same weighted sums give dual bounds. For the linear program maximizing over unrestricted with , any satisfying gives
for every feasible point. Minimizing over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize subject to , , . The multipliers give the upper bound , attained at . The infeasibility example above uses the same row directions, but lower bounds of on both coordinates. Its multipliers cancel the objective function as well as the variables: with would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.
Why every inconsistent system has such a certificate. Introduce a slack variable vector and write . Split the unrestricted vector as with . Applying Farkas' lemma to the column matrix gives , , and . The first two conditions together are exactly . This reduction explains both the equality and the nonnegative row multipliers.
Lagrange dual function 2026-10-06
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.
Lagrangian duality Created 2026-10-06 Updated 2026-10-18
A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.
Let be a nonempty decision domain on which the objective function and the constraint functions are finite. Write the primal problem and its optimization Lagrangian as
The inequality Lagrange multipliers obey ; the equality Lagrange multipliers are unrestricted real numbers. Define the Lagrange dual function and dual optimal value by
The inner infimum keeps , but releases the displayed optimization constraints. It can be , giving an uninformative lower bound. A different domain changes the bound.[ref]
Here is the entire weak duality argument. For any feasible point and allowable Lagrange multipliers,
The first inequality is the definition of an infimum; the second uses and . Taking the infimum over feasible , then the supremum over allowable Lagrange multipliers, gives . No convexity is used.
The Lagrange dual function is a concave function, since each fixed decision makes an affine function of the Lagrange multipliers.[ref] Explicitly, write and choose two points where is finite. For and every ,
Taking the infimum over proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating can itself be difficult.
For finite optimal values, strong duality means , or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when is finite.[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.
Linear programming duality Created 2026-09-24 Updated 2026-11-05
Linear programming duality pairs the standard maximization problem
with the minimization problem
The dual variables form nonnegative combinations of primal inequalities. If and are feasible, then
This is weak duality, giving independently checkable bounds before any algorithm reaches an optimum.
For a feasible primal with finite optimal value, strong duality for finite-dimensional linear programs ensures attained primal and dual optima with equal values. Their objective difference decomposes into nonnegative products of variables and opposite slacks, yielding complementary slackness. The worked allocation in linear programming has primal point and dual multipliers , both with value ten. Sign conventions change for minimization, equality rows and unrestricted variables; a dual formula belongs to its declared primal form.
For the linear program maximizing with , , a vector with proves for every feasible . If a feasible 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.
Max-flow min-cut theorem Created 2026-09-24 Updated 2026-10-14
For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:
For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.[ref]
Why is a cut of a flow network an upper bound? Sum flow conservation on its source side . Internal edge contributions cancel, leaving
Only directed edges leaving contribute to cut capacity. Directed edges entering are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.
In the running flow network, the two internal vertices give four possible source sides. For , the cut capacity is . For it is . For it is ; the incoming edge contributes nothing to that cut capacity. Finally, gives . Thus the minimum cut has cut capacity , matching the explicitly computed maximum flow.
Figure 1.
Maximum flow of value five and two minimum-cut certificates
. Labels show flow/capacity on each directed edge. The shaded source sides give cuts of capacities three plus two and two plus one plus two, both equal to the flow value. Details.
Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.[ref]
Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight . Pairing everyone is a perfect matching, and its maximum total weight is . Consider the capacitated linear program
It is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row and column both below one. Increasing by the smaller of their positive deficits remains feasible and increases the objective because , a contradiction.
Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence . One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.
The dual linear program assigns nonnegative dual variables to the row and column capacity constraints:
These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is . It is feasible, for example by taking and . Strong duality now gives . In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.
For a direct weak duality check, sum over any pairing . Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.
The point satisfies dual feasibility and supplies an upper bound of by weak duality. Directly, take one copy of the first constraint and four copies of the second:
Since , the original objective function is at most . The feasible point attains . Hence
There are also nonvertex optima. In terms of the slack variables, the exact objective function identity is
Equality requires , leaving the entire optimal face
Negative or on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.
With the new right sides, the dual function is
Take . Then , so the minimization dual is unbounded below:
By weak duality, any feasible integer point with finite objective would have to have objective at most every dual value, which is impossible. Thus the modified integer program is infeasible and has no optimal solution. This is an infeasibility certificate from an unbounded Lagrangian dual.
There is also a direct certificate: the assignment equalities force , while the new bounds force it to be at most . Even the modified linear relaxation is infeasible. The earlier problem also had no integer solution, but there its fractional feasible point kept the dual value finite.
Since every reduced weight is nonpositive and every feasible variable is nonnegative, any feasible assignment satisfies
For , each selected entry has zero reduced weight, and each unselected entry has zero variable. Thus every product vanishes and equality holds:
The two hypotheses therefore form one optimality certificate: the first provides a universal upper bound, and the second makes the proposed assignment attain it. This is weak duality plus complementary slackness for the maximization assignment problem. For a minimization assignment, the sign reverses: gives a lower bound, with equality on the selected arcs certifying optimality.
For a directed graph, the uncapacitated minimum-cost flow problem is
Positive is external supply and negative is demand; summing the flow balances requires . There are no finite upper arc capacities. Let be the oriented incidence matrix with tail and head . For free dual potentials , the Lagrangian is
Its infimum over nonnegative flows is exactly when every network reduced cost is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes subject to these inequalities. For a primal feasible flow and dual feasible potentials,
This derives weak duality and the complementary slackness condition . A feasible pair satisfying it has equal objectives and certifies optimality.
A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances , and take . The shortest-path inequality proves dual feasibility, with tightness on the shortest-path tree.
For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This gives
The remaining arcs have zero flow. The total initial cost is . This is a basic feasible solution, though degenerate because the tree flow on is zero.
Normalize . Tree tightness gives
The non-tree reduced costs are
The negative reduced cost on identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending along increases the flows on by and decreases those on by ; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits to the minimum of the four decreasing flows, namely . Choose arc to leave among the tied limiting arcs.
After this one pivot the nonzero flows are
and every other arc flow is zero. The objective decreases by , giving cost .
For the new tree, tight potentials normalized at vertex 1 are
All tree reduced costs are zero. For the non-tree arcs they are , respectively, so the potentials are dual feasible. Their dual objective is
matching the primal cost. Complementary slackness therefore proves
This is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.
True. Suppose a dual feasible solution exists. For every primal feasible , weak duality gives , a finite upper bound independent of . This contradicts primal unboundedness. Therefore an unbounded primal has an infeasible dual. Here “unbounded” arithmetic means a nonempty feasible set with objective values unbounded above, rather than merely an unbounded feasible region.
For the linear program in maximization form, a nonnegative multiplier of the resource inequalities gives
whenever . Equivalently, the Lagrangian is ; its supremum over is finite exactly when . Minimizing this bound gives the dual linear program
The displayed inequality proves weak duality directly.
For the final simplex tableau, the basic-variable order is . With interpreted as the ordinary unpriced slack variables, its constraint equations give
The bottom row is read in the reduced-cost convention , with right side minus the basic objective value. It says the reduced costs of are . Thus optimality requires , while can increase without changing the objective until reaches zero. The complete primal optimum set is
Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns are
Because the first basic column is that of , the original constraint data are
The slack reduced costs give and
Consequently the recovered homogeneous linear program is
Every point in the optimum segment has value . Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum
The printed bottom-right entry is , but it must be for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to gives the reconstructed problem above. Alternatively, if an affine objective is permitted, has the displayed optimum value and unchanged reduced costs; the corresponding affine dual objective is . Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.
Associate free real dual variables and with the row and column equality constraints. The Lagrangian for the transportation problem is
Its infimum over is finite exactly when for every pair. The linear programming duality therefore gives
The dual variables have no sign restrictions because the primal constraints are equalities.
A feasible shipment is optimal if and only if there exist feasible transportation dual potentials satisfying complementary slackness:
Thus every occupied route must have . To see sufficiency explicitly, the primal minus dual objective is
and complementary slackness makes it zero. This is the weak duality certificate. Necessity follows from strong duality for the feasible, bounded linear program. If the total supply is positive, gives feasibility; if , does. The feasible shipments form a closed bounded set, so the primal optimum is attained. This also covers zero supplies and demands. The one redundant equality merely leaves the dual gauge freedom .
The dual linear program is
The negatives of the final slack payoff coefficients give . Its three dual constraints are equalities, and its objective is . Equality with the primal objective proves optimality by weak duality, independently of tableau sign conventions. It is also the complementary slackness certificate, with all primal variables and all dual variables strictly positive.