# #* *

*

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