# Prove Non-Homogeneous Farkas' Lemma

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:

either
$$\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.

• Are there any additional constraints on $x$ and $y$? It would have also been nice, if you could mention the source for this formulation. – Konstantin Dec 24 '20 at 17:21
• 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" – convxy Dec 24 '20 at 18:50