In this blog, we will show the power of LP problem and duality in mathematics. In this series of blog, we focus on the method that how to solve LP problem. But a “good” math can interacts to other branches of math. We gonna show how LP can be a tool to prove Farkas’ Lemma, which is the base of Convex Optimization.

Farkas’ Lemma

In this blog, we will show that infeasibility of a given system of linear inequalities is equivalent to the feasibility of another, related, system of linear inequalities.

Given an $m \times n$ matrix $A$ and a vector $b \in \mathbb{R}^m$, consider the systems of linear inequalities

\[\begin{equation} (*) \begin{cases} A\bar{x} = \bar{b} \\ \bar{x} \geq \bar{0} \end{cases} \quad and \quad (\star) \begin{cases} \bar{p}^\top A \geq \bar{0}^\top \\ \bar{p}^\top \bar{b} < 0 \end{cases} \end{equation}\]

Suppose ($\star$) is feasible, i.e., $\exists \bar{p}^* \in \mathbb{R}^m$ satisfying $(\bar{p}^*)^\top A \geq \bar{0}^\top$ and $(\bar{p}^*)^\top \bar{b} < 0$. Then, $\forall \bar{x} \geq \bar{0}$, we have $(\bar{p}^*)^\top A\bar{x} \geq 0 > (\bar{p}^*)^\top \bar{b}$.

It follows that, $\forall \bar{x} \geq \bar{0}$, we have $A\bar{x} \neq \bar{b}$, otherwise $(\bar{p}^*)^\top A\bar{x} = (\bar{p}^*)^\top \bar{b}$. Therefore ($*$) is infeasible.

Theorem Farkas’ Lemma Given an $m \times n$ matrix $A$ and a vector $b \in \mathbb{R}^m$, exactly one of the following two alternatives holds:

(a) $\exists \bar{x} \in \mathbb{R}^n$ satisfying $A\bar{x} = \bar{b}$ and $\bar{x} \geq \bar{0}$

(b) $\exists \bar{p} \in \mathbb{R}^m$ satisfying $\bar{p}^\top A = \bar{0}^\top$ and $\bar{p}^\top \bar{b} < 0$.

Proof.

(a) true ⇒ (b) false: Suppose $\exists \bar{x} \in \mathbb{R}^n$ s.t. $A\bar{x} = \bar{b}$ and $\bar{x} \geq \bar{0}$. Then, $\forall \bar{p} \in \mathbb{R}^m$ satisfying $\bar{p}^\top A \geq \bar{0}^\top$, we obtain

\[\bar{p}^\top \bar{b} = \bar{p}^\top (A\bar{x}) = (\bar{p}^\top A)\bar{x} \geq 0\]

(a) false ⇒ (b) true: Suppose there exists no vector $\bar{x}$ satisfying $A\bar{x} = \bar{b}$ and $\bar{x} \geq \bar{0}$. Consider the problem

\[\begin{equation} (\star) \quad \begin{aligned} \text{min} \quad & \bar{p}^\top \bar{b} \\ \text{s.t.} \quad & \bar{p}^\top A \geq \bar{0}^\top \\ & \bar{p} \text{ free} \end{aligned} \end{equation}\]

and its dual

\[\begin{equation} (*) \quad \begin{aligned} \text{min} \quad & \bar{0}^\top \bar{x} \\ \text{s.t.} \quad & \bar{x} \geq \bar{0} \\ & A \bar{x} = \bar{b} \end{aligned} \end{equation}\]

By assumption, $(*)$ is infeasible. Therefore, $(\star)$ is either unbounded with $-\infty$ as optimal cost or infeasible (by the duality theorem). However $\bar{p} = \bar{0}$ is clearly a feasible solution of $(\star)$. Hence $(\star)$is unbounded with $-\infty$ as optimal cost. Therefore, $\exists \bar{p}$ such that $\bar{p}^\top A = \bar{0}^\top$ and $\bar{p}^\top \bar{b} < 0$. $\square$

