# Mar 23. Linear Programming II

Consider the following standard form of an LP:

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

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

The decision problem associated with this LP is the following: does there exist an $x \ge 0$  such that $c^\top x > t$ and $Ax = b$. To certify a yes instance, we can simply give as our certificate a solution $x \ge 0$ such that $c^\top x > t$ and $Ax=b$. To certify a no instance we will use the dual LP. Recall the dual form of the above LP:

$\min{b^\top y}$

• $A^\top y \ge c$

Weak LP Duality: Let $OPT(P)$ denote the optimal value of the primal program and let $OPT(D)$ denote the optimal value of the dual program. We claim that $OPT(P) \le OPT(D)$ (if the optima exist).

Proof: Let $x$ be a feasible solution of the primal and let $y$ be a feasible solution to the dual. Then $c^\top x \le y^\top Ax = y^\top b$.

Farkas’ Lemma: Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$ then exactly one of the following holds:

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

Proof: Let $C_A = \{ Ax \mid x \ge 0\}$ be the cone generated by the columns of $A$. In other words if $\{a_1, \cdots, a_n\}$ are the columns of $A$, then $C_A = \{ \sum_{i=1}^n a_i x_i \mid x_i \ge 0\}$. Suppose there exists an $x \ge 0$ such that $Ax = b$, then clearly $b \in C_A$. Note that $C_A$ is a convex set – since if $x, y \in C_A$ then for any $1\ge \lambda \ge 0$, $\lambda x + (1-\lambda)y \in C_A$ since $\lambda, (1-\lambda) \ge 0$. From the homework, if $b \notin C_A$, then $\exists y, \alpha$ such that $y^\top b < \alpha$ and $Ay \ge \alpha \bf{1}$, where $\bf{1}$ is the all $1$‘s vector. Note that $\alpha$ cannot be positive. Suppose $\alpha < 0$. We may raise $\alpha$ till there must be some subset of columns of $A$ such that $y^\top A_{|S} = -\epsilon$ where $\epsilon > 0$. But then for a large enough $M > 0$, and scaling every column of $A_{|S}$ by $M$ we get $y^\top A_{|S} < \alpha$. This contradicts the fact that $y^\top x \ge \alpha$ for any $\alpha \in C_A$. Thus we may raise $\alpha$ till it is equal to $0$.

Strong LP Duality: If the primal and dual are feasible, then $OPT(P) = OPT(D)$.

Proof: Let $z = OPT(D)$. Suppose there exists an $x$ such that

• $Ax = b$
• $c^\top x = z$
• $x \ge 0$

In this case we would be done. Let $B^\top = [A^\top, c]$ and $d^\top = [b^\top, z]$. Then by Farkas’ lemma, either:

1. $\exists x\ge 0$ such that $Bx = d$, in which case we have an $x\ge 0$ such that $Ax = b$ and $c^\top x = OPT(D)$.
2. $\exists [y, \alpha]$ such that $A^\top y + \alpha c \ge 0$ and $b^\top y + \alpha z < 0$. In this case, choose a feasible $x$ for the primal program. Then $0 \le x^\top A^\top y + \alpha(x^\top c) = b^\top y + \alpha (x^\top c)$ which implies (if $\alpha \ge 0$) that $c^\top x > z$ which contradicts weak duality. If $\alpha < 0$ then $A^\top y \ge -\alpha c$ while $b^\top y < -\alpha z$ which implies $A^\top (-y)/\alpha \ge c$ while $b^\top (-y)/\alpha < z$. This contradicts optimality of $z$. Thus this option is not possible.