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 <z$
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$

Like this:

Related