# How does this list of optimal values prove Farkas' lemma?

From Convex Optimization:

Can someone explain how the proof below shows that $$5.87$$ and $$5.88$$ are strong alternatives?

It seems to just list the optimal values of $$5.89$$ and $$5.90$$ depending on the feasibility of $$5.87$$ and $$5.88$$ and claim that they're equal because of this list.

Is there a feasibility relationship between a linear program and it's dual that would suggest that exactly one of $$5.87$$ and $$5.88$$ is feasible? ## 1 Answer

Is there a feasibility relationship between a linear program and it's dual

Yes, if the primal is infeasible, the dual is infeasible or unbounded. If the primal is unbounded, the dual is infeasible. You can switch primal and dual in these statements. These statements follow from the weak duality theorem.

The two lines of reasoning here are:

1. If the dual is feasible, the dual has optimal value 0, and therefore the primal also has optimal value 0 (by strong duality), and therefore you cannot have $$x$$ such that $$c^Tx < 0$$, $$Ax \leq 0$$.

2. If there is an $$x$$ for which $$c^Tx < 0$$ and $$Ax \leq 0$$, then the primal problem is unbounded (fill in $$tx$$ and let $$t\to\infty$$), therefore the dual is infeasible.