| Prev | Next | Top | DualIneq |
A \in \R^{m \times n}
,
b \in \R^m
, and
c \in \R^n
,
the corresponding primal problem is
\[
\begin{array}{ll}
{\rm maximize} & c^T x \; {\rm with \; respect \; to} \; x \in \R_+^n
\\
{\rm subject \; to} & A x \leq b
\end{array}
\]
The extended primal objective function
f : \R_+^n \rightarrow \R \cup \{ - \infty \}
is defined by
\[
f(x) = \left\{ \begin{array}{ll}
c^T x & {\rm if} \; b - A x \geq 0 \\
- \infty & {\rm otherwise}
\end{array} \right.
\]
Solving the primal problem is equivalent to finding
an argument
x
that maximizes the value of
f(x)
with respect to
x \in \R_+^n
.
L : \R_+^n \times \R_+^m \rightarrow \R
is defined by
\[
\begin{array}{rcl}
L(x, y)
& = & c^T x + y^T ( b - A x )
\\
& = & b^T y + x^T ( c - A^T y )
\end{array}
\]
It follows that
\[
f(x) = \inf \; L(x, y) \; {\rm with \; respect \; to} \; y \in \R_+^m
\]
g : \R_+^m \rightarrow \R \cup \{ + \infty \}
is defined by
\[
g(y) = \sup \; L(x, y) \; {\rm with \; respect \; to} \; x \in \R_+^n
\]
It follows that
\[
g(y) = \left\{ \begin{array}{ll}
b^T y & {\rm if} \; c - A^T y \leq 0 \\
+ \infty & {\rm otherwise}
\end{array} \right.
\]
The dual problem is to find an argument value
y
that minimizes
g(y)
with respect to
y \in \R_+^m
.
This is equivalent to the following problem:
\[
\begin{array}{ll}
{\rm minimize} & b^T y \; {\rm with \; respect \; to} \; y \in \R_+^m
\\
{\rm subject \; to} & A^T y \geq c
\end{array}
\]
\hat{x} \in \R_+^n
and
\hat{y} \in \R_+^m
,
the corresponding duality gap is
g( \hat{y} ) - f( \hat{x} )
.
The duality gap is always non-negative and if it is zero,
\hat{x}
solves the primal problem
and
\hat{y}
solves the dual problem.
\[
\begin{array}{rcl}
g( \hat{y} )
& = &
\sup L( x , \hat{y} ) \; {\rm with \; respect \; to} \; x \in \R_+^n
\\
& \geq &
L( \hat{x} , \hat{y} )
\\
& \geq &
\inf \; L( \hat{x} , y ) \; {\rm with \; respect \; to} \; y \in \R_+^m
\\
& = &
f( \hat{x} )
\end{array}
\]
Thus we conclude that the duality gap is non-negative.
Further if it equals zero then for all
x \in \R_+^n
and
y \in \R_+^m
\[
\begin{array}{rcccl}
g( y ) & \geq & f( \hat{x} ) & = & g( \hat{y} )
\\
f( \hat{x} ) & = & g( \hat{y} ) & \geq & f( x )
\end{array}
\]
which completes the proof of the lemma.