Geometric interpretation of Farkas’ Lemma

Think of the $n$ columns of the matrix $A$ as a family of vectors $\bar{A}_1, \bar{A}_2, \cdots , \bar{A}_n$.

EITHER $\bar{b}$ is in the convex cone spanned by the columns of $ A $ (i.e., $\bar{b}$ is a linear combination of $\bar{A}_1, \bar{A}_2, \cdots , \bar{A}_n$ with nonnegative coefficients). (That is $A\bar{x}=\bar{b}$ with $\bar{x}\geq \bar{0}$)

OR There exists a hyperplane $ H $ separating $ \bar{b} $ from the convex cone spanned by the columns of $ A $. (Think of the vector $ \bar{p} $ as a nonzero vector normal to the separating hyperplane. So $\bar{p} A \geq \bar{0}^\top $ that means $\bar{p}$ has a sharp angle to all the $\bar{A}_1, \bar{A}_2, \cdots , \bar{A}_n$. And $\bar{p}^\top \bar{b} < 0$, which means $\bar{b}$ lives in other side of hyperplane.)

linear inequalities

Theorem

Let $A$ be an $m \times n$ matrix.

Let $\bar{b}$ be a vector in $\mathbb{R}^m$.

Let $\bar{c}$ be a vector in $\mathbb{R}^n$.

Let $d$ be a scalar.

Suppose $A\bar{x} \leq \bar{b}$ has at least one solution. Then the following assertions are equivalent:

1. Every feasible solution of $A\bar{x} \leq \bar{b}$ satisfies $\bar{c}^\top \bar{x} \leq d$.
2. There exists $\bar{p} \geq 0$ such that $\bar{p}^\top A = \bar{c}^\top$ and $\bar{p}^\top \bar{b} \leq d$.

Note! The geometric interpretation of above theorem is: 1) the cost of optimal (max) solution of $A\bar{x} \leq \bar{b}$ will not greater than $d$. 2) At optimal solution point, the cost vector is in the convex cone spanned by the columns of $A$, and the cost of this point is not greater than $d$.

Proof. Consider the problem

\[\begin{equation} (\star) \quad \begin{aligned} \text{min} \quad & \bar{p}^\top \bar{b} \\ \text{s.t.} \quad & \bar{p}^\top A = \bar{c}^\top \\ & \bar{p} \geq \bar{0} \end{aligned} \end{equation}\]

and its dual

\[\begin{equation} (*) \quad \begin{aligned} \text{min} \quad & \bar{c}^\top \bar{x} \\ \text{s.t.} \quad & \bar{x} \text{ free} \\ & A \bar{x} \leq\bar{b} \end{aligned} \end{equation}\]

$\Rightarrow$: If $A\bar{x} \leq \bar{b}$ has a feasible solution and every feasible solution of $A\bar{x} \leq \bar{b}$ satisfies $\bar{c}^\top \bar{x} \leq d$, then $d$ is an upper bound on the objective values of $(*)$, the problem $(*)$ has an optimal solution $\bar{x}^*$ and its optimal objective is bounded above by $d$.

By the strong duality theorem, the problem $(\star)$ also has an optimal solution $\bar{p}^*$ whose objective is bounded above by $d$. This optimal solution $\bar{p}^*$ satisfies $(\bar{p}^*)^\top A = \bar{c}^\top$, $\bar{p}^* \geq \bar{0}$, and $(\bar{p}^*)^ \top \bar{b} \leq d$.

$\Leftarrow$: If some vector $\bar{p}^*$ satisfies $(\bar{p}^*)^ \top A = \bar{c}^\top$, $\bar{p}^* \geq \bar{0}$, and $(\bar{p}^*)^ \top \bar{b} \leq d$, then the weak duality theorem asserts that every feasible solution $\bar{x}$ of $(*)$ must satisfy $\bar{c}^\top \bar{x} \leq (\bar{p}^*)^\top \bar{b} \leq d$. $\square$

Summary: In this part, we can see LP can be a powerful tool to prove other branches of math.