8
$\begingroup$

I worked on an exercise to prove Farkas' lemma, which states that for $A \in \mathbb{R}^{m,n}$ and $b \in \mathbb{R}^n$ exactly one of the following is true:

  • There exists $x \ge 0$ such that $Ax=b$.
  • There exists $y$ such that $A^T y \ge 0$ and $y^T b < 0$.

This is simply a trivial fact about the separation between two closed convex sets: $S_1 = \{ b \}$ and $S_2 = \{ Ax \mid x \ge 0 \}$.

Given its simplicity, there must be some broader significance or application of this fact. Can anyone enlighten me as to what it is?

$\endgroup$
  • 1
    $\begingroup$ Farkas lemma is the geometric interpretation of Duality in linear programming . $\endgroup$ – Red shoes Mar 1 '18 at 7:03
4
$\begingroup$

The feasible set of the optimization is usually written as

$$\{x| x \ge 0, Ax=b\}$$

We might construct the above feasible set by asking a client what do they desire and we included that criteria in the set above. A natural question to ask is whether the set is non-empty, i.e. whether the optimization problem is infeasible.

What Farkas' lemma has promised you is that if you can find such a $y$ such that $A^Ty \ge 0$ and $y^Tb <0$, then you have proven that the set is empty. Farkas lemma has promised us the existence of a certificate $y$ to show that the set is empty.

$\endgroup$
  • $\begingroup$ Thanks. That sounds useful. Do solvers return a certificate $y$ in cases where the feasible set is empty? And if so, does it give you any other information over and above the fact that the feasible set is empty? Also, is it computationally as easy to search for $y$ as it is to search for $x$? $\endgroup$ – ted Mar 1 '18 at 7:09
  • $\begingroup$ I can't speak for all solvers, but Cplex does. Looking for $y$ is just another linear programming problem where the feasible region is a subset of $\mathbb{R}^m$. $\endgroup$ – Siong Thye Goh Mar 1 '18 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.