1

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?

Community
  • 1
James
  • 3,997

2 Answers2

2

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$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • So, to prove the converse: I would argue as follows: by contrapositive, if $Ax=b$ $x \geq 0$ has no solution, then the primal is unfeasible which means that the Dual is Infeasible or unbounded. However, it it not infeasible as $y=0$ satisfies $y^T A \leq 0$ trivially. So, this leaves the dual to be unbounded which means that $y$ can be anything and satisfies $y^T A \leq 0 $. IS this correct argument? – Mikey Spivak Nov 08 '18 at 06:25
  • I would phrase the last part as, we can find a feasible $y$ such that $y^TA \le 0$ and $y^Tb$ is positive since the dual is unbounded. – Siong Thye Goh Nov 08 '18 at 06:32
  • thanks so much! can you tell me if Im doing this problem correctly? https://math.stackexchange.com/questions/2989514/trying-to-set-up-a-linear-programming-problem – Mikey Spivak Nov 08 '18 at 06:36
1

The argument is incorrect. First of all your primal-dual pair is wrong (they are not duals). Secondly, if your dual was the right one, then 0 being optimal means that there is no $y$ for which $y^T b < 0$ (since then 0 would not be optimal).

LinAlg
  • 19,822
  • The primal dual pair is correct. I do not have enough points to downvote but I would downvote this response if I could. – tooAnnoying Aug 16 '21 at 02:20