To Prove: $Ax =b, x \geq 0$, $ x\in \mathbb{R}^n$ has solution $\iff$ there is no $y \in \mathbb{R}^m$ (y is unrestricted in sign) such that $y^T A \leq 0 $ and $y^Tb > 0$.
Attempt.
We consider the following primal-dual
\begin{align*}
\max 0 x &&&&&&& \min y^Tb \\
Ax=b &&&&&&& y^TA\leq 0 \\
x \geq 0 &&&&&&& y \; \; \text{free}
\end{align*}
Suppose $Ax=b, x \geq 0$ has solution. Meaning primal is feasible so there must be an optimal solution, but since $0x = 0$, then $0$ must be the optimal. By duality then $0$ must be the optimal of Dual problem, which means that $y^Tb = 0$ so it is impossible to have $y$ with $y^Tb > 0$.
Conversely, suppose there is ${\bf no}$ $y$ so that $y^TA \leq 0 $ and $y^T b > 0$ so that for every $y'$ we have $y'^T A > 0$ or $y'^Tb \leq 0$ so that $y'^T b \leq 0 $ for every $y'$ gives that the objective dual is bounded. can we conclude here that there exists a solution? If so, then the primal has at least one $x$ feasible. Is this argument valid?
Best Answer
Guide:
Argue using the following primal-dual pair:
Primal: $$\min 0^Tx$$
subject to
$$Ax=b$$ $$x \ge 0$$
Dual:
$$\max b^Ty$$
subject to
$$y^TA \le 0^T$$