If x " 0, then we must have : 1, and so

x : 1 9 k, x : <(2k(1 9 k), 0 : k : 1.

If x : 0, then from the second equation in (3) we get that x : 0, and

consequently : 1/k.

In summary, we have shown that if 0 : k : 1, then the only points

x : (x , x ) and multipliers (1, ) that satisfy the necessary conditions for

problem are

I

: 1, x :19k x : <(2k(1 9 k) , (4)

1

: x :0 x : 0. (5)

k

150 OPTIMIZATION PROBLEMS

If k . 1, the necessary conditions are only satis¬ed by (5). Note that if k : 1,

then (4) and (5) both give : 1 and x : x : 0.

We emphasize that Theorem 5.1 is a necessary condition, so that without

further arguments we cannot determine which, if any, of the points (4) and (5)

furnish a minimum In the problem we are minimizing the distance from the

I

point (1, 0) to the closed set X . By Lemma II.3.3 a solution to this problem

I

exists. Since for k . 1 the only point that satis¬es the necessary conditions is

for k . 1. If we denote the

the origin, this point is the solution to problem

I

two points in (4) by x and x , then

f (x ) : f (x ) : 9k ; 2k.

The point in (5) is the origin, and f (0) : 1. Since 9k ; 2k : 1 for k " 1, a

for 0 : k : 1 is given by each of the points x and x .

solution to problem

I

Before we present our proof of Theorem 5.1, we shall present the principal

idea of a proof which, with variations, is popular in the literature. We suppose

that the equality constraints have been converted into inequality constraints,

h(x) - 0 and 9h(x) - 0, so that the only constraints are g(x) - 0. By a trans-

lation of coordinates, we can assume that x : 0 and that f (x ) : f (0) : 0.

* *

We also assume that

f (0) " 0.

As in the linear programming problem, let

E : +i : g (0) : 0,, I : +i : g (0) : 0,. (6)

G G

The constraints g (c) : 0 with i in E are said to be active or binding at 0; those

G

with i + I are said to be inactive at 0.

Since f and g are C, they are differentiable by Theorem I.11.2. Therefore,

since f (0) : 0 and g (0) : 0,

#

f (x) : 1

f (0), x2 ; o(#x#),

g (x) :

g (0)x ; o(#x#),

# #

where o(#x#) and o(#x#) represent terms such that o(#x#)/#x# ; 0 and o(#x#)/

#x# ; 0 as #x# ; 0. Thus, o(#x#) and o(#x#) represent higher order terms.

Since g is continuous and g (0) : 0, there exists a 9 0 such that g (x) : 0

' '

whenever #x# : . The origin is therefore a solution of the local problem:

Minimize f (x) subject to g (x) - 0 and #x# : . If we drop the terms o(#x#)

#

and o(#x#), that is, if we linearize the problem about the solution 0 and assume

that the problem is the linearized problem, then x : 0 is the solution of the

*

linear programming problem:

Minimize 1

f (0), x2 : 19(9

f (0)), x2,

subject to

g (0)x - 0, #x# : . (7)

#

DIFFERENTIABLE NONLINEAR PROGRAMMING PROBLEMS 151

By Remark 4.3, we can now apply Theorem 4.1 with A :

g (0) and

#

b : 9

f (0) to the linearized problem and obtain the existence of a vector

" 0 in RK# such that . 0 and

# #

R

g (0) : 9

f (0).

##

:( , 0 ), then . 0 and we can rewrite this equation as

If we now set

# '

f (0) ; R

g (0) ; 0R

g (0) :

f (0) ; R

g(0) : 0.

## ''

The rightmost equation is statement (iii) of Theorem 5.1 with : 1. (Recall

that we are taking all the constraints to be inequality constraints.) Since : 1,

( , ) " 0. Also

1 , g(0)2 : 1( , 0 ), (g (0), g (0))2 : 0,

# ' # '

which is (ii). Note that if the linearization is valid, then we can get a set of

multipliers ( , ) with : 1.

To complete the proof, one must show that the terms o(#x#) and o(#x#) can

indeed be neglected. That is, it must be shown that if the terms represented by

o(#x#) and o(#x#) are absent, then 0 is a solution of (7). This part of the proof

becomes quite technical and is carried out in different ways by different authors

depending on the additional assumptions that are made. In Exercise 5.10 below

the reader will be asked to carry out one such proof, the original proof by

Kuhn and Tucker.

Our proof of Theorem 5.1, which we now present, will be a ˜˜penalty

function™™ proof and is due to McShane [1973].

Proof. As noted in the preceding discussion, we may assume that x : 0

*

and that f (x ) : 0.

*

Let E and I be as in (6). To simplify the notation, we assume that E : +1,

2, . . . , r, and that I : +r ; 1, . . . , m,. Since E or I can be empty, we have

0 - r - m.

Let be a function from (9-, -) to R such that (i) is strictly increasing

on (0, -), (ii) (u) : 0 for u - 0, (iii) is C, and (iv) (u) 9 0 for u 9 0. Note

that (u) 9 0 for u 9 0.

Since g is continuous and X is open, there exists an 9 0 such that

B(0, ) : X and g (x) : 0 for x + B(0, ).

'

De¬ne a penalty function F as follows:

P I

F(x, p) : f (x) ; #x# ; p (g (x)) ; [h (x)] , (8)

G G

G G

152 OPTIMIZATION PROBLEMS

where x + X and p is a positive integer. We assert that for each satisfying

0 : : , there exists a positive integer p( ) such that for x with #x# :

F(x, p( )) 9 0. (9)

We prove the assertion by assuming it to be false and arriving at a

contradiction. If the assertion were false, then there would exist an with

0 : : such that for each positive integer p there exists a point x with

N

#x # : and F(x , p) - 0. Hence, from (8)

N N

P I

f (x ) ; #x # - 9p (g (x )) ; [h (x )] . (10)

N N GN GN

G G

Since #x # : and since S(0, ) : +y : #y# : , is compact, there exist sub-

N

sequences, which we relabel as x and p, and a point x with #x # : such

N

that x ; x . Since f, g, and h are continuous,

N

f (x ) ; f (x ), g (x ) ; g (x ), h(x ) ; h(x ).

N #N # N

Therefore, if in (10) we divide through by 9p and then let p ; -, we get

P I

0. (g (x )) ; [h (x )] . 0.

G G

G G

Hence for each i : 1, . . . , r we have g (x ) - 0, and for each i : 1, . . . , k we

G

have h (x ) : 0. Since #x # : : , we have g (x ) : 0. Thus x is a feasible

G '

point and so

f (x ) . f (0) : 0. (11)

On the other hand, from (10) and from #x # : we get that f (x ) - 9( ),

N N

and so

f (x ) - 9( ) : 0,

which contradicts (11). This proves the assertion.

For each in (0, ) the function F( , p( )) is continuous on the closed ball

B(0, ). Since B(0, ) is compact, F( , p( )) attains its minimum on B(0, ) at

some point x with #x # - .

C C

Since F(x, p( )) 9 0 for x with #x# : , and since F(0, p( )) : f (0) : 0, it

follows that F( , p( )) attains its minimum on B(0, ) at an interior point x of

C

B(0, ). Hence,

*F

(x , p( )) : 0, j : 1, . . . , n.

*x C

H

DIFFERENTIABLE NONLINEAR PROGRAMMING PROBLEMS 153

Calculating *F/*x from (8) gives

H

*f P *g

G (x )

(x ) ; 2x ; p( ) (g (x ))

*x C CH G C *x C

H G H

I *h

; 2p( )h (x ) G (x ) : 0 for j : 1, . . . , n. (12)

G C *x C

G H

De¬ne

P I

L ( ) : 1 ; [ p( ) (g (x ))] ; [2p( )h (x )],

GC GC

G G

1

( ): ,

(L ( )

p( ) (g (x ))

GC,

( ): i : 1, . . . , r,

G (L ( )

( ) : 0, i : r ; 1, . . . , m,

G

2p( )h (x )

G C,

(): i : 1, . . . , k.

G (L ( )

Note that

(i) ( ) 9 0,

(ii) ( ) . 0, i : 1, . . . , r,

G (13)

(iii) ( ) : 0, i : r ; 1, . . . , m,

G

(iv) #( ( ), ( ), ( ))# : 1,

where ( ) : ( ( ), . . . , ( )) and ( ) : ( ( ), . . . , ( )).

K I

If we divide through by (L ( ) in (12), we get

*f P *g (x ) I *h (x )