Farkas' lemma Created 2026-10-07 Updated 2026-10-14
For a real matrix and a vector , exactly one of the following systems has a solution:
The linear inequalities here are componentwise. In the first system is nonnegative; in the second system is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.
Build the target, or separate it. Write the columns of as . Then is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated cone
A solution explains how to build from those columns. A certificate instead defines a linear functional . The condition says that its dot product with every generating column is nonnegative, and hence with every point of . But places the target strictly on the other side of the hyperplane . Thus belongs to the dual cone of and rules out every allowed conic combination at once.
A certificate that can be checked by eye. Take the identity matrix
Here is the nonnegative orthant. The equation forces , violating . The certificate gives
The linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while has first coordinate . For comparison, the target is obtained with .
Figure 1.
Nonnegative column combinations lie in a cone, while a Farkas certificate separates the target
. For , the shaded nonnegative orthant is the conic hull of the two columns. The hyperplane for is the vertical axis; lies strictly on its negative side. The obtainable target illustrates the other alternative. Details.
Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.
Brief geometric proof. The two systems cannot both hold, because they would imply
For existence of a certificate when , closedness of finitely generated cones makes a closed convex cone, so separation from a closed convex cone supplies and for every . Testing each column gives . Concretely, let be the Euclidean projection onto a convex set of onto and set . The projection inequality gives for . Testing and gives , whence . In the example, and . Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.
An original historical source is Julius Farkas's [ref]. The linked archival record verifies the author, title and publication details.
Linear polyhedron Created 2026-10-06 Updated 2026-10-14
A linear polyhedron is an intersection of finitely many closed affine half-spaces in finite-dimensional real space. It may be empty, unbounded, or lower-dimensional. This usage differs from a three-dimensional geometric polyhedron. The strict separation of disjoint linear polyhedra follows from linear programming duality.
Linear programming Created 2026-09-24 Updated 2026-11-05
Linear programming optimizes a linear function over finitely many linear equalities and inequalities. A common convention is
The feasible region is a linear polyhedron, so the problem has convex geometry even when it represents a discrete-looking allocation. A linear programming relaxation drops integrality requirements and supplies bounds for an integer program.
For a concrete example, maximize subject to , , , and . The point is feasible and has value ten. Multiplying the first inequality by two and adding the second gives
Thus this point is globally optimal. The multipliers form a dual linear program certificate; the unused third constraint has zero multiplier. This small calculation captures the purpose of linear programming duality: a feasible solution gives a value, while a feasible dual combination proves that no better value is possible.[ref]
A model can instead be infeasible or unbounded. The simplex method uses changing bases, while interior-point methods approach the optimum through the feasible interior when suitable initialization or embedding is supplied. A chosen numerical algorithm must report which case occurred and respect the input's sign and standard-form conventions.
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.
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 objective function is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.
If the primal is feasible and bounded below, strong duality and attainment for a linear program give , and with
Set , , , , , and
The first three embedding equations hold. Substituting their equalities into the fourth gives precisely .
If the primal is infeasible, the Farkas alternative supplies with and . Take , , , and . These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone with and . Set , , and . This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,
The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.
To recover information from the transformed optimum, multiply the first three original embedding equations by , , and , respectively, and add. Their cross terms cancel; the fourth equation gives
At , nonnegativity forces and . The equations also imply
Thus any normalized zero-objective point has : if , all these coordinates vanish, and then , contradicting normalization.
If , division by gives a primal-feasible point and dual-feasible point with equal objective function values; hence they are optimal. If , then , , , and
Therefore either certifies primal infeasibility, or is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function ; it gives either a feasible point or a direct primal infeasibility certificate.
A degenerate optimal point can have and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with . A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.
This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.
A balanced transportation problem chooses nonnegative shipments minimizing , subject to and , where the total supply equals total demand. For multipliers , its Lagrangian is
Taking its infimum over produces the linear programming duality problem of maximizing subject to . These are the transportation dual potentials.
The transportation simplex algorithm starts with a feasible transportation spanning tree of basic entries, obtainable by filling the north-west available cell with the smaller remaining supply or demand. Set on basic cells; this determines all potentials up to adding a constant to all and subtracting it from all . If all nonbasic reduced costs are nonnegative, feasibility and the dual bound prove optimality. Otherwise let a negative-cost cell enter. It closes a unique cycle in the basic tree. Alternate additions and subtractions around that cycle and choose the largest amount preserving nonnegativity, namely the minimum shipment on the subtraction cells. A cell that reaches zero leaves the basis. The cost changes by the entering reduced cost times the pivot amount. Zero basic cells and an anti-cycling rule can handle degeneracy; all pivots below are nondegenerate.
The north-west initial shipment matrix is
With , its transportation dual potentials are and . The most negative reduced cost is . The cycle is ; the pivot amount is . Hence
Now and . Enter , of reduced cost , on cycle . The amount is , giving
The new potentials are and . Enter , of reduced cost , on cycle . The amount is . Thus
To certify optimality in the original transportation problem, take and . Their entire reduced-cost matrix is
They satisfy dual feasibility, and their value is , equal to the shipment cost. The minimum transportation cost is therefore , with no unproved optimality assertion from the iterations alone.
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 .
In a finite two-person zero-sum game the row player chooses , the column player chooses , and the row player receives while the column player receives . The row player maximizes that payoff and the column player minimizes it. Mixed strategies are probability vectors and , giving expected row payoff .
Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff :
Similarly the column player minimizes an upper guarantee :
The values are unrestricted real variables; no positivity shift of the matrix is required.
To see the linear programming duality explicitly, introduce nonnegative multipliers for the first problem's payoff inequalities and multiplier for its normalization. Its upper-bound Lagrangian is
The supremum over free and nonnegative is finite precisely when and , and is then . Minimizing it gives the displayed column problem, proving that the programs are a dual pair.
A sufficient optimality certificate is a pair of probability vectors and a common value satisfying
Equivalently, both programs are feasible with equal values. Positive-probability rows then have and positive-probability columns have , the complementary slackness conditions. These conditions certify a saddle point and hence optimal mixed strategies for both players.
The dual constraints and objective coefficients on are unchanged, so remains dual feasible. Since every component of is positive, complementary slackness forces every constraint of any primal optimum paired with it to bind. Let be the original three-by-three constraint matrix and . It is invertible, and the only possible paired primal point is
If this point is nonnegative, it is primal feasible with zero slacks and , proving optimal. Conversely, if is optimal, linear programming duality supplies a paired primal optimum, and complementary slackness forces it to be exactly this point. This proves the strictly positive dual certificate and right-hand-side sensitivity criterion:
Non-strict inequalities are essential: boundary cases can be degenerate but retain the same optimal dual vector. This is the complete range, not just a small-perturbation sufficient condition for linear programming sensitivity within a fixed optimal basis.
Write the amended primal as with , . A convenient linear programming duality convention uses and gives subject to . Explicitly the dual is
The optimal dual vector is the negative of the three payoff-row slack coefficients:
Indeed substitution gives , so all dual inequalities hold. To certify optimality directly by weak duality, for any feasible primal and dual vectors,
where the second inequality uses and . Our feasible primal and dual vectors have equal values , so neither can be improved. This is a linear programming optimality certificate.
Fix and a finite epsilon-net in . Choose a Borel map with , for example the nearest point with ties broken by index. Its cells give discrete probability measures with masses and . Let
The feasible set is nonempty and compact, so the minimum exists. Pushing any coupling forward by changes its cost by at most , hence . Conversely, lift a discrete coupling by the measure
Terms with zero row or column masses vanish. This lift has marginals , and its cost differs by at most . Therefore
Here is the finite linear programming duality proof. Write and consider the convex cone
It is closed and finitely generated. One elementary justification of closedness is to reduce each nonnegative representation to linearly independent generators, eliminating a coefficient along any linear dependence; after choosing a subsequence using the same subset of generators, their independent coordinates have bounded, convergent coefficients whenever the represented vectors converge. For , the point lies outside . Separation from this closed convex cone gives coefficients with
If , summing the middle inequalities against any feasible contradicts the last one. Thus , and , obey with dual objective greater than . The weak inequality already proved gives the reverse bound. Letting proves finite strong duality.
Reduce this discrete dual to a single Lipschitz function. For a feasible pair put . The triangle inequality gives , while and . Consequently
Conversely, any -Lipschitz vector gives a feasible pair . Adding a constant leaves its objective unchanged, so impose . The resulting feasible set is compact, and its maximum is .
For a maximizing vector, the McShane extension theorem has the following explicit proof in this situation. Define
The triangle inequality proves that this extension is -Lipschitz, and the discrete Lipschitz condition makes . Thus is a continuous feasible pair. Because ,
Letting , together with part i, proves . The infimum defining is also attained: the set of couplings is a closed subset of the compact space of probability measures on , and integrating the continuous cost is continuous for the weak-star topology.
Use the Lipschitz constant convention in the final quantity; it is a seminorm, with constants having value zero. Also interpret the coupling space as . The printed has an undefined . The third quantity has a duplicated printed label; it is placed in part iii here, with the fourth in part iv.
First prove weak optimal transport duality. For any feasible continuous pair and any coupling of probability distributions with marginals ,
Taking the supremum over pairs and infimum over couplings gives . These quantities are finite: is a coupling and the continuous cost is bounded on the compact metric space . The zero pair is feasible, so .
The reverse inequality is established in part ii by finite approximation and a proof of the required finite linear programming duality. Parts iii and iv then show that all the dual formulations agree.
Introduce a free scalar . The epigraph reformulation is the linear program
For each fixed , the smallest feasible equals the maximum of the affine expressions, so the reformulation preserves the optimum.
Associate nonnegative multipliers with these inequalities. Its optimization Lagrangian is
Because and are unrestricted, the infimum is finite precisely when the coefficients of both vanish. Therefore the Lagrangian dual problem is
A feasible dual vector is a convex combination of the slopes whose mean slope is zero. It gives a constant lower bound on the maximum of the affine functions. The primal is always feasible, by taking and sufficiently large . If it has a finite optimum, linear programming duality gives attainment and equality with this dual; otherwise the dual is infeasible and the primal is unbounded below.
A transportation problem minimizes subject to nonnegative shipments, prescribed row supplies, and prescribed column demands.
One optimal shipment table is
which has the required row sums and column sums and costs .
For an optimality certificate, take row potentials and column potentials . Their sums equal costs in occupied cells and do not exceed any cost:
The dual value is , so linear programming duality proves optimality.
Associate nonnegative Lagrange multipliers with and with . The Lagrangian dual problem is obtained from
Its infimum over unrestricted is finite exactly when . Thus the dual is
The precise finiteness condition is . If , then on the feasible set. The primal is feasible and bounded below, and splitting into positive and negative parts makes the dual feasible. Linear programming duality therefore gives attained equal finite optima. Equivalently, the strictly feasible point satisfies the Slater condition, with the required finiteness hypothesis. This is strong duality in the usual finite sense.
If , there is with . Every , , is feasible and the objective tends to . The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as , but there are no finite optimizers. The paper does not assume full column rank of , so this qualification is necessary. The same calculation gives the support function of an inverse image of an infinity-norm ball, for finite decisions.
Keep as the domain restriction, introduce nonnegative Lagrange multipliers for , and introduce a free multiplier for . The maximizing Lagrangian is
Its supremum over is finite exactly when , and then equals . By linear programming duality, since the primal is feasible and bounded,
Minimizing over for fixed gives , the positive part of a real-valued function. Thus the threshold formula for the sum of the largest components is
For a direct attainment check, order the coordinates . Any is optimal for , while any is optimal for .
Robust optimization Created 2026-10-05 Updated 2026-10-06
Robust optimization chooses a decision while accounting for every parameter in a prescribed uncertainty set. A worst-case maximization takes the form with the decision chosen before the uncertain parameter. With affine dependence on the uncertainty, the support function and linear programming duality often replace the inner optimization by explicit constraints.
Support function of an inverse image of an infinity-norm ball Created 2026-10-05 Updated 2026-10-07
If , the support function is infinite along a kernel line. Otherwise linear programming duality gives the displayed minimum, attained because the corresponding linear programs are feasible with finite values. Splitting into nonnegative parts yields the equivalent minimum of . Thus worst-case revenue over a polyhedral uncertainty set is , with value off the row space.
For , linear programming duality gives
where is the positive part of a real-valued function. To see equality directly, order the coordinates and choose for , or for . The threshold expression then equals the sum of the largest components. Introducing the variables turns this convex piecewise-linear objective into a linear program.