Farkas Lemma Certificates
Find a feasible nonnegative combination or a separating certificate of impossibility.
By Riano · Published · Updated · Report a correction
Farkas Lemma Certificates
Farkas' Lemma provides a powerful tool in linear algebra and convex optimization. It states that exactly one of two possibilities is true for a given matrix A and vector b: either the system Ax = b has a non-negative solution (x ≥ 0), or there exists a vector ysuch that ATy ≥ 0 and bTy < 0. This separating vector yserves as a certificate of infeasibility.
Worked Example
Consider the wedge cone where A = [(1,0), (1,1)] and the target b = (1, 2).
- To find the algebraic solution, we calculate x = A-1b.
- Since x1 + x2 = 1 and x2 = 2, we find x1 = -1 and x2 = 2.
- Since x1 = -1 < 0, the target is outside the cone, so it is infeasible.
- According to Farkas' Lemma, there must be a separating hyperplane. The expected result is the certificate y = (1, -1), yielding yTb = -1.
- Checking the conditions: ATy = (1, 0)T ≥ 0 and bTy = 1(1) + 2(-1) = -1 < 0.
- Thus, y successfully certificates the infeasibility.
Experiment
- Select the Wedge cone from the Cone control.
- Select the Above wedge target from the Target control.
- Observe that the feasibility result displays Infeasible.
- Notice the separating certificate vector y appear in the visualization and results table.
Explore this experiment directly at https://riano.app/module/farkas-lemma-certificates.
Limitations
This module only visualizes two-dimensional systems (matrices with two rows and two columns). Farkas' Lemma naturally extends to arbitrary dimensions and general convex cones, but finding the separating certificate y in higher dimensions typically requires solving a linear programming problem rather than inspecting the signs of A-1b. Furthermore, numerical precision issues can arise when testing inequalities near the boundaries in floating-point arithmetic.
References
- Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. Available at: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf.
This foundational text provides a comprehensive treatment of convex analysis, separation theorems, and theorems of the alternatives such as Farkas' Lemma.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Farkas Lemma Certificates module.
Try Farkas Lemma Certificates on Riano →