<<

. 39
( 59 .)



>>

h(x )z2.
# #* *
*
Since . 0, it follows that for any z satisfying the tangential constraints (4)
#
we have 1
f (x ), z2 . 0. Hence the condition 1
f (x ), z2 - 0 reduces to
* *
1
f (x ), z2 : 0.
*
If the inequality constraints are absent, then a vector z satis¬es the
tangential constraints at a point x if and only if
h(x )z : 0. Thus, if at a
 
point x the necessary conditions of Corollary 2 of Theorem 5.2 are satis¬ed,
*
the proof of Corollary 4 shows that for every vector z such that
h(x )z : 0
*
we have 1
f (x ), z2 : 0. Therefore the following corollary holds.
*
C¬¬ 5. L et (x , ) satisfy the necessary condition of Corollary 2 of
*
T heorem 5.2. Suppose that for every z such that
h(x )z : 0
*
1z, Hxx (x, )z2 9 0,

where

H(x, ) : f (x) ; 1 , h(x)2.

T he f attains a strict local minimum for the problem of minimizing f subject to
h(x) : 0.

There is a suf¬cient condition due to Pennisi [1953] which is not as
convenient to apply as Corollary 4 but is equivalent to it. We now state this
condition and prove its equivalence to Corollary 4.

C¬¬ 6. L et (x , , ) satisfy the KKT necessary conditions of T heorem
*
5.2. L et E* : +i : i + E and 9 0,. Suppose that for every z " 0 + RL that satis¬es
G
1
g (x ), z2 : 0, i + E*, 1
g (x ), z2 - 0, i + E, i , E*,
G* G*

h(x )z : 0, (19)
*
the inequality

1z, F (x , , )z2 9 0
VV *
holds, where F is as in (18). T hen f attains a strict local minimum for problem
PI at x .
*
Proof. To prove the corollary it suf¬ces to show that the set V of vectors

that satisfy (19) is the same as the set V of vectors that satisfy the tangential

176 OPTIMIZATION PROBLEMS


constraints (4) and the equality 1
f (x ), z2 : 0, and then invoke Corollary 4.
*
We ¬rst show that V 3 V . If V : `, there is nothing to prove, so we
  
assume that V " `. From (ii) of Theorem 5.2 we get that for z in RL

1
f (x ), z2 ; 1 ,
g(x )z2 ; 1 ,
h(x )z2 : 0. (20)
* * *
Now let z + V . Then
g (x )z - 0, and
h(x )z : 0. Thus z satis¬es the
 #* *
tangential constraints (4). Moreover, since : 0 for i + I, we have that : 0
G G
for i , E*. Thus (20) becomes

1
f (x ), z2 ;  1
g (x ), z2 : 0
* G G*
GZ#1
for all z in V . For such z and for i + E* we have 1
g (x), z2 : 0. Hence
 G
1
f (x ), z2 : 0, and so V 3 V .
*  
We now show that V 3 V . We assume that V " `. Since : 0 for i , E*
   G
and 1
f (x ), z2 : 0, it follows that, for z + V , (20) becomes
* 
 1
g (x ), z2 : 0.
G G*
GZ#1
Since for any vector z that satis¬es the tangential constraints (4) we have
1
g (x ), z2 - 0, and since 9 0 for i + E , the last equality implies that
G* G *
1
g (x ), z2 : 0 for i + E* Since
g (x )z - 0 for any vector satisfying the
G* #*
tangential constraints, we get that V 3 V .
 
Example 5.1 (Concluded). We now apply Corollary 4 to show that the points
given in relation (4) in Section 5 furnish local minima for problems when
I
0 : k : 1 and that the origin furnishes a local minimum for problems when
I
k 9 1.
for 0 : k : 1. At the point x :
We ¬rst consider the problem
I *
(1 9 k, (2k(1 9 k)), the condition 1
f (x ), z2 : 0 becomes
*

1%92k, 2(2k(1 9 k) &, (z , z )2 : 0.


At the point x : %1 9 k, 9(2k(1 9 k) & the condition 1
f (x ), z2 : 0 be-
* *
comes

1%92k, 92(2k(1 9 k) &, (z , z )2 : 0.

Thus at x and x we require that
* *


 
2(1 9 k) 2(1 9 k)
x :z :z x : z : 9z (21)
, .
*   *  
k k
SECOND-ORDER CONDITIONS 177


The tangential constraints at the points x and x become
* *

x : 1(2k, 92(2k(1 9 k)), (z , z )2 - 0,
* 
x : 1(2k, 2(2k(1 9 k)), (z , z )2 - 0
* 
or



 
2(1 9 k) 2(1 9 k)
x :z -z x : z - 9z .
,
*   *  
k k

Hence at x the vectors z : (z , z ) that satisfy (
f (x , z2 : 0 and the
*  *
tangential constraints are given in (21). Similarly, at x the vectors that satisfy
*
1
f (x ), z2 : 0 and the tangential constraints are given in (21). Since : 1 at
*
x and x , the function F in (18) becomes
* *
F : (x 9 1) ; x ; (2kx 9 x).
 
 
Thus

z
20
 : 2(z ).
1z, Fxx (x, 1, )z2 : (z , z ) (22)
00 
z

At x and at x vectors z " 0 at which (21) holds have z " 0. It therefore
* * 
follows that the hypotheses of Corollary 4 hold at x and x , and so both
* *
of these points furnish local minima. We leave it as an exercise to show that
these points furnish minima for problem , with 0 : k : 1.
I
We now consider the problem , k 9 1. The origin is the only point that
I
satis¬es the conditions of Theorem 5.2. Since
f (0) : (92, 0), all vectors z of
the form (0, z ), with z arbitrary, satisfy 1
f (0), z2 : 0. Since
g(0) : (2k, 0),
 
all vectors z of the form z : (z , z ), with z - 0, and z arbitrary, satisfy the
  
tangential constraint 1
g(0), z2 - 0. Hence the vectors that satisfy the tangen-
tial constraints and 1
f (0), z2 : 0 are vectors of the form (0, z ), where z is
 
arbitrary.
The function F with : 1/k becomes

2kx 9 x
.
F : (x 9 1) ; x ; 

 k

Thus (17) with z : (0, z ) becomes

2 0 0 1
(0, z ) :2 19 (z ) 9 0, z " 0.
 0 2(1 9 )  
z k
I 
Convexity and Optimization in n . Leonard D. Berkovitz
Copyright 2002 John Wiley & Sons, Inc.
ISBN: 0-471-35281-0




V
CONVEX PROGRAMMING
AND DUALITY


1. PROBLEM STATEMENT

In the preceding chapter we studied programming problems with differentiable
data. In this chapter we shall replace the assumption that the data are
differentiable by the assumption that the data are convex. This assumption will
enable us to obtain much more detailed information about the behavior of
solutions. In Section 1 of Chapter IV we de¬ned a convex programming problem
to be a programming problem in which the underlying set X is convex, the

functions f and g are convex, and there are no equality constraints.

Convex Programming Problem I (CPI)
Let X be a convex set and let f : X ; R and g: X ; RK be convex.
  
Minimize + f (x) : x + X,,

where

X : +x : g(x) - 0,.

The problem is often stated as

Minimize f (x) subject to g(x) - 0.

Remark 1.1. A convex programming problem with the additional equality
constraint h(x) : 0 can be cast in the format CPI if the function h is af¬ne. One
replaces the constraint h(x) : 0 by the two inequality constraints h(x) - 0 and

<<

. 39
( 59 .)



>>