2
$\begingroup$

I am trying to show that

$$Ax < b$$

Is feasible

iff

$$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

Work So Far

Now when I try to hit this with Gordan's Lemma I seem to get just short of proving it and I don't know how to go over the remaining gap.

Observe the bottom system can be written as

$$ G^T w =0, w \ge 0, w \ne 0, G^T = \begin{bmatrix} A^T & 0 \\ b^T & 1\end{bmatrix}, w = \begin{bmatrix} y \\ s \end{bmatrix} $$

So by Gordans Lemma either this is feasible or

$$ G \mu < 0, \mu = \begin{bmatrix} x \\ r \end{bmatrix} $$

Is feasible. This of course expands as

$$ \begin{bmatrix}A & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ r \end{bmatrix} < 0 \rightarrow \begin{matrix} Ax + br < 0 \\r < 0 \end{matrix} \iff \begin{matrix} Ax < bq \\ q > 0 \end{matrix} $$

So it is clear how to proceed in one direction

If $Ax < b$ then $\begin{matrix} Ax < bq \\ q > 0 \end{matrix}$ with $q=1$ that gives us $r=-1$ that solves $$\begin{bmatrix}A & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ r \end{bmatrix} < 0$$

And from Gordan's it follows that

$$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

But now suppose we assume that

$$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$

Is infeasible.

The furthest we can go is state $\exists q$ such that

$$\begin{matrix} Ax < bq \\ q > 0 \end{matrix}$$

But unless $q = 1$ we don't have

$$ Ax < b$$

And it isn't obvious that $q=1$ MUST be able to solve this.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.