Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible:

Question

Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible:

1. $Ax\geq0,x\geq0,c^Tx>0$
2. $A^Ty\geq c,y\leq0$

Assume that A is feasible meaning $Ax\geq0,x\geq0,c^tx<0$ we'll show that B is not feasible.

$$A^Ty\geq c\iff x^TA^Ty\geq x^Tc\iff(Ax)^Ty\geq c^Tx>0$$ because $Ax\geq0$ we get that $y>0$ and therefore B is not feasible.(not sure if this true or not)

for the second side I got stuck.

Answer 1

Here is a solution using LP duality. Consider the following primal dual problems:

\begin{align} &\textbf{PRIMAL} \\ \underset{x\in \mathbb{R}^{n}}{\max{}} & c^\top x \\ \mbox{s.t.} & Ax \geq 0 \\ &x \geq 0 \end{align}

\begin{align} &\textbf{DUAL} \\ \underset{y\in \mathbb{R}^{n}}{\min{}} & 0 \\ \mbox{s.t.} & A^\top y \geq c \\ &y \leq 0 \end{align}

You can verify that the 2 LPs shown above indeed form a primal-dual pair. Now suppose the PRIMAL problem has a feasible solution, say $\bar{x}$, and suppose $c^\top \bar{x} > 0$, then DUAL must be infeasible. This is because, the optimal value of the dual problem is 0 assuming that the dual is feasible. So if both the PRIMAL and DUAL were feasible and $c^\top \bar{x} > 0$, then we will violate the Weak LP duality rule that the optimal value of the PRIMAL can be no greater than the optimal value of the DUAL. So this proves the first part of the question.

Now assume that the DUAL is feasible, so the optimal value of the DUAL is 0. Once again by weak duality recall that the optimal value of the PRIMAL cannot exceed 0. That means there is no $x$ feasible to the PRIMAL (i.e. the constraints $Ax \geq 0, x \geq 0$) such that $c^\top x > 0$ (since $c^\top x$ is the objective of the PRIMAL). This completes the proof of the second part.

Answer 2

Assume that A is feasible we'll show that B is not feasible.

$A^Ty\geq c\iff x^TA^Ty\geq x^Tc\iff(Ax)^Ty\geq c^Tx>0\to (Ax)^Ty>0$ but $Ax\geq0$ therefore $y$ must satisfy that $y>0$ and B is not feasible.
Assume that B is feasible and we will show that A is not feasible
$Ax\geq0\iff y^TAx\leq 0\iff(A^Ty)^Tx\leq0\iff c^Tx\leq(A^Ty)^Tx\leq 0\to c^Tx\leq 0$ and A is not feasible. as desired.
Correct if I am wrong