David G. Luenberger, Yinyu Ye - Linear and Nonlinear Programming International Series Episode 2 Part

References 317

10.6 The lemma on interlocking eigenvalues is due to Loewner [L6]. An analysis of the one￾by-one shift of the eigenvalues to unity is contained in Fletcher [F6]. The scaling concept,

including the self-scaling algorithm, is due to Oren and Luenberger [O5]. Also see Oren

[O4]. The two-parameter class of updates defined by the scaling procedure can be shown to

be equivalent to the symmetric Huang class. Oren and Spedicato [O6] developed a procedure

for selecting the scaling parameter so as to optimize the condition number of the update.

10.7 The idea of expressing conjugate gradient methods as update formulae is due to Perry

[P3]. The development of the form presented here is due to Shanno [S4]. Preconditioning

for conjugate gradient methods was suggested by Bertsekas [B9].

10.8 The combined method appears in Luenberger [L10].

Chapter 11 CONSTRAINED

MINIMIZATION

CONDITIONS

We turn now, in this final part of the book, to the study of minimization problems

having constraints. We begin by studying in this chapter the necessary and sufficient

conditions satisfied at solution points. These conditions, aside from their intrinsic

value in characterizing solutions, define Lagrange multipliers and a certain Hessian

matrix which, taken together, form the foundation for both the development and

analysis of algorithms presented in subsequent chapters.

The general method used in this chapter to derive necessary and sufficient

conditions is a straightforward extension of that used in Chapter 7 for unconstrained

problems. In the case of equality constraints, the feasible region is a curved surface

embedded in En. Differential conditions satisfied at an optimal point are derived by

considering the value of the objective function along curves on this surface passing

through the optimal point. Thus the arguments run almost identically to those for

the unconstrained case; families of curves on the constraint surface replacing the

earlier artifice of considering feasible directions. There is also a theory of zero-order

conditions that is presented in the final section of the chapter.

11.1 CONSTRAINTS

We deal with general nonlinear programming problems of the form

minimize fx

subject to h1x = 0 g1x 0

h2x = 0 g2x 0





 





hmx = 0 gpx 0

x∈  ⊂ En

(1)

where m n and the functions f, hi i = 1 2m and gj j = 1 2p

are continuous, and usually assumed to possess continuous second partial

321