(9 , ) and with range in RL such that

(0) : x ,

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

#

(t) : x ; tz , i : ; 1, . . . , n.

G G G

Differentiation of the equations in (9) with respect to t and then setting t : 0

give

0

(0) : ,

I

0 z

L\MM L\M

where z : (z

, . . . , z ). The matrix on the left is the matrix J for the system

M> L

(8) and is nonsingular. Therefore the system

0

w:

I

0 z

L\MM L\M

has a unique solution. Since (0) and z are both solutions, we get that

(0) : z.

Since g (x ) : 0 and (0) : x , it follows from the continuity of g and that

'

for suf¬ciently small we have g ( (t)) : 0 for "t" - .

'

Since

dg ( (t))

#‚ :

g ( (t)) (t)

#‚

dt

and since (0) : x and (0) : z, it follows from (6) that dg ( (0))/dt : 0. It

#

then follows from continuity that by taking to be smaller, if ‚necessary, there

is an interval [0, ) on which all of the previous conclusions hold and on which

168 OPTIMIZATION PROBLEMS

dg ( (t))/dt : 0. Since g ( (0)) : g (x ) : 0, we have g ( (t)) : 0 on (0, ).

#‚ # #‚ #‚

This completes the proof. ‚

C¬¬ 1. L et CQ hold at a point x . T hen for every z satisfying relation

(18) in Section 5 there exists a C N function ( ) such that (0) : x , (0) : z

and (t) is feasible for all t in some interval [0, ). Moreover, g( (t)) : 0 on (0, ).

Proof. A vector z satisfying relation (18) in Section 5 satis¬es the tangential

constraints, and the set of indices E corresponding to z is empty.

Example 5.2 (Continued). At the point x : (1, 0)

*

0 91 z 9z

: .

g (x )z :

#* z z

0 1

Therefore, since there are no equality constraints, every vector of the form

(z , 0) satis¬es the tangential constraints. Clearly, there exists no curve ( · )

emanating from x : (1, 0) with tangent vector (1, 0) at x such that (t) is

* *

feasible for t in some interval [0, ). Lemma 6.1 is not contradicted, since we

have E : E and the rows of

g (x ) are linearly dependent. Also, the

#*

conclusion of the corollary is not contradicted since CQ does not hold at (1, 0).

We now present a second-order necessary condition.

De¬nition 6.2. Let (x , , ) be as in Theorem 5.2. Let z be a vector that

*

satis¬es the tangential constraints (4) at x . Let

*

E : E (z) : +i : i + E, 1

g (x ), z2 : 0,,

G*

E : E (z) : +i : i + E, 1

g (x ), z2 : 0,.

G*

The vector z will be called a second-order test vector if (i) : 0 for i + E and

G

(ii) the rows of the matrix

g (x )

# *

h(x )

*

are linearly independent.

T 6.2. L et f, g, and h be of class C on X . L et x be a solution to

*

problem PI. L et and be KKT multipliers as in T heorem 5.2 and let F( , , )

be de¬ned by

F(x, , ) : f (x) ; 1 , g(x)2 ; 1 , h(x)2.

SECOND-ORDER CONDITIONS 169

T hen for every second-order test vector z,

1z, Fxx (x , , )z2 . 0, (10)

*

where

*F

Fxx : i : 1, . . . , n, j : 1, . . . , n.

,

*x *x

HG

We ¬rst establish an elementary result.

L 6.2. L et

be a C function de¬ned on an interval (9 , ) such that

(0) : 0 and

(t) .

(0) for all t in [0, ). T hen

(0) . 0.

Proof. By Taylor™s theorem, for 0 : t :

(t) 9

(0) :

( t)t,

where 0 : : 1. If

(0) were negative, then by continuity there would exist

an interval [0, ) on which

would be negative. Hence

(t) :

(0) on this

interval, contradicting the hypothesis.

Proof (Theorem 6.2). Let z be a second-order test vector. Since : 0 for

G

i + E and

:( ):( ) :(

, , , , 0, 0),

# ' # #‚ ' #

we have

F(x, , ) : f (x) ; 1 , g (x)2 ; 1 , h(x)2.

# #

Let ( · ) be the function corresponding to z as in Lemma 6.1, with x : x .

*

Since g ( (t)) : 0 and h( (t)) : 0 for "t" : , we have

#

f ( (t)) : F( (t), for "t" : .

,)

Since for 0 - t : , all points (t) are feasible, and since (0) : x , the

*

mapping t ; f ( (t)), where 0 - t : has a minimum at t : 0. Hence, so does

the mapping

( · ) de¬ned on [0, ) by

(t) : F( (t), , ).

170 OPTIMIZATION PROBLEMS

Straightforward calculation gives

(t) : 1

F( (t), , ), (t)2

(t) : 1 (t), Fxx ( (t), , ) (t)2 ; 1

F( (t), , ), (t)2.

Setting t : 0 in the ¬rst equation and using the relations (0) : x and

*

F(x , , ) : 0 give

(0) : 0. Hence by Lemma 6.2 we have

(0) . 0.

*

Setting t : 0 in the second equation and using (0) : x ,

F(x , , ) : 0, and

* *

(0) : z give the conclusion of the theorem.

The following corollary requires that (10) holds for fewer z than the theorem

does and thus is more restrictive than the theorem but easier to apply.

C¬¬ 2. L et the functions f , g, and h be as in T heorem 6.2 and let x be

*

a solution to problem PI. Suppose that the vectors

g (x ), . . . ,

g (x ),

h (x ), . . . ,

h (x )

* P* * I*

are linearly independent. T hen there exist KKT multipliers , as in T heorem

5.2, and (10) holds for every vector z satisfying

g (x )z : 0,

h(x )z : 0. (11)

#* *

Proof. The existence of KKT multipliers follows from Corollary 1 of

Theorem 5.2. The second conclusion follows from the theorem by taking

E : E, in which case E : +1, . . . , r, and E : `.

If the inequality constraints are absent, then the linear independence

hypothesis of Theorem 6.2 and Corollary 2 becomes ˜˜the vectors

h (x ), . . . ,

h (x ) are linearly independent,™™ which is also the constraint

* I*

quali¬cation CQ for this problem. Thus, we get the following corollary.

C¬¬ 3. L et f and h be as in T heorem 6.2, let the inequality constraints

be absent, let x be a solution of problem PI and let CQ hold at x . T hen there

* *

exists a unique vector in RI such that the function H( , ) de¬ned by

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

satis¬es

f (x ) ; R

h(x ) : 0

(i)

* *

SECOND-ORDER CONDITIONS 171

and

1z, Hxx (x , )z2 . 0

(ii)

*

for all z in RL satisfying

h(x )z : 0.

*

Corollary 3 is the classical second-order necessary condition for equality-

constrained problems.