Proving Strong Duality with Simplex

Consider the primal program $P$

$\max c^T x$
$Ax \leq b$
$x \geq 0$

and the dual $D$

$\min b^T y$
$A^T y \geq c$
$y \geq 0$

where $\max c^T x \leq \min b^T y$ .

We will once again prove strong duality, but this time using the simplex algorithm.

Let $z^* = c^T x^*$ be an optimal, bounded primal solution. Add slack variables $x_{n+1} ... x_m$ such that

$\max z = \sum_{i=1}^{n} c_i x_i$
$\sum_{j=1}^{n} a_{ij}x_{j} + x_{n+i} = b_i$
$x_1 ... x_{m+n} \geq 0$

So, at the end of our simplex algorithm, we reach

$z = z^* + \sum_{j=1}^{n+m} \bar{c}_j x_j$
$\bar{c}_i \leq 0$

Let $y^*_i = -\bar{c}_{n+i}$

We will show that

(1) $z^* = b^T y^*$
(2) $A^T y^* \geq c$

Proof.

We will first prove (1).

$z = z^* + \sum_{j=1}^n \bar{c}_j x_j - \sum_{i=1}^m y^*_i x_{n+i}$
$= z^* + \sum_{j=1}^n \bar{c}_j x_j - \sum_{i=1}^m y^*_i b_i + \sum_{i=1}^m y^*_i (\sum_j a_{ij}x_j)$
$= z^* - \sum_{i=1}^m y^*_i b_i + \sum_{j=1}^n (\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i)x_j$

holds for all $x$ . So $x = 0 \implies z = 0 \implies z^* = b^T y^*$ .

Now we show (2). We are left with

$z = \sum_{j=1}^n (\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i)x_j = \sum_{j=1}^n c_j x_j$

which holds for all $x$ . So,

$\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i = c_j$
$\bar{c}_j \leq 0$

$\implies A^T y^* \geq c$

At the optimal solution we get

$z = z^* + \sum_{j=1}^n \bar{c}_j x^*_j - \sum_{i=1}^m y^*_i x_{n+i}^*$

with the second and third terms equal to $0$ ,

$\implies x^*_j > 0 \implies \bar{c}_j = 0$
$\implies y^*_i > 0 \implies x^*_{n+i} = b_i - \sum_{j=1}^n a_{ij}x^*_j = 0$

This is what is referred to as “complementary slackness”.

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Connecting to %s

%d bloggers like this: