Certify infeasibility by a separating vector

Try

Can nonnegative numbers x₁,x₂ satisfy x₁+x₂=−3? The answer is no because the left side is nonnegative. This simple sign contradiction is a Farkas certificate. In matrix notation A=(1,1), b=−3 and y=1 give Aᵀy≥0 but bᵀy<0. If Ax=b with x≥0 existed, multiplication by y would force bᵀy=xᵀAᵀy≥0, contradicting the negative value. The certificate can be checked without searching all possible x.

Predict

Predict why nonstrict negativity is insufficient. The zero vector y always gives Aᵀy=0 and bᵀy=0, even for feasible systems. Strict negativity creates the contradiction. Predict also what geometry lies behind the general result: the vectors Ax with x≥0 form the cone of nonnegative combinations of A’s columns. If b is outside that cone, a separating hyperplane should place all attainable vectors on one side and b strictly on the other.

Experiment

Take columns a₁=(1,0), a₂=(1,1). Their cone consists of points with first coordinate at least the nonnegative second coordinate. Test two right sides.

Right side b	Feasible representation or certificate
(3,2)	b=1a₁+2a₂
(1,2)	y=(1,−1), Aᵀy=(1,0), bᵀy=−1

Verify every dot product. Then explain why the same separating vector works for any b whose second coordinate exceeds its first. A certificate may describe a whole region of infeasibility, but it must still be checked against the actual right side in the problem being reported.

Understand

Farkas’ alternative says exactly one of these systems is feasible: Ax=b,x≥0; or Aᵀy≥0,bᵀy<0. Exclusivity follows from the multiplication contradiction. To prove that one exists, let K be the finitely generated cone of A’s columns. Such a cone is closed. One proof reduces every conic combination to an independent active support: for dependent active columns choose a nonzero dependence, reverse its sign to have a positive coefficient, and subtract the largest nonnegative multiple that keeps all current coefficients nonnegative. At least one coefficient becomes zero. Repeat until the support is independent.

For a convergent sequence in K, choose a subsequence with the same independent support, possible because there are finitely many supports. The coefficient map on that independent span has a continuous inverse; coefficients therefore converge to nonnegative limits, proving the limit lies in K. If b is outside K, project b to p in K. The projection inequality gives (b−p)·(k−p)≤0. Taking k=0 and k=2p shows (b−p)·p=0. Set y=p−b. Then y·k≥0 for every k in K, while y·b=−||b−p||²<0. In particular Aᵀy≥0, supplying the certificate.

Apply

Explain every finite-dimensional assumption in that proof. Projection exists because the cone is nonempty and closed, and is unique because it is convex. The support argument uses finitely many generators. A general nonclosed cone can have a point in its closure but not in the cone, preventing strict separation of this form. This is why a geometric slogan about “drawing a line between sets” is not enough for every possible infinite-dimensional or nonclosed model.

To handle inequalities, introduce nonnegative slack variables and convert to equality form. Keep track of the resulting sign restrictions on certificate coordinates. Different textbook versions of Farkas use opposite signs; they are equivalent after multiplying the separating vector by minus one, but mixing conventions halfway through a proof destroys the contradiction.

Continue

A useful certificate consists of the vector, its sign checks and the strict negative dot product. Continue to Linear programming duality to use related multiplier combinations as objective bounds. Feasibility certificates and optimality certificates answer different questions, but both replace an uninspectable search claim with a finite algebraic verification.