2014年5月1日星期四

有关Farkas Lemma的证明

Question: The system Ax<0 is unsolvable if and only if the system yA=0, y>=0 and y!=0 is solvable.

Proof: Construct the prime dual problems
Prime:
max s                         min 0
st. Ax+s<=0     ==> st. Ay=0
                                   1*y=1
if dual problem is solvable, then by strong duality, the optimal value in prime is s=0, so Ax+0<=0, but Ax<0, so prime is unsolvable.