<<

. 37
( 59 .)



>>

Theorem 6.1 there exists a 9 0 and a C N function ( · ) de¬ned on the interval
(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\M M 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\M M 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.

<<

. 37
( 59 .)



>>