Why a failed search can have a certificate
Solving with may feel like a search over infinitely many candidates. Farkas' alternative replaces an unsuccessful search with a finite, checkable witness: a vector whose inner products with the columns of are nonnegative but whose inner product with is negative. A nonnegative combination of those columns could never have a negative inner product with . This separation principle also explains why multipliers appear in optimality conditions and what those multipliers actually certify.
We work in finite-dimensional Euclidean spaces, with , and componentwise inequalities. Empty constraint collections are allowed; in particular, the cone generated by no columns is . Inner products and norms are Euclidean.
A geometric fact about finitely generated cones
Definition 2.2.1
(Finitely generated cone)
Write the columns of as . The cone generated by them is
The cone is convex, and it contains whenever and . Closedness deserves proof: a continuous image of a closed set is not automatically closed.
Lemma 2.2.2
(Finitely generated cones are closed)
The cone generated by finitely many vectors in is closed.
Proof
(Reduce to independent generators, then use compactness)
Every has a representation using linearly independent columns. Start with any representation and discard zero coefficients. If its remaining columns are dependent, choose a nonzero dependence . Replacing by if needed makes some . Set and replace by . The coefficients remain nonnegative, at least one becomes zero, and the represented vector is unchanged. Repeat until the remaining columns are independent.
Now let converge to . There are finitely many independent subsets of columns, so a subsequence uses the same subset . If is empty, its vectors are zero. Otherwise the map is injective, hence there is a constant such that : minimize on the compact unit sphere. Thus the corresponding coefficient vectors are bounded. A further subsequence converges to a nonnegative vector , and . In Euclidean space sequential closedness proves closedness.
The alternative
Theorem 2.2.3
(Farkas' alternative)
Exactly one of the following systems has a solution:
- and ;
- and .
Proof
(Project b onto the cone)
The two cannot both hold, because . Conversely, if the first fails then . Let be the closest point of the nonempty closed convex cone to . Projection gives for every . Taking and shows . Thus, with , every satisfies , and
Each column belongs to , hence .
Proof X-ray
Where closedness and the cone property enter
The easy half uses only and . The hard half has three moves. First, closedness of guarantees that a nearest point exists and lies in ; since , this gives and a positive gap , which is where finite generation is used. Second, is a cone, so and are admissible test points; for a general convex set the projection inequality would give only an affine separation , and the cone property turns it into the homogeneous statement with . Third, testing at the generators themselves turns that statement into . Strictness of is then the orthogonality combined with .
Worked example 2.2.4
(A certificate is shorter than a search)
Try with . The equations give , , so this particular system is infeasible. A certificate is : its products with the two columns are and , but . Anyone can verify these three inner products without trusting the attempted solution.
Common mistake
(Weakening the strict inequality in the certificate)
The strict inequality cannot be weakened to : would then satisfy the second system even when the first is feasible. The certificate is a proof of infeasibility, not an approximate solution.
An inequality form
The same alternative can be stated for a system of linear inequalities.
Corollary 2.2.5
(Farkas' alternative for inequalities)
For and , exactly one system holds:
Proof
(Split the free variable and add slack)
Write with , add slack , and apply the alternative to . Its witness has , and , that is , , together with . Conversely, multiplying by such a nonnegative would give .
This form makes a contradiction by adding inequalities explicit.
Worked example 2.2.6
(Adding two inequalities to reach a contradiction)
The system , in one variable has and . The vector is nonnegative, and , so the system is infeasible. Concretely, adding the two inequalities gives . The edge case of an empty generating set behaves the same way: if , then , and for the vector is a certificate, since the condition is vacuous and .
From linearized descent to multipliers
At a feasible point of a smooth constrained problem, collect the gradients of the active inequalities as rows of and the equality gradients as rows of . Write . A linearized direction satisfies and . Does some such direction give strict objective decrease, ? Because the homogeneous conditions are unchanged by positive scaling, this is equivalent to the feasibility of
Theorem 2.2.7
(A certificate for absence of linearized descent)
Exactly one of the following holds: (i) there is with , and ; (ii) there are and an unrestricted such that
Proof
(Apply the inequality alternative to the normalized system)
Express as the two inequalities and . If the normalized descent system is infeasible, the inequality alternative provides multipliers satisfying
Thus ; divide by and set . Conversely, if the displayed multiplier equation and a strict descent direction both existed, taking their inner product with would imply
contradicting strict descent. Equality multipliers have no sign restriction: they are differences of two nonnegative multipliers.
For an optimization problem with and , assign zero multipliers to inactive inequalities. The certificate is then the stationarity, multiplier-sign and complementarity part of KKT. It follows from absence of linearized descent, not from feasibility alone. A constraint qualification such as MFCQ is used separately to establish that absence at a local minimum: it connects the linearized directions to actual feasible curves.
Common mistake
(Reading a KKT certificate as a minimum certificate)
A KKT certificate by itself is not a minimum certificate for a general nonconvex problem; convexity or another sufficient condition must be checked. The theorem above only excludes strict linearized descent at the given point.
Worked example 2.2.8
(Deriving a multiplier from the direction test)
Minimize subject to and . At , the active gradients are and , while . The linearized constraints give and , so : strict linearized descent is impossible. Stationarity gives , hence , . In this example feasibility itself yields , providing a separate global-optimality proof.
The distinction between actual and linearized directions matters, and without a constraint qualification the multiplier conclusion can fail at a genuine minimum.
Counterexample mode
A global minimum without multipliers
Claim: at every local minimum of a smooth problem there are multipliers satisfying stationarity. Minimize subject to . The only feasible point is , hence it is a global minimum. But the active constraint gradient is there, so every is linearized feasible and gives : strict linearized descent exists, and no multiplier satisfies . The repaired statement adds a constraint qualification. MFCQ fails here, because no satisfies ; under MFCQ, local optimality excludes linearized descent and the theorem then supplies the multipliers.
Practice and solutions
Quick check
(For and , find an infeasibility certificate for , .)
A single number suffices.
Solution · Answer
Take : and .
Quick check
(Let , and . Find the multiplier certificate and explain why there is no strict linearized descent.)
Solve the stationarity equation, then check it against the direction conditions.
Solution · Answer
Stationarity gives and . Alternatively, gives and gives ; hence .
Quick check
(In the counterexample , does the direction arise as the derivative of a feasible curve through ? Why?)
Describe the feasible set first.
Solution · Answer
No. Every feasible curve is identically zero because the feasible set is , so its derivative is zero. A linearized direction need not be an actual feasible velocity without suitable regularity.