1 Introduction 1
MathematicalFormulation . . . . . . . . . . . . . . . . . . . . . . . . 2
Example:ATransportationProblem . . . . . . . . . . . . . . . . . . . 4
ContinuousversusDiscreteOptimization . . . . . . . . . . . . . . . . . 5
ConstrainedandUnconstrainedOptimization . . . . . . . . . . . . . . 6
GlobalandLocalOptimization . . . . . . . . . . . . . . . . . . . . . . 6
Stochastic and Deterministic Optimization . . . . . . . . . . . . . . . . 7
Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 8
NotesandReferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Fundamentals of Unconstrained Optimization 10
2.1 What IsaSolution? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Recognizing a Local Minimum . . . . . . . . . . . . . . . . . . . . . . 14
NonsmoothProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Overview of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 18
TwoStrategies:LineSearchandTrustRegion . . . . . . . . . . . . . . . 19
SearchDirections forLineSearchMethods . . . . . . . . . . . . . . . . 20
Models for Trust-Region Methods . . . . . . . . . . . . . . . . . . . . . 25
Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Line SearchMethods 30
3.1 StepLength . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
TheWolfe 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 theWolfe Conditions . . . . . . . . . . . . 60
NotesandReferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4 Trust-RegionMethods 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 IterativeSolutionof theSubproblem . . . . . . . . . . . . . . . . . . . 83

……
……