(0) : z,

(0) : x ,

>

g( (t)) - 0, h( (t)) : 0 for all t in [0, ).

The Kuhn”Tucker constraint quali¬cation is dif¬cult to check. In Lemma 6.1

we give a veri¬able condition that implies KTQ.

Let x be a solution of problem PI and let KTQ hold at x . Show that the

* *

conclusion of Theorem 5.2 holds without invoking Theorem 5.1. Hint: What

can you say about the right-hand derivatives at t : 0 of the mappings

t ; f ( (t)), t ; g ( (t)), and t ; h( (t)) in relation to Farkas™s theorem?

#

6. SECOND-ORDER CONDITIONS

In this section we ¬rst obtain second-order necessary conditions. Points that

satisfy the ¬rst-order necessary conditions but fail to satisfy the second-order

conditions cannot solve the programming problem. We conclude this section

with a presentation of some second-order suf¬ciency conditions. Points that

satisfy the ¬rst-order necessary conditions and these suf¬ciency conditions are

solutions to the programming problem.

Since second-order conditions involve second derivatives, in this section we

assume that the functions f , g, and h that occur in the statement of problem

PI are of class C on X .

The derivation of our second-order necessary condition will require an

application of the implicit function theorem, which we now discuss.

Consider the system of equations

u (x , . . . , x , y , . . . , y ) : 0,

L K

$ (1)

u (x , . . . , x , y , . . . , y ) : 0,

K L K

where the real-valued functions u , i : 1, . . . , m, are de¬ned on an open set

G

D : D ;D , where D is open in the x-space RL and D is open in the y-space

RK. Equation (1) asks us to ¬nd all (x, y) in D such that (1) is satis¬ed. For a

given x in D , the system (1) can therefore be interpreted as a system of m

equations for the m unknowns ( y , . . . , y ). If for each x in some subset S of

K

D we can ¬nd a unique solution y(x) : (y (x), . . . , y (x)), then in this fashion

K

we obtain a function y( · ) with domain S. In this event, we say that (1) de¬nes

y as a function of x implicitly.

164 OPTIMIZATION PROBLEMS

Let (x , y ) be a point in D that satis¬es (1). The implicit function theorem

gives conditions ensuring that (1) has a unique solution for points x suf¬ciently

close to x . The resulting function y( · ) will inherit the regularity properties of

the functions u , . . . , u .

K

To illustrate these ideas, take D : R, D : R, and D : R : R;R.

Consider

u(x , x , y) : x ; x ; y 9 1 : 0. (2)

The set of points (x, y) : (x , x , y) in R that satisfy (2) is the surface of the

ball with center at the origin and radius 1.

Given any point (x , y ) : (x , x , y ) with y 9 0 that satis¬es (2), we can

¬nd an 9 0 and a 9 0 such that

