<<

. 45
( 59 .)



>>

L (x, ) : e\ V>V‚ ; (eV  ; eV‚ 9 20).

Then for each . 0 de¬ne

 ( ) : inf+L (x, ) : x + R,.

The dual problem is to maximize  ( ).
We saw in Example 3.1 that the primal problem is strongly consistent and
that it has a solution at x : ( , ), where : ln 10. The value of the minimum
*
is 10\ and the value of the multiplier is 10\. Thus we would expect the
*
value of the maximum of  to be 10\ and for  to assume this value at
: 10\. We now show that this is indeed so.

We ¬rst determine the function  . For each . 0, the function L ( , ) is
readily seen to be a strictly convex function of x. Hence a necessary and
suf¬cient condition that L ( , ) attain a unique minimum at : ( , ) is that

*L /*x and *L /*x both equal zero at . As in Example 3.1 we see that for
 
" 0 this implies that : . Denoting this common value by , we get that
 

 ( ) : inf+
( , ) : + R,, (9)

where


( , ) : e\K ; 2 (eK 9 10).

For ¬xed positive ,
( , ) is a strictly convex function of . A necessary and
suf¬cient condition that
( , ) attain a unique minimum at a point is that

204 CONVEX PROGRAMMING AND DUALITY


d
/d vanish at . Now


d

: 92e\K ; 2 eK.
d

Setting d
/d : 0, we get that exp(9 ) : . Substituting this into (9) gives


 ( ) : 3  9 20 , 9 0.

Since  ( ) : 0 when : 0, the preceding formula is valid for all . 0. An
elementary calculus argument shows that  is maximized at the unique point
at which  ( ) : 0. This value of is readily seen to be 10\ and the
corresponding value of  is 10\. These values are as required.

Example 4.2. Let the primal problem be as follows: Minimize #x# subject to
x ; x - 0. This problem was analyzed in Example 3.2 with z : 0. This
 
problem is strongly consistent and has x : 0 as its solution. The value of the
minimum is clearly zero. Any in the interval [0, 1/(2] is a multiplier vector.
The dual problem is as follows: Maximize +  ( ) : . 0,  ( ) 9 9-,, where
 ( ) : inf+#x#; (x  ; x) : x + R,. We introduce polar coordinates (r,
) and
obtain

 ( ) : inf+r(1 ; (cos
; sin
)) : r . 0, 0 -
- 2 ,.
Let
(
, ) : 1 ; (cos
; sin
).

Then  ( ) : 0 if (
, ) . 0 for all 0 -
- 2 , and  ( ) : 9- if this is not so
and r " 0. The argument used in Example 3.2 shows that (
, ) . 0 for all

in [0, 2 ] if and only if 0 - - 1/(2. Thus  ( ) : 0 for in [0, 1/(2] and
 ( ):9- otherwise. Hence max+  ( ) : + Y ,:0 and the maximum is attained
at each + [0, 1/(2]. Comparison with the solution to the primal problem
shows that there is no duality gap and the points at which the dual problem
attains its maximum are the multipliers for the primal problem.

Example 4.3. Let the primal problem be the problem treated in Example 2.1
and in Example 3.3 with z : 0. The primal problem has the origin as the only
feasible point. This point furnishes the solution and the value of the minimum
is zero. This problem is clearly not strongly consistent.
The dual problem is as follows: Maximize +  ( ) : + Y ,, where

 ( ) : inf(x  ; x ; (x 9 x) : x + R,.
Y : + : . 0,  ( ) 9 9-, and

LAGRANGIAN DUALITY 205


If we write

x ; x ; (x 9 x ) : x ; x ; ( 9 )x ,
 
     
" , then  ( ) : 9-. For " 0 with :
we see that if , we have
   
" 0 and


 ( ) : inf+x ; x : x + R,.

The function inside the curly brackets attains its minimum at x : 91/2 and
 

 ( ) : 91/4 . (10)
: 0 we have
For

 (0) : 9-.

Thus Y : + : ( , ) : : , 9 0,. Since 9 0, it follows from (10) that
   
sup+  ( ) : + Y , : 0. The supremum is not attained in the dual problem, even
though there is no duality gap. Thus we have an example in which there is no
duality gap; the primal problem has a solution but the dual problem has no
solution. We also recall from Example 3.3 that * (0) :
and there are no
Kuhn”Tucker vectors.

Example 4.4. In this example we will exhibit a duality gap. Let the primal
problem be the problem in Example 3.4 with z : 0. We saw there that the
minimum is attained at every point of the feasible set and that the value of the
minimum is 1.
The dual problem is to maximize +  ( ) : . 0,  ( ) 9 9-,, where

 ( ) : inf+e\V‚ ; ((x ; x 9 x) : x + R,.
 
Let

L (x, ) : e\V‚ ; ((x ; x 9 x ).
  
Then L (x, ) . 0 for all x in R. We shall show that  ( ) : 0.
Let x 9 0 and let x 9 0. Then
 
x

L (x, ) : e\V‚ ;
(x ; x ; x
  
x

: e\V‚ ; .


x
1;  ;1
x
 x

206 CONVEX PROGRAMMING AND DUALITY


Now let x : (x ) and then let x ; -. We see that L (x, ) ; 0 along this
  
curve. Thus  ( ) : 0 for all . 0 and max+  ( ) : . 0, : 0. Thus : 0, and
since : 1, we have a duality gap.
Theorem 4.2 states that if a solution to the primal problem exists, then
strong consistency is a suf¬cient condition for the absence of a duality gap and
the existence of a solution to the dual problem. The following example shows
that strong consistency is not a necessary condition for the absence of a duality
gap and for the existence of a solution to the dual problem.

Example 4.5. Minimize f (x) : x subject to

g (x) : (x ; 1) ; (x ) 9 1 - 0, g (x) : 9x - 0.
    
The problem is clearly a convex programming problem. The feasible set
consists of the origin 0 in R, and the problem is not strongly consistent. The
solution to the primal problem is x : 0 and : 0.
*
The dual objective function is given by

 ( ) : inf+x ; [(x  ; 1) ; (x ) 9 1] 9 x : x + R,,

where . 0. If we take : : (0, 1) we get that  ( ) : 0. If then follows
* *
from (iv) of Theorem 4.1 that there is no duality gap and that is a solution
*
of the dual problem.

We will now obtain two necessary and suf¬cient conditions for the absence
of a duality gap and the existence of a solution to the dual problem.

T 4.3. L et problem CPII have a solution x . T hen a necessary and
*
suf¬cient condition for the absence of a duality gap and for : ( , ), . 0,
***
*
to be a solution of the dual problem is that (x , , ) is a saddle point for L .
***
Proof. Let (x , , ) be a saddle point for L . Then (2.18i) and (2.19) of
***
Theorem 2.7 hold. Thus (8) of Theorem 4.2 holds. That there is no duality gap
and that ( , ) is a solution to the dual problem follows by the same
**
arguments used to establish (i) and (ii) in Theorem 4.2.
: ( , ) be a solution of the dual problem and let there be no
Now let
* **
duality gap. Then, as in the proof of statement (iii) in Theorem 4.2 with
: and : , we get that ( , ) is a multiplier as in Theorem 2.2 for
  **
* *
the primal problem. But (7) of Theorem 2.2 states that (x , , ) is a saddle
***
point for L .

T 4.4. L et CPII have a solution x . T hen a necessary and suf¬cient
*
condition for the absence of a duality gap and the existence of a solution to the
dual problem is that * (0) " `. In this event every vector in 9* (0) is a
solution of the dual problem.
GEOMETRIC INTERPRETATION 207


Proof. We ¬rst prove the suf¬ciency of the condition * (0) " `. Since the
primal problem has a solution, (0) is ¬nite. By hypothesis, * (0) " `. Hence
by Lemma 3.3 each vector : ( , ) such that 9 + * (0) is a Kuhn”Tucker
vector, and such vectors exist. By Theorem 3.3 each such vector is in M, the
set of multiplier vectors, as in Theorem 2.2. Thus (x , , ) is a saddle point
*
for L , and so by Theorem 4.3 there is no duality gap and ( , ) is a solution
to the dual problem. Now suppose that there is no duality gap and that the
: ( , ). Then by Theorem 4.3 the point
dual problem has a solution
* **
(x , , ) is a saddle point for L . By Theorem 2.7, ( , ) is a Kuhn”Tucker
*** **
vector. It then follows from Theorem 3.3 that ( , ) + 9* (0).
**
C¬¬ 1. L et CPII have a solution x . T hen a necessary and suf¬cient
*
condition for the absence of a duality gap and the existence of a solution to the
dual problem is that one of the sets * (0), K, or M be nonempty.

The corollary is an immediate consequence of Theorems 4.4 and 3.3.

Remark 4.1. In Remark 3.4 we indicated an economic interpretation of the
multiplier vectors as equilibrium prices. In view of the preceding corollary, we
see that the solution of the dual problem gives the equilibrium price.

Exercise 4.1. Formulate, and solve whenever possible, the problems dual to the
problems in Exercise 3.2. Discuss your results as they relate to Theorem 4.2.

Exercise 4.2. The problem posed in Exercise IV.5.8 is a convex programming
problem. Solve this problem by formulating the dual and solving the dual.
Hint: To simplify the algebra involved, ¬rst solve the problem for x : 0. Then

use a translation of coordinates to obtain the result for general x .

Exercise 4.3. Show that the function  de¬ned by (2.2) is concave.


5. GEOMETRIC INTERPRETATION

<<

. 45
( 59 .)



>>