3
$\begingroup$

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me.

The proof I am following is in this paper at page 16.

What I do not understand is:

(1) how the system $S_1$ and $S_2$ are formulated in relation to the ones in the Farkas alternative lemma;

(2) in the following proof, Farkas lemma is applied yielding the solution vector $x^i$ but the statement is obtained from the vector $\overline{x}$. Why are we allowed to take the sum of the $x_i's$ and use the result?

Tucker's theorem:

Let $M$ be any $R^{n×n}$ skew-symmetric matrix (i.e. $L^T = −L$).

The set of solutions

$S := \{x ∈ R^n |\ Mx \succeq 0, x \succeq 0\}$

always has a non-degenerate solution of the system, i.e. a solution $\overline{x} ∈ S$ s.t. for each component $i = 1, . . . , n$ either $( M\overline{x} )_i\succ0 $ or $\overline{x}_i\succeq 0$ $ $ holds (i.e. each component satisfies at least one inequality strictly). Formally: $∃\overline{x} ∈ S$ s.t.: $\overline{x}+ M\overline{x} \succ 0$.

Proof:

Let $L$ be an arbitrary skew-symmmetric matrix, of order $n$; let $e ^i$ be the $i_{th}$ unit coordinate vector and $I$ the identity matrix of order $n$: By Farkas lemma, either the system $$S_1=\{-L^Tx \succeq\underline{0} ,\ Ix \succeq \underline{0} ,\ (-e^i)^Tx < 0\}$$

has a solution, or the system

$$\{S_2= Lv-Iz = e^i,\ v\succeq 0 ,\ z\succeq 0\}$$

has a solution $y$, with $y^T = (v^T; z^T)$ but never both.

In the first case, taking into account the equality $L^T= -L$, we have a solution $x ^i$ of $S_1$ for which $\{Lx^i \succeq\underline{0} , x^i \succeq\underline{0} , x^i_i>0\}$.

In the second case, we have a vector $v^i$ for which $\{Lv^i \succeq e^i, v^i \succeq\underline{0}\}$.

Therefore, in either case there exists a vector $x^i$ for which $Lxi + xi \succeq\underline{0}$ and the $i_th$ component of the vector on the left-hand side is positive. Thus, for the vector

$$\overline{x}:=\sum_{i=1}^nx^i$$

it holds that: $$L\overline{x}+ \overline{x}\succ \underline{0}.$$

I hope my questions were clear enough.

$\endgroup$
1
$\begingroup$

Below is a rewording of the argument that's hopefully more transparent than the one in the paper. I'll use the symbols $\ge $ and $>$ for componentwise inequality. Recall that Farkas' lemma may be stated as follows:

Suppose that $A$ is an $m\times n$ matrix, and that $b \in \mathbb{R}^m$. Then either there is some $x\ge 0$ such that $Ax = b$, or there is some $p$ such that $p^\top A \ge 0$ and $p^\top b <0$.

If $L$ is a $k\times k$ matrix, choose $A$ to the be $k\times 2k$ matrix $A=[\,\,-L \,\,|\,\, I\,\,]$, and take $b = -e_1$ for specificity. Then Farkas' lemma tells us that exactly one of the following situations holds:

(a) There is some $x\ge 0$ such that $[\,\,-L \,\,|\,\, I\,\,] \,x = b$. In this case, write $x$ as a concatenation of its first $k$ coordinates and last $k$ coordinates, $x = (v,z)$. Notice that $v, z \ge 0$ since $x\ge 0$, and that we have $-Lv + Iz = -e_1 \iff Lv -z = e_1 \iff Lv = e_1 + z$. This last expression shows us that $Lv > 0$, and adding this to $v\ge 0$, we obtain $Lv+v >0$. So $v$ is our desired vector.

(b) There is some $p$ such that $p^\top [\,\,-L \,\,|\,\, I\,\,]\ge 0$ and $p^\top (-e_1) < 0$. Rewrite the constraints to give $[-p^\top L \,\,|\,\, p^\top\,\,] \ge 0$ and $p_1 >0$. Using skew-symmetry, the first constraint holds iff $Lp \ge 0$ and $p\ge 0$. Now, the constraints $p\ge 0$ and $p_1 >0$ imply that $p >0$, so adding inequalities, we see that $Lp + p>0$, and thus $p$ is our desired vector.

In either case, there's a vector $w\ge 0$ such that $Lw \ge 0$ and $Lw+w >0$, so we're done.

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