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”.

Advertisements

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

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

Facebook photo

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

Connecting to %s