Question

Use Farka's Lemma directly to prove that, if p* is finite, then PS has a feasible solution.

Answer 1

Use Farka's Lemma directly to prove that, if $p^*$ is finite, then $PS$ has a feasible solution.

Solution.

Farkas' Lemma: precisely one of the following is true:

a. there is $x \geq 0$ such that $Ax = b$;

b. there is $y$ such that $A^T y \geq 0$ and $b^T y \leq 0$.

So consider the system of inequalities given in block-matrix form by

$$\left[ \begin{array}{cc} -A^T & c \\ 0^T & 1 \end{array} \right] \left[ \begin{array}{c} r \\ \alpha \end{array} \right] \geq \left[ \begin{array}{c} 0 \\ 0 \end{array} \right]$$

and

$$\left[ \begin{array}{cc} -b^T & p^* \end{array} \right] \left[ \begin{array}{c} r \\ \alpha \end{array} \right] < 0$$

Here $r$ is a column vector and $\alpha$ is a real number.

By Farkas' Lemma, there must be $\tilde{x} \geq 0$ and $\beta \geq 0$ such that $A\tilde{x} = b$ and $c^T\tilde{x} = p^* - \beta \leq p^*$. It follows that $\tilde{x}$ is optimal (feasible solution where the objective function reaches its maximum or minimum) for $PS$ and $c^T\tilde{x} = p^*$.