<<

. 38
( 59 .)



>>

Example 5.1 (Continued). The reader will recall that for 0 : k : 1 the ¬rst-
order necessary conditions were satis¬ed by three points and corresponding
multipliers given by

x : 1 9 k, x : <(2k(1 9 k), :1
 
x : 0, x : 0, : 1/k.
 
We will use the second-order necessary condition as given in Corollary 2 to
rule out the origin as a candidate for optimality when 0 : k : 1.
Recall that for any x we have
g(x) : (2k, 92x ). At x : (0, 0),
 *

g(x ) " 0, so the linear independence requirement of Corollary 2 holds. Thus
*
for z to satisfy (11) we require that

1
g(x ), z2 : 1(2k, 0), (z , z )2 : 0.

*
This is satis¬ed by all vectors (z , z ) of the form

z : 0, z arbitrary. (12)
 
The function F with : 1/k becomes

1
F : (x 9 1) ; x ; (2kx 9 x).
k 
 

Condition (10) with x : (0, 0) becomes
*
z
2 0 1
 : 2z ; 2z 1 9 . 0
(z , z )
 
  0 2(1 9  z k
I 
for all (z , z ) satisfying (12). Since z : 0 and for 0 : k : 1 the coef¬cient of
 
2z is negative; the last relation only holds for z : 0. Thus (10) fails to hold
 
for all (z , z ) satisfying (12), and so x : (0, 0) is not optimal if 0 : k : 1.
 *
172 OPTIMIZATION PROBLEMS


For k . 1 the only critical point is x : (0, 0) with : 1/k. We now have
*
1z, Fxx z2 . 0 for all z, so the second-order conditions of Theorem 6.2 and
Corollary 2 both hold at (0, 0).
We now show that for 0 : k : 1 the second-order condition (10) holds at
the two points (1 9 k, <(2k(1 9 k)). At these points : 1. Thus, for a
second-order test vector z we have E : ` and E : E. Hence (5) and (6)
 
reduce to
g (x )z : 0 at these points. Thus a test vector z satis¬es
#*
1(2k, h2(2k(1 9 k)), (z , z )2 : 2kz h 2z (k(1 9 k) : 0. (13)
  
The function F with : 1 becomes

F : (x 9 1) ; x ; (2kx 9 x)
 
 
and condition (10) becomes

z
20
 : 2(z ) . 0.
(z , z )
00 
z

This inequality is satis¬ed for all z and hence for all z satisfying (13).

We now state and prove a second-order suf¬ciency theorem [Han and
Mangasarian, 1979]. This theorem is more useful and easier to apply than the
second-order necessary conditions.

T 6.3. L et (x , , , ) satisfy the FJ necessary conditions of T heorem
*
5.1. Suppose that every z " 0 that satis¬es the tangential constraints (4) at
x : x and the inequality 1
f (x ), z2 - 0 also satis¬es
 *
*

1z, Fxx (x , , )z2 9 0, (14)
*
where

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

T hen f attains a strict local minimum for problem PI at x .
*
Note that strict inequality is required in (14), while equality is allowed in
the necessary condition (10).
Proof. To simplify notation, we assume that x : 0 and that f (0) : 0. For
*
any real-valued function : X ; R, the symbol xx will denote the Hessian

matrix whose (i 9 j )th entry is * /*x *x .
HG
If f did not attain a strict local minimum at 0, then for every positive integer
q there would exist a feasible point v " 0 such that v + B(0, 1/q) and f (v ) - 0.
O O O
SECOND-ORDER CONDITIONS 173


Thus there would exist a sequence of points +v , in X such that
O

v " 0, lim v : 0, f (v ) - 0, g(v ) - 0, h(v ) : 0.
O O O O O O

Let E : +1, . . . , r,. It then follows from Taylor™s theorem (Corollary 1,
Theorem I.11.2) and our assumption that x : 0 and f (0) : 0 that
*

f (v ) : 1
f ( v ), v 2 - 0 (15i)
O O O

and that for i : 1, . . . , r and j : 1, . . . , k

g (v ) : 1
g ( v ), v 2 - 0,
GO G GO O
h (v ) : 1
h ( v ), v 2 : 0, (15ii)
HO H HO O

where the are numbers in the open interval (0, 1).
?
It also follows from Taylor™s theorem that

f (v ) : 1
f (0), v 2 ;  1v , f xx (  v )v 2 - 0 (16i)
O
O O O O

and that for i : 1, . . . , r and j : 1, . . . , k

v 2 ;  1v , gixx (  v )v 2 - 0,
g (v ) : 1
g (0),
O
GO G O GO O
v 2 ;  1v , hjxx (  v )v 2 : 0,
h (v ) : 1
h (0), (16ii)
O
HO H O HO O

where the  are real numbers in the open interval (0, 1).
?
Since v " 0, the sequence v /#v # is a sequence of unit vectors. Hence there
O OO
exists a unit vector v and a subsequence that we relabel as +v , such that
O
v /#v # ; v.
OO
Now suppose that the sequence +v , in (15) and (16) is the subsequence. If
O
we divide through by #v # in the rightmost inequalities and the equalities in
O
(15) and then let q ; ;-, we get that v satis¬es

1
f (0), v2 - 0,
g (0)v - 0,
h(0)v : 0.
#
Thus v satis¬es the tangential constraints (4).
Next, multiply the ¬rst inequality in (16) by . 0, the ith inequality in (16)

by . 0 (the ith component of ), and the jth equation in (10) by (the jth
G H
component of ) and then add the resulting equations and inequalities. Since
174 OPTIMIZATION PROBLEMS


:( ) and : 0, we get
,
# ' '

f (0) ; R
g(0) ; R
h(0), v 2 ;  1v , Fxx (  v )v 2 - 0,

1
O
 O OO
where

L I
F (  v ) : fxx (  v ) ;  gixx (  v ) ;  h ( v ).
H jxx  H O
O  O G GO
xx
G H
Since (0, , , ) satis¬es the FJ necessary conditions of Theorem 5.1, we get
that

 1v , F (  v )v 2 - 0.
 O xx O O
If we now divide both sides of this inequality by #v # and then let q ; -, we
O
get that 1v, F (0)v2 - 0 for a nonzero vector that satis¬es the tangential
xx
constraints (4) and 1
f (0), v2 - 0. This contradicts the assumption that (14)
holds for all such z.

: 1, we have a slightly
If there exists a set of multipliers at x with

*
different version of the suf¬cient conditions.

C¬¬ 4. L et (x , , ) satisfy the KKT necessary conditions of T heorem
*
5.2. Suppose that every z " 0 in RL that satis¬es the tangential constraints (4) at
x : x and the equality 1
f (x ), z2 : 0 also satis¬es
 * *
1z, Fxx (x , , )z2 9 0, (17)
*
where

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

T hen f attains a strict local minimum for problem PI at x .
*
The corollary differs from the theorem in that the condition 1
f (x ), z2 - 0
*
is replaced by 1
f (x ), z2 : 0.
*
Proof. If (x , , ) satis¬es the conditions of Theorem 5.2, then
*

f (x ) ; R
g(x ) ; R
h(x ) : 0.
*
* *
: 0,
Since
'

f (x ) : 9 R
g (x ) 9 R
h(x ).
# #*
* *
SECOND-ORDER CONDITIONS 175


Hence, for any z + RL

1
f (x ), z2 : 91 ,
g (x )z2 9 1 ,

<<

. 38
( 59 .)



>>