0

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.

user313212
  • 2,176

1 Answers1

2

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)!

Community
  • 1
dankness
  • 1,141