Let $A\in\mathbb{R}^{m \times n}, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}, d\in\mathbb{R}$. Suppose that there exists $y\geq0$ such that $A^Ty=c$.

Question: prove that exactly one of the following is feasible:

$$\begin{cases}A x&\leq b\\ c^T x &>d \end{cases} \tag{A}$$ or
$$ \begin{cases} A^T y & = c \\ b^T y &< d. \end{cases} \tag{B}$$

My attempt is the following.

I'm not sure about the way I solve the second part where B doesn't hold.

  1. Assume that B holds and we'll show that A doesn't.

$$Ax\leq b\iff y^T Ax\leq y^T b\iff (A^Ty)^Tx\leq d\iff c^Tx\leq d$$

and therefore A doesn't hold.

  1. Now, assume the contrary, that B doesn't hold and we'll show that A is feasible.

If B doesn't holds then $A^Ty=c,b^Ty=d$ doesn't hold either. Introduce

$$\tilde{A}:=\begin{pmatrix} A^T\\b^T \end{pmatrix},\quad \tilde{c}:=\begin{pmatrix} c\\d \end{pmatrix}.$$

Now from the homogenous Farkas' lemma we know that

$$\tilde{A}\tilde{x}\leq 0,\tilde{c}^T \tilde x>0\iff Ax+x_{n+1}b\leq0,c^Tx+dx_{n+1}>0$$

and setting $x_{n+1}=-1$ we get $Ax\leq b,c^Tx >d$ as desired.

  • $\begingroup$ Are there any additional constraints on $x$ and $y$? It would have also been nice, if you could mention the source for this formulation. $\endgroup$
    – Konstantin
    Dec 24 '20 at 17:21
  • $\begingroup$ It's from a course that I do right now and I'm not sure if the book is on the internet "introduction to nonlinear optimization by amir beck" $\endgroup$
    – convxy
    Dec 24 '20 at 18:50

Your Answer

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

Browse other questions tagged or ask your own question.