Dual Linear Program

I was asked to construct dual linear program to prove the following statement: $S_1=\{A^Ty\leq0, b^Ty>0\}$ is nonempty iff $S_2=\{Ax=b,x\geq0\}$ is empty.

I'm trying to begin with $$\min_{A^Ty\geq0} b^Ty$$ and its dual $$\max_{x\geq0, Ax=b} c^Tx$$ with $c=0$ but stuck after that.

Any help would be greatly appreciated!

Solution 1:

This is what's known as a "theorem of the alternative". We can show it using a powerful tool for LPs, strong duality.

From the primal LP $$ \max_x \;\{c^\top x : Ax=b,\,x\geq0\}\tag{$P$} $$ we can find the dual (which we will call $(D)$) by $(i)$ replacing the constraints with appropriate penalization and $(ii)$ using the minmax inequality (aka weak duality) $$ (P) \overset{(i)}{\equiv} \max_{x\geq0}\big\{\min_y \{c^\top x + y^\top(b-Ax)\}\big\} \overset{(ii)}{\leq} \min_y\max_{x\geq0} c^\top x + y^\top(b-Ax) =\begin{cases}-\infty,\quad&\text{if $Ax\neq b$}\\\min_y\{b^\top y : A^\top y\geq c\},\quad&\text{o.w.}\end{cases} \equiv (D). $$ By strong duality, we know that the optimal values $\nu(P)$ and $\nu(D)$ are equal if both programs are feasible.

Returning to the question, let $S_2 = \{x:Ax=b,x\geq0\}$, $S_1=\{y:A^\top y\geq0,b^\top y>0\}$ and $c=0$. We can make the following argument to show that $S_1\neq\emptyset \iff S_2=\emptyset$.

$(\impliedby)$: If $S_2=\emptyset$, then problem $(P)$ is infeasible. By strong duality, the dual of $(P)$ (i.e., problem $(D)$) is unbounded or infeasible. Since $y=0$ is always feasible for $(D)$, then we must have that $\nu(D)=+\infty$ and hence there exists a feasible $y$ with $b^\top y>0$.

$(\implies)$: We will consider the contrapositive. If $S_2\neq\emptyset$, then $(P)$ is feasible and has optimal value $\nu(P)=0$. By strong duality, since $(D)$ is always feasible from $y=0$, we have that $\nu(P)=\nu(D)=0$. Hence there cannot be a feasible $y$ that attains a strictly better objective value than zero, meaning that $S_1=\emptyset$.