[Math] Farkas Lemma Question with strict inequality

linear programmingmatricesproof-explanation

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*}

Best Answer

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.

Related Question