$\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

1 Answer

$\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$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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