viii C ONTENTS
Recognizing a Local Minimum ...................... 14
NonsmoothProblems ........................... 17
2.2 Overview of Algorithms .......................... 18
TwoStrategies:LineSearchandTrustRegion............... 19
SearchDirectionsforLineSearchMethods ................ 20
Models for Trust-Region Methods . . . .................. 25
Scaling................................... 26
Exercises...................................... 27
3 Line Search Methods 30
3.1 StepLength ................................ 31
The Wolfe Conditions ........................... 33
The Goldstein Conditions . . ....................... 36
Sufficient Decrease and Backtracking . .................. 37
3.2 ConvergenceofLineSearchMethods ................... 37
3.3 RateofConvergence............................ 41
ConvergenceRateofSteepestDescent................... 42
Newton’sMethod ............................. 44
Quasi-NewtonMethods.......................... 46
3.4 Newton’s Method with Hessian Modification ............... 48
EigenvalueModification.......................... 49
Adding a Multiple of the Identity . . . .................. 51
Modified Cholesky Factorization ..................... 52
ModifiedSymmetricIndefiniteFactorization............... 54
3.5 Step-Length Selection Algorithms ..................... 56
Interpolation................................ 57
InitialStepLength............................. 59
A Line Search Algorithm for the Wolfe Conditions . . . ......... 60
NotesandReferences ............................... 62
Exercises...................................... 63
4 Trust-Region Methods 66
Outline of the Trust-Region Approach .................. 68
4.1 Algorithms Based on the Cauchy Point .................. 71
TheCauchyPoint ............................. 71
ImprovingontheCauchyPoint...................... 73
TheDoglegMethod ............................ 73
Two-Dimensional Subspace Minimization . . .............. 76
4.2 GlobalConvergence ............................ 77
ReductionObtainedbytheCauchyPoint................. 77
ConvergencetoStationaryPoints ..................... 79
4.3 IterativeSolutionoftheSubproblem ................... 83
