Let A be a $m \times n$ matrix, $\mathbf{c}$ an $n$-dimensional ector and $\mathbf{b} \ge \mathbf{0}$ an $m$-dimensional vector. Show that exactly one of the following two systems has a solution: $\begin{align*} 1. \ Ax \le z, \mathbf{c}^tx \gt \mathbf{d}^tz, x \ge \mathbf{0}, z \le \mathbf{0}, x \in \mathbb{R}^n, z\in \mathbb{R}^m \end{align*}$ $\begin{align*} 2. \ A^t y \ge c \, , y\ge \mathbf{d} \, , y\in \mathbb{R}^m \end{align*}$ I usually put here what I've done so far, but in this case I only know what I should do instead of some concrete calculations.

That statement above looks pretty similar to Farka's lemma, and I've seen some corollaries that are consequences of Farka's lemma whose proofs consist in some modifications on the matrix of the formulation of Faka's lemma. However, I don't know how I should modify the matrix so the exercise follows. Any help will be highly appreciate and thanks in advance!

By the way, I don't know if the tags are accurate so feel free to edit them.


We can rewrite (2) as $By \leq a$, where $$ B = \begin{bmatrix} -A^t \\ -I \end{bmatrix} \text{ and } a = \begin{bmatrix} -c \\ -d \end{bmatrix} $$

By this question, this system has a solution if and only if $y \geq 0, y^t B = 0, y^t a < 0$ has no solution $y$. So now, we just need to show that this system is equivalent to (1).

If we let $y = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}$ and expand the definition of $A$ and $b$, then the system looks like this:

$$ y_1 \geq 0, y_2 \geq 0, \qquad y_1^t (-A^t) + y_2^t (-I) = 0, \qquad y_1^t (-c) + y_2^t (-d) < 0 $$

We can simplify this to: $$ y_1, y_2 \geq 0, \qquad A y_1 + y_2 = 0, \qquad c^t y_1 + d^t y_2 > 0 $$ Now, if we replace $y_1$ by $x$ and $y_2$ by $-z$, we get (1)!

  • $\begingroup$ You are completely right! It should be $z \le 0$. I've changed that already. Thank you very much! $\endgroup$ – user313212 Jun 7 '16 at 21:53
  • $\begingroup$ That's encouraging to hear! I'll edit out my remark $\endgroup$ – dankness Jun 7 '16 at 21:58

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.