3
$\begingroup$

I have a question which I thought that can be solved by Farkas Lemma, but I could not manage it.

Prove that only one of the systems has a feasible solution, where $A$ is an $m \times n$ matrix, $C$ is a $r \times n$ matrix:

System 1.

\begin{align*} A\mathbf{x} &\leq \mathbf{b} \\ C\mathbf{x} & > \mathbf{d} \\ \mathbf{x} &\geq 0 \end{align*}

System 2. \begin{align*} \mathbf{y}^T A &\geq \mathbf{s}^T C \\ \mathbf{y}^T \mathbf{b} &= \mathbf{s}^T\mathbf{d} \\ \sum_{k=1}^r s_k &= 1 \\ \mathbf{y}, \mathbf{s} &\geq 0 \end{align*}

$\endgroup$
0
$\begingroup$

Using a trick on P.6 of L. Vandenberghe's notes.

System 1 is equivalent to

\begin{align} \exists t &\ge 1 \text{ s.t. } \\ A\mathbf{x} &\leq \mathbf{b} \\ C\mathbf{x} &\ge \mathbf{d} + \frac1t\sum_{k=1}^r {\bf e}_k \\ \mathbf{x} &\geq 0 \end{align}

$\forall k \in \{1,\dots,r\}, {\bf e}_k$ is a standard unit vector. Let ${\bf u} = t{\bf x}$. Write the above system into the canonical form.

\begin{align} \exists t &\ge 1 \text{ s.t. } \\ A\mathbf{u} &\le t\mathbf{b} \\ -C\mathbf{u} &\le -t\mathbf{d} - \sum_{k=1}^r {\bf e}_k \\ \mathbf{u} &\geq 0 \end{align}

Add slack variables ${\bf s}_1, {\bf s}_2$.

\begin{align} & \exists t \ge 1 \text{ s.t. } \\ & \begin{bmatrix} A & I_m & 0 \\ -C & 0 & I_r \end{bmatrix} \begin{bmatrix} {\bf u} \\ {\bf s}_1 \\ {\bf s}_2 \end{bmatrix} = \begin{bmatrix} t\mathbf{b} \\ -t\mathbf{d} - \sum\limits_{k=1}^r {\bf e}_k \end{bmatrix} \tag1\label1 \\ & \mathbf{u},{\bf s}_1, {\bf s}_2 \geq 0 \end{align}

To make life easier, let's consider a variant of Farkas' Lemma.

A variant of Farkas' lemma

Let $A$ be $m \times n$ matrix and $b \in \mathbb{R}^m$ $m$-dimensional vector. Then, exactly one of the following holds:

  1. there exists some $x \in \mathbb{R}^n$, $x \geq 0$, such that $Ax = b$
  2. there exists some vector $y \in \mathbb{R}^m$ such that $y^TA \geq 0$ and $y ^Tb = -1$.

From Farkas' lemma, either \eqref{1} or \eqref{2} has a solution.

\begin{align} & \exists t \ge 1 \exists {\bf y} \in \Bbb R^m \exists {\bf s} \in \Bbb R^r \text{ s.t. } \\ & \begin{bmatrix} {\bf y} \\ {\bf s} \end{bmatrix}^T \begin{bmatrix} A & I_m & 0 \\ -C & 0 & I_r \end{bmatrix} \ge {\bf 0} \tag2\label2 \\ & \begin{bmatrix} {\bf y} \\ {\bf s} \end{bmatrix}^T \begin{bmatrix} t\mathbf{b} \\ -t\mathbf{d} - \sum\limits_{k=1}^r {\bf e}_k \end{bmatrix} = -1 \\ & \mathbf{u},{\bf s}_1, {\bf s}_2 \geq 0 \end{align}

From the inequality in \eqref{2}, we immediately have

\begin{align} \mathbf{y}^T A &\geq \mathbf{s}^T C \\ \mathbf{y}, \mathbf{s} &\geq 0 \end{align}

From the equality in \eqref{2}, we have

\begin{align} t{\bf y}^T {\bf b} - {\bf s}^T \left( t{\bf d} + \sum\limits_{k=1}^r {\bf e}_k \right) &= -1 \quad \forall t \ge 1 \quad \text{(to be justified below)}\\ t({\bf y}^T {\bf b} - {\bf s}^T {\bf d}) - \sum\limits_{k=1}^r s_k &= -1 \tag#\label# \\ {\bf y}^T {\bf b} - {\bf s}^T {\bf d} - \frac1t \sum\limits_{k=1}^r s_k &= -\frac1t. \end{align}

As $t \to +\infty$, ${\bf y}^T {\bf b} = {\bf s}^T {\bf d}$, which is OP's system 2's second constraint. Substitute this equality to \eqref{#} to get $\sum\limits_{k=1}^r s_k = 1$.

Justification for taking $t \to +\infty$

  • If system 1 is infeasible, $\forall t \ge 1$, \eqref{1} doesn't hold.
  • For each $t \ge 1$, apply Farka's lemma to conclude that \eqref{2} has a solution.
  • Since \eqref{2} is solvable for all $t \ge 1$, equation \eqref{#} derived from \eqref{2} holds for all $t \ge 1$.

We finally get OP's system 2.

\begin{align} \mathbf{y}^T A &\geq \mathbf{s}^T C \\ \mathbf{y}^T \mathbf{b} &= \mathbf{s}^T\mathbf{d} \\ \sum_{k=1}^r s_k &= 1 \\ \mathbf{y}, \mathbf{s} &\geq 0 \end{align}

Note that the steps above can be reversed: if we assume the feasibility of OP's system 2, we have \eqref{#} without the need to take limits. Thus, \eqref{2} is equivalent to system 2.

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