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

Advertisements