| Prev | Next | Top | CompSlack |
A \in \R^{m \times n}
,
b \in \R^m
,
and
c \in \R^n
define the
primal problem
with extended objective
f(x)
and the
dual problem
with extended objective
g(y)
.
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
satisfy the complementary slackness condition if the following conditions
hold:
for
i = 1 , \ldots , m
,
and
j = 1 , \ldots , n
\[
\begin{array}{rcl}
0 & = & \left( b_i \; - \; \sum_{k=1}^n A_{i,k} \hat{x}_k \right) \hat{y}_i
\\
0 & = & \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \; - \; c_j \right) \hat{x}_j
\end{array}
\]
\hat{x} \in \R_+^n
is feasible for the primal problem,
\hat{y} \in \R_+^m
is feasible for the dual problem,
and they satisfy the complementary slackness condition.
It follows that the corresponding
duality gap
is zero.
\[
\begin{array}{rcl}
b_i \hat{y}_i & = & \hat{y}_i \left( \sum_{k=1}^n A_{i,k} \hat{x}_k \right)
\\
c_j \hat{x}_j & = & \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \right) \hat{x}_j
\end{array}
\]
The vector
\hat{x} \in \R_+^n
is feasible for the primal problem
and
\hat{y} \in \R_+^m
is feasible for the dual problem.
Hence,
\[
\begin{array}{rcl}
g(\hat{y}) & = &
\sum_{i=1}^m \hat{y}_i \left( \sum_{k=1}^n A_{i,k} \hat{x}_k \right)
\\
f(\hat{x}) & = &
\sum_{j=1}^n \left( \sum_{k=1}^m \hat{y}_k A_{k,j} \right) \hat{x}_j
\end{array}
\]
Rearranging the indexing we conclude that
\[
\begin{array}{rcl}
g(\hat{y})
= \sum_{i=1}^m \sum_{j=1}^n \hat{y}_i A_{i,j} \hat{x}_j
= f(\hat{x})
\end{array}
\]
It follows from the
and
\hat{y}
solves the dual problem.
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
are such that the corresponding
duality gap
is zero.
It follows that they satisfy the complementary slackness condition.
g(y)
are plus infinity
and the only infinite values for
f(x)
are minus infinity.
Thus, the duality gap being zero implies that
\hat{x} \in \R_+^n
is primal feasible,
\hat{y} \in \R_+^m is dual feasible
, and
\[
\sum_{j=1}^n c_j \hat{x}_j = \sum_{i=1}^m b_i \hat{y}_i
\]
We now suppose that the first complementary condition is false; i.e.,
there is an index
I
such that
\[
0 \neq \left( b_I \; - \; \sum_{j=1}^n A_{I,j} \hat{x}_j \right) \hat{y}_I
\]
It follows from the fact that
\hat{x}
is feasible
and
\hat{y} \in \R_+^m
that
\[
\begin{array}{rcl}
0
& < & \left( b_I \; - \; \sum_{j=1}^n A_{I,j} \hat{x}_j \right) \hat{y}_I
\\
b_I \hat{y}_I
& > & \sum_{j=1}^n \hat{y}_I A_{I,j} \hat{x}_j
\\
\sum_{i=1}^m b_i \hat{y}_i
& > & \sum_{i=1}^m \sum_{j=1}^n \hat{y}_i A_{i,j} \hat{x}_j
\\
& > & \sum_{j=1}^n \hat{x}_j \sum_{i=1}^m \hat{y}_i A_{i,j}
\end{array}
\]
We now apply the fact that
\hat{y}
is feasible to conclude that
\[
\sum_{i=1}^m b_i \hat{y}_i > \sum_{j=1}^n \hat{x}_j c_j
\]
Which contradicts the fact that the duality gap is zero.
Thus the first complementary condition must be satisfied for all indices.
We now suppose that the second complementary condition is false; i.e.,
there is an index
J
such that
\[
0 \neq \left( \sum_{i=1}^n \hat{y}_i A_{i,J} \; - \; c_J \right) \hat{x}_J
\]
It follows from the fact that
\hat{y}
is feasible
and
\hat{x} \in \R_+^n
that
\[
\begin{array}{rcl}
0
& < & \left( \sum_{i=1}^n \hat{y}_i A_{i,J} \; - \; c_J \right) \hat{x}_J
\\
c_J \hat{x}_J
& < & \sum_{i=1}^m \hat{y}_i A_{i,J} \hat{x}_J
\\
\sum_{j=1}^n c_j \hat{x}_j
& < & \sum_{j=1}^n \sum_{i=1}^m \hat{y}_i A_{i,j} \hat{x}_j
\\
& < & \sum_{i=1}^m \hat{y}_i \sum_{j=1}^n A_{i,j} \hat{x}_j
\end{array}
\]
We now apply the fact that
\hat{x}
is feasible to conclude that
\[
\sum_{j=1}^n c_j \hat{x}_j
<
\sum_{i=1}^m \hat{y}_i b_i
\]
Which contradicts the fact that the duality gap is zero.
Thus the second complementary condition must be satisfied for all indices.
This completes the proof.