y : (1 9 x 9 x

is the unique solution of (2) for x in B(x , ) having range in B( y , ) The point

(x , 9y ) also satis¬es (2), and

y : 9(1 9 x 9 x

is the unique solution of (2) for x in B(x , ) having range in B(9y , ).

Although all points of E : +(x, y) : x ; x : 1, y : 0, are solutions of (2),

equation (2) does not de¬ne y as a function of x on any ball about a point x

such that #x # : 1. Since * f /*y : 2y, we see that at any point (x , y ) that

satis¬es (2) we have * f /*y " 0 if y " 0 and * f /*y : 0 if y : 0. Thus at all

points of E, * f /*y : 0. The reader should return to this paragraph after

reading Theorem 6.1.

Equation (1) in vector form is

u(x, y) : 0.

T 6.1 (I°¬©© Fµ®©® T). L et D be an open set in RL and

let D be an open set in RK. L et D : D ;D . L et

u : (x, y) ; u(x, y), x+D , y+D ,

be a mapping that is of class C N on D and with range in RK. L et (x , y ), x + D ,

y + D , be a solution of

u(x, y) : 0

SECOND-ORDER CONDITIONS 165

and suppose that the m;m matrix

*u

G (x , y ) ,

J(x , y ) : i : 1, . . . , m, j : 1, . . . , m, (3)

*y

H

is nonsingular. T hen there exist an 9 0, a 9 0, and a function y( 9 ) de¬ned

on B(x , ) : D with range in B(y , ) : D such that

y( · ) is of class CN, (i)

y(x, y(x)) : 0 for all x + B(x , ). (ii)

Moreover, for x in B(x , ), y(x) is the only solution of u(x, y) : 0 such that

y(x) + B(y , ).

For a proof of this theorem we refer the reader to Rudin [1976] or Fleming

[1977].

De¬nition 6.1. Let x be a point of X . The vector z " 0 in RL is said to satisfy

the tangential constraints at x if

g (x )z - 0,

h(x )z : 0, (4)

#

where E : +i : g (x ) : 0,.

G

For de¬niteness we shall henceforth suppose that E : +1, . . . , r,. Let

I : +r ; 1, . . . , m,. Since either E or I can be empty, 0 - r - m.

Let z be a vector that satis¬es the tangential constraints. Let

E : +i : i + E, 1

g (x ), z2 : 0,,

G

E : +i : i + E, 1

g (x ), z2 : 0,.

G

Then E : E 6 E ,

g (x )z : 0,

h(x )z : 0, (5)

#

and

g (x )z : 0. (6)

#‚

For the sake of de¬niteness suppose that E : +1, . . . , q,. Since E may be

empty, 0 - q - r. If q : 0, statements involving E in (5) in the ensuing

discussion should be deleted. The reader should keep in mind that the sets E

and E depend on z and x .

166 OPTIMIZATION PROBLEMS

The next lemma gives a condition under which, given a vector z that satis¬es

the tangential constraints, we can construct a curve ( · ) emanating from x

and going into the feasible set in the direction given by z.

L 6.1. L et g and h be of class C N on X , p . 1. L et x be feasible and let

z satisfy the tangential constraints at x . Suppose that the vectors

g (x ), . . . ,

g (x ),

h (x ), . . . ,

h (x ) (7)

O I

are linearly independent. T hen there exists a 9 0 and a C N mapping ( · ) from

(9 , ) to RL such that

(0) : x , (0) : z,

g ( (t)) : 0, h( (t)) : 0, g ( (t)) : 0

# '

g ( (t)) : 0 for 0 : t : .

#‚

Proof. Let : q ; k. In view of (7), - n. If : n, then again in view of

(7) the only solution of (5) is z : 0. Hence, E : ` and E : E. The mapping

( · ) is then the constant map (t) : x .

We now suppose that : n. Let denote the ;n matrix whose rows are

the vectors in (7). Thus

g (x )

# ,

:

h(x )

and has rank . By relabeling the coordinates corresponding to linearly

independent columns of , we may suppose without loss of generality that the

¬rst columns of the matrix are linearly independent. Thus the ; matrix

*g (x )

G

*x

H

: i : 1, . . . , q, s : 1, . . . , k, j : 1, . . . , ,

M *h (x )

Q

*x

H

is nonsingular.

The system of equations

g (x) : 0,

#

h(x) : 0,

x 9x 9 tz : 0, (8)

M> M> M>

$

x 9 x 9 tz : 0,

L L L

SECOND-ORDER CONDITIONS 167

where z , . . . , z are the last n 9 components of the vector z, has a solution

M> L

(x, t) : (x , 0). We shall use the implicit function theorem to show that the

system (8) determines x as a function of t near t : 0.

For the system (8), viewed as de¬ning x implicitly as a function of t, the

matrix J de¬ned in (3) becomes

M L\M ,

J:

I

0

L\MM L\M

is the ;(n 9 ) matrix whose columns are the last n 9 columns

where

L\M

is the (n 9 ); zero matrix, and I

of , the matrix 0 is the

L\MM L\M

(n 9 );(n 9 ) identity matrix. Since is nonsingular, so is J. Hence by

M