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 ,