3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.