<<

. 44
( 59 .)



>>


whence x : ln 10. This is in agreement with the solution of the constrained
problem given by (12) with z : 0.

Example 3.2. Find the point in the half space de¬ned by x ; x - z that is
 
closest to the origin. This problem has a solution. (Why?)
We may formulate this problem analytically as follows: Minimize #x#
subject to x ; x - z. Thus the problem is a problem of type CPII(z). If we
 
take z : 0, we see that CPII is strongly consistent. On sketching the feasible
sets for z . 0, it becomes clear that for z . 0 the solution is the origin and that
(z) : 0. For z : 0 the minimum is the point of intersection of the line x : x
 
and the line x ; x : z. Thus the minimum is achieved at (z, z) and

 
(z) : z for z : 0. The function is differentiable at all points and (0) : 0.

Therefore 0 is the unique Kuhn”Tucker vector, and the constrained problem
CPII can be replaced by the problem of minimizing #x#. The conditions of
Theorem 2.5 are clearly satis¬ed if we take x : (0, 0) and : 0.
* *
PERTURBATION THEORY 199


We may also formulate the problem analytically as follows: Minimize #x#
subject to x ; x - z. Again, the solution is the origin if z . 0 and the point
 
(z, z) if z : 0. The function is now given by (z) : 0 for z . 0 and

(z) : 9z/(2 for z : 0. Thus, is not differentiable at the origin. It is a
straightforward calculation to show that * (0) is the interval [91/(2, 0].
Hence by Theorem 3.2 the Kuhn”Tucker vectors and multiplier vectors are all
points in the interval [0, 1/(2]. We now verify this assertion independently.
For to be a Kuhn”Tucker vector, we must have

inf+#x# ; (x ; x ), : 0.
 
When x : 0, the quantity in brackets is clearly zero. Therefore, for to be a
Kuhn”Tucker vector, we require that . 0 and

(x ; x ; (x ; x ) . 0 for all x + RL.
   
To see what requirement this places on , we introduce polar coordinates. The
preceding inequality is then satis¬ed at the origin and whenever

(cos  ; sin  ) . 91, 0-  -2 . (14)

The function (  ) : cos  ; sin  achieve its minimum on the interval [0, 2 ]
at  : 5 /4 and the value of the minimum is 9(2. Hence we must have
- 1/(2 as well as . 0.
We can replace the constrained problem by the unconstrained problem.

min+#x# ; (x ; x ),,
 
where is any point in [0, 1/(2]. The preferred choice of is clearly : 0.
We leave it to the reader to verify that any in [0, 1/(2] will serve as a
multiplier as in Theorem 2.2.
*
Example 3.2 furnishes another illustration of the advantage of minimizing
the square of the distance rather than the distance itself.

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

g (x) : x 9 x - z .
g (x) : x - z ,

     
When z : 0, the problem reduces to the problem considered in Example 2.1.
We saw there that when z : 0, there exists no Kuhn”Tucker vector. By draw-
ing an appropriate ¬gure, the reader can see that dom( ) : +z : z ; z . 0,
 
and that (z) :9(z ; z . We leave the proof of this assertion as an exercise.
 
Thus neither 0 nor any point on the line z ; z : 0 are interior to dom( ).
 
It is easy to verify that * (z) : ` at each z on the boundary of dom( ).
200 CONVEX PROGRAMMING AND DUALITY


The next example has discontinuous value function at the origin.


Example 3.4. Minimize e\V‚ subject to (x ; x 9 x - z. For z : 0, the
  
feasible set is +x : (x , x ) : x . 0, x : 0,. The minimum is attained at each
  
point of the feasible set since e\V‚ : e\ : 1. Hence (0) : 1. If z : 0, the
feasible set X(z) is empty. If z 9 0, points x of the feasible set satisfy

x - 2x z ; z.
 

Thus the feasible set is the set of points on and ˜˜inside™™ the parabola x :

2x z ; z. This parabola is symmetric with respect to the x -axis, has vertex
 
at (9 z, 0), and opens to the right. Hence inf+e\V‚ : x + X(z), : 0, and so

(z) : 0 for z 9 0. Thus, dom( ) : [0, -), and is discontinuous at z : 0.
Also, * (0) : `. Note that if z 9 0, then the in¬mum is never attained at any
point of X(z). Thus the problem CP(z) has no solution if z 9 0.

Exercise 3.1. Prove the assertions in Example 3.3 that

(i) dom( ) : +z : z ; z . 0,,
 
(ii) (z) : 9(z ; z , and
 
(iii) * (z) : ` at each z on the boundary of dom( ).

, dom( ), and * (0) if it
Exercise 3.2. In each of the following problems ¬nd
is not empty:

(i) Minimize e\V subject to 9x - 0.
(ii) Minimize x subject to x ; x : 1.
 

(iii) Minimize x ; x ; 2x ; 2x subject to x ; x . 2.
     
(iv) Minimize x subject to e\V 9 x - 0.
 

Exercise 3.3. Show directly that there are no Kuhn”Tucker vectors for the
problem with z : 0 in Example 3.4.


4. LAGRANGIAN DUALITY

If CPII has a solution and is strongly consistent, then Theorem 2.4 suggests a
method for computing the value of the minimum. Let

Y : + : : ( , ) : + RK, . 0, + RI,, (1)

LAGRANGIAN DUALITY 201


+ Y let
and for each

 ( ) : inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x + RL,. (2)

Let
: sup+  ( ) : + Y ,. (3)

Then by Theorem 2.4, : , where

: inf+ f (x) : g(x) - 0, h(x) : 0,. (4)

A possible procedure for ¬nding x , a point at which the minimum is achieved,
*
is to ¬rst ¬nd all solutions to the equation f (x ) : and then retain those
*
solutions that satisfy the constraints.
This discussion suggests that it might be fruitful to consider the following
problem, which we call the problem dual to CPII, or simply the dual problem,
and denote by DCPII.

Problem DCPII
Let
Y : + : + Y ,  ( ) 9 9-,, (5)

where Y is de¬ned in (1) and  ( ) in (2). Then

Maximize +  ( ) : + Y ,.

Note that in formulating the dual problem it is not assumed that CPII has
a solution or is strongly consistent. The set Y is the feasible set for DCPII. If
Y "`, then the dual problem is said to be consistent. The original problem
CPII is often referred to as the primal problem.
The next theorem indicates how the dual problem gives information about
the primal problem and vice-versa.

T 4.1 (L§®§©® Dµ¬© T ¦ C® P§©®§).

(i) If X " ` and Y "`, then for each x + X and +Y

 ( ) - f (x). (6)

Moreover, if and are as in (3) and (4), then both are ¬nite and - .

(ii) L et Y "`. If  ( ) is unbounded above on Y, then X : `.
(iii) L et X " `. If f (x) is unbounded below on X, then Y : `.
(iv) If there exists an + Y and an x in X such that f (x ) :  ( ), then
* * * *
:  ( ) : f (x ) : .
* *
T hus x is a solution of CPII and is a solution of DCPII.
* *
202 CONVEX PROGRAMMING AND DUALITY


Proof. The key to the proof of the theorem is the observation that since
. 0 for + Y and since g(x) - 0 and h(x) : 0 for x + X, it follows that for
x + X and + Y,

f (x) ; 1 , g(x)2 ; 1 , h(x)2 - f (x). (7)

In (2) we take the in¬mum over all x in RL. This in¬mum is less than the
in¬mum in (2) taken over all x + X. From these observations and from (7) the
inequalities (6) and - follow. Assertion (ii) follows from (6), for if X were
not empty, then  ( ) would be bounded above. Also, (iii) follows from (6) by
a similar argument. Statement (iv) follows from the chain

 ( *) - - - f (x *) :  ( *).
We now see how the dual problem gives useful information about the primal
problem and vice-versa. Statement (i) shows how a feasible point for the dual
problem gives a lower bound for the value of the primal problem and how a
feasible point for the primal problem gives an upper bound for the value of the
dual problem. Statement (ii) gives a way of checking whether X : ` in the
absence of more direct checks. Statement (iii) gives a condition under which
the dual problem cannot be formulated.

De¬nition 4.1. Problems CPII and DCPII are said to exhibit a duality gap if
:.

The next theorem gives a suf¬cient condition for the absence of a duality
: ( , ) to the solutions of the dual
gap and relates the multipliers
* **
problem.

T 4.2. L et the primal problem CPII be strongly consistent and have a
solution. T hen:

(i) T here is no duality gap.
(ii) If : ( , ) is a multiplier for CPII, then is a solution of the dual
* ** *
problem.
(iii) If : ( , ) is a solution of the dual problem, then is a multiplier
  
vector for the primal problem.

Proof. Let x denote the point at which CPII achieves its minimum. Since
*
the problem is strongly consistent by Theorem 2.2, there exists a multiplier
: ( , ) for CPII. Thus,
vector
* **
f (x ) - f (x) ; 1 , g(x)2 ; 1 , h(x)2 (8)
* * *
for all x in RL. Hence, from (2),  ( ) . f (x ). By Theorem 4.1,  ( ) - f (x ),
* * * *
so  ( ) : f (x ). Conclusions (i) and (ii) now follow from (iv) of Theorem 4.1.
* *
LAGRANGIAN DUALITY 203


: ( , ) be a solution of the dual problem. From (2) and from
Now let
 
the absence of a duality gap we get that

inf+ f (x) ; 1 , g(x)2 ; 1 , h(x)2 : x + RL, :  ( ) : f (x ).
   *
Thus ( , ) is a Kuhn”Tucker vector, and so by Theorem 2.3, ( , ) is a
 
multiplier vector for the primal problem.

We now present several examples to illustrate the theory developed in this
section.

Example 4.1. We take the primal problem to be the problem in Exercise IV.5.5
or the problem in Example 3.1 with z : 0. The primal problem is

Minimize f (x) : e\ V>V‚
subject to eV ; eV‚ - 20.
Let

<<

. 44
( 59 .)



>>