# Strong Duality

Last time we showed that $\max \{\boldsymbol{c^T}\boldsymbol{x} : A\boldsymbol{x}\leq\boldsymbol{b}, x\geq 0\} \leq \min \{\boldsymbol{b^T}\boldsymbol{y} : A^{T}\boldsymbol{y}\geq\boldsymbol{c}, y\geq 0\}$, also known as the Weak Duality Theorem.

Let’s now take a look at other standard forms for LPs. Last time we worked mostly with $\max \boldsymbol{c^{T}x}$ $s.t.$ $A\boldsymbol{x} \leq \boldsymbol{b}$ $\boldsymbol{x} \geq 0$

We have already seen that we can switch the objective between minimizing a function or maximizing a function by taking the negative of the original objective. Now we want to show that the following two forms are equally as expressive, $\max \boldsymbol{c^{T}x}$ $s.t.$ $A\boldsymbol{x} = \boldsymbol{b}$ $\boldsymbol{x} \geq 0$ $\max \boldsymbol{c^{T}x}$ $s.t.$ $A\boldsymbol{x} \leq \boldsymbol{b}$

We can transform an inequality constraint of the form $\boldsymbol{a}\cdot\boldsymbol{x} \leq b$ into an equality constraint by adding a nonnegative slack variable such that $\boldsymbol{a} \cdot \boldsymbol{x} + s = b,\ s \geq 0$. An equality constraint $\boldsymbol{a}\cdot\boldsymbol{x} = b$ can easily be transformed into inequality constraints, $\boldsymbol{a}\cdot\boldsymbol{x} \leq b$ and $-\boldsymbol{a}\cdot\boldsymbol{x} \leq -b$.

The nonnegativity constraints can be imposed as follows. For each original variable $x$, we have two variables $\boldsymbol{x_1, x_2}$ such that $\boldsymbol{x} = \boldsymbol{x_1} - \boldsymbol{x_2}$. So constraint $\boldsymbol{a}\cdot\boldsymbol{x} \leq b$ would be replaced with $\boldsymbol{a}\cdot(\boldsymbol{x_1}-\boldsymbol{x_2}) \leq b$ and nonnegativity constraints $\boldsymbol{x_1, x_2} \geq 0$.

Let’s now look at prelationships between a primal LP that we will call $(P)$ and its dual $(D)$.

Theorem 1. (Strong Duality)
Given a primal LP $(P)$ and its dual $(D)$, one of the following four possibilities must hold:

1. $(P)$ Infeasible; $(D)$ Unbounded
2. $(P)$ Unbounded; $(D)$ Infeasible
3. $(P)$ Infeasible; $(D)$ Infeasible
4. $(P)$ Bounded & Feasible; $(D)$ Bounded & Feasible with equal optimal values

Proof.
We can rule out the following three possibilities using Weak Duality,

5. $(P)$ Unbounded; $(D)$ Unbounded
6. $(P)$ Unbounded; $(D)$ Bounded & Feasible
7. $(P)$ Bounded & Feasible; $(D)$ Unbounded

Let’s turn our attention to ruling out

8. $(P)$ Bounded & Feasible; $(D)$ Infeasible

and by duality,

9. $(P)$ Infeasible; $(D)$ Bounded & Feasible

We will need the following lemma

Lemma 1. (Farkas’ Lemma)
For any $A \in \mathbb{R}^{m \times n},\ \boldsymbol{b} \in \mathbb{R}^m$, exactly one of the following holds:

(1) $\exists \boldsymbol{x} : \boldsymbol{x}\geq 0,\ A\boldsymbol{x} = \boldsymbol{b}$
(2) $\exists \boldsymbol{y} : A^{T}\boldsymbol{y} \geq 0,\ \boldsymbol{b^T}\boldsymbol{y} < 0$

Proof.
(1) says that $\boldsymbol{b} \in C = cone\{\boldsymbol{a^{(1)}} ... \boldsymbol{a^{(n)}}\}$. If $\boldsymbol{b}$ is not, then there exists a hyperplane that separates $\boldsymbol{b}$ from $C$. We can take this hyperplane to be passing through $\boldsymbol{0}$, with normal $\boldsymbol{y}$. (2) then follows. $\square$

We now use Farkas’ Lemma to prove Strong Duality.

Let primal $(P)$ be the following feasible and bounded LP, $\max \boldsymbol{c^{T}x}$ $s.t.$ $A\boldsymbol{x} = \boldsymbol{b}$ $\boldsymbol{x} \geq 0$

and the dual $(D)$ is $\min \boldsymbol{b^{T}y}$ $s.t.$ $A^{T}\boldsymbol{y} \geq \boldsymbol{c}$

and $z > OPT(P)$. Now consider the matrix $\begin{pmatrix} A \\ \boldsymbol{c^T} \end{pmatrix}$ and vector $\begin{pmatrix} \boldsymbol{b} \\ z \end{pmatrix}$.

Apply Farkas’ Lemma, so either

(1) $\exists \boldsymbol{x}\geq 0 : A\boldsymbol{x} = \boldsymbol{b},\ \boldsymbol{c^{T}x} = z$ — this cannot hold since we assumed $\boldsymbol{c}^Tx
or
(2) $\exists (\boldsymbol{y}, \alpha) : A^T\boldsymbol{y}+\alpha {\bf c}\ge 0, \boldsymbol{b^{T}y} + \alpha z <0$. Multiplying the first with ${\bf x}^T$, and using $Ax=b$, we get ${\bf b}^Ty + \alpha {\bf c}^T x \ge 0$. Comparing the two inequalities with ${\bf b}^Ty$ and using our assumption that ${\bf c}^T x < z$, we conclude that $\alpha < 0$.  Hence, $\boldsymbol{b^T}(\frac{-\boldsymbol{y}}{\alpha}) < z$ $A^{T}(\frac{-\boldsymbol{y}}{\alpha}) \geq \boldsymbol{c}$

which gives us a feasible dual $(-{\bf y}/\alpha)$!

Moreover, this gives us $OPT(P) \leq \boldsymbol{b^T}(\frac{-\boldsymbol{y}}{\alpha}) < z$. Since $z$ is an arbitrary value greater than $OPT(P)$, we know that there exists a feasible dual with $OPT(P) = OPT(D)$. $\square$