<<

. 36
( 59 .)



>>

[0, ) such that

 (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\M M 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\M M L\M
(n 9 );(n 9 ) identity matrix. Since is nonsingular, so is J. Hence by
M

<<

. 36
( 59 .)



>>