# Mar 11. Linear Programming

Consider a generic linear program:

$\max{c^\top x}$ s.t.

• $Ax \le b$
• $x\ge 0$

Note that we can write any linear program in this form. Suppose the $x \ge 0$ was absent. Then we could write $x = y - z$ where $y \ge 0, z \ge 0$ and this would make it an LP of the above form. Here are a few other forms of the LP that are equivalent:

$\max{c^\top x}$ s.t.

• $Ax = b$
• $x \ge 0$

We can write the first form by introducing a slack variable, i.e. $Ax \le b$ if and only if there exists $s \ge 0$ such that $Ax + s = b$. To write the second form in the first form we observe that $Ax = b$ if and only if $Ax \le b$ and $-Ax \le -b$.

Suppose we are given a linear program in the first form, i.e.

$\max{c^\top x}$ s.t.

• $Ax \le b$
• $x \ge 0$

We wish to find an upper bound for the maximum. Notice that for any $y \ge 0$ such that $y^\top A \ge c^\top$, $y^\top b$ is a valid upper bound for the maximum. Thus the best upper bound we can find is given by another LP called the dual of the first LP.

$\min{y^\top b}$ s.t.

• $y^\top A \ge c^\top$
• $y \ge 0$

The first LP is often called the primal and the second program is called the dual. Note that the dual of the dual is the primal program. Let $P$ be the primal optimal value and $D$ the dual optimal value. Then weak LP duality tells us that $P \le D$.

Strong LP Duality: For a primal and dual pair of LP programs, $P = D$. In other words

$\max\{c^\top \mid Ax \le b, x \ge 0\} = \min\{b^\top \mid A^\top y \ge c, y \ge 0\}$.

To prove this we will introduce the following simple lemma.

Farkas Lemma: Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^n$. Then exactly one of the following is true:

1. $x \ge 0$ such that $Ax = b$
2. $y$ such that $b^\top y < 0$ and $A^\top y > 0$

Let $a_1, \cdots, a_n$ be the columns of $A$. Then the first condition is equivalent to saying that the vector $b$ belongs to the cone generated by the columns of $A$. Notice that the cone generated by the set of vectors $\{a_1, \cdots, a_n\}$ is given by $C = \{ \sum_i a_i x_i \mid x_i \ge 0\}$. The second condition merely says that if $b \notin C$ (i.e. the first condition does not hold) then one can find a hyperplane $H$ going through the origin such that $H$ separates $b$ from the cone. The hyperplane is given by $\{x \mid y^\top x = 0\}$. Since $y^\top a_i > 0$ for every $a_i$ it follows that for every element $x\in C$ satisfies $y^\top x \ge 0$. However $y^\top b < 0$ thus separating it.