目录
- Contents
Preface
prefcetothe Second Edition
1 Introduction 1
Mathematical Formulation 2
Example:A Transportation Problem 4
Continuous versus Discrete Optimization 5
Constrained and Unconstrained Optimization 6
Global and Local Optimization 6
Stocbastic and Deterministic Optimization 7
Convexity 7
Optimization Algorithms 8
Notes and References 9
2 Fundamentals of Unconstrained Optimization 10
2.1 What ls a Solution? 12
Recognizing a Local Minimum 14
Nonsmooth Problems 17
2.2 Overview of A1gorithms 18
Two Strategies:Line Search and Trust Region 19
Search Directions for Line Search Methods 20
Models for Trust-Region Methods 25
Scaling 26
Exercises 27
3 Line Search Methods 30
3.1 Step Length 31
The Wolfe Conditions 33
The Goldstein Conditions 36
Sufficient Decrease and Backtracking 37
3.2 Convergence of Line Search Methods 37
3.3 Rate of Convergence 41
Convergence Rate of Steepest Descent 42
Newton's Method 44
Quasi-Newton Methods 46
3.4 Newton's Method with Hessian Modification 48
Eigenvalue Modification 49
Adding a Multiple of the ldentity 51
Modified Cholesky Factorization 52
Modified Symmetric Indefinite Factorization 54
3.5 Step-Length Selection Algorithms 56
lnterpolation 57
lnitial Step Length 59
A Line Search A1gorithm for the Wolfe Conditions 60
Notes and References 62
Exercises 63
4 Trust-Region Methods 66
Outline of the Trust-Region Approach 68
4.1 A1gorithms Based on the Cauchy Point 71
The Cauchy Point 71
lmpro时ng on the Cauchy Point 73
The Dogleg Method 73
Two-Dinlensional Subspace Mininlization 76
4.2 Global Convergence 77
Reduction Obtained by the Cauchy Point 77
Convergence to Stationary Points 79
4.3 lterative Solution of the Subproblem 83
The Hard Case 87
Proof of Theorem 4.1 89
Convergence of Algorithms Based on Nearly Exact Solutions 91
4.4 Local Convergence ofTrust-Region Newton Methods 92
4.5 0ther Enhancements 95
Scaling 95
Trust Regions in 0ther Norms 97
Notes and References 98
Exercises 98
5 Conjugate Gradient Methods 101
5.1 The linear Conjugate Gradient Method 102
Conjugate Direction Methods 102
Basic Properties of thee Conjugate Gradient Method 107
A Practical Form of the Conjugate Gradient Method 111
Rate of Convergence 112
Preconditioning 118
Practical Preconditioners 120
5.2 Nonlinear Conjugate Gradient Methods 121
The Fletcher-Reeves Method 121
The Polak-Ribière Method and Variants 122
Quadratic Termination and Restarts 124
Behavior of the Fletcher-Reeves Method 125
Global Convergence 127
Numerical Performance 131
Notes and Reference 132
Exercises 133
6 Quasi-Newton Methods 135
6.1 The BFGS Method 136
Properties ofthe BFGS Method 141
Implementation 142
6.2 The SR1 Method 144
Properties of SR1 Updating 147
6.3 The Broyden Class 149
6.4 Convergence Analysis 153
Global Convergence of the BFGS Method 153
Superlinear Convergence of the BFGS Method 156
Convergence Analysis of the SR1 Method 160
Notes and References 161
Exercises 162
7 Large-Scale Unconstrained optimization 164
7.1 lnexact Newton Methods 165
Local Convergence of Inexact Newton Methods 166
Line Search Newton-CG Method 168
Trust-Region Newton-CG Method 170
Preconditioning the Trust-Region Newton-CG Method 174
Trust-Region Newton-Lanczos Method 175
7.2 Limited-Memory Quasi-Newton Methods 176
Limited-Memory BFGS 177
Relationship with Conjugate Gradient Methods 180
General Lirnited:d-Memory Updatiug 181
Compact Representation of BFGS Updating 181
Unrolling the Update 184
7.3 Sparse Quasi-Newton Updates 185
7.4 Algorithms for Partially Separable Fnnctions 186
7.5 Perspectives and Sotrware 189
Notes and References 190
Exercises 191
8 Calculating Derivatives 193
8.1 Finite-Difference Derivative Approximations 194
Approximating the Gradient 195
Approximating a Sparse Jacobian 197
Approximatiug the Hessian 201
Approximatiug a Sparse Hessian 202
8.2 Automatic Differentiation 204
Au Example 205
The Forward Mode 206
The Reverse Mode 207
Vector Fnnctions and Partial Separablity 210
Calculating Jacobians ofVector Funlctions 212
Calculating Hessians:Forward Mode 213
Calculating Hessians:Reverse Mode 215
Current Lirnitations 216
Notess and References 217
Exercises 217
9 Derivatve-Free Optiimization 220
9.1 Finite Differences and Noise 221
9.2 Model-Based Methods 223
Interpolation aod Polyoomial Bases 226
Updating the Interpolation Set 227
A Method Based on Minimum-Change Updating 228
9.3 Coordinate and Pattern-Search Methods 229
Coordinate Search Method 230
Pattern-Search Methods 231
9.4 A Conjugate-Direction Method 234
9.5 Nelder-Mead Method 238
9.6 Implicit Filtering 240
Notes and References 242
Exercises 242
10 Least-Sqnares Problems 245
10.1 Background 247
10.2 Linear Least-Squares Problems 250
10.3 Algorithms for Nonlinear Least-Squares Problems 254
The Gauss-Newton Method 254
Convergence of the Gauss Newton Method 255
The Levenberg-Marquardt Method 258
Implementation of the Levenberg-Marquardt Method 259
Convergence of the Levenberg-Marquardt Method 261
Methods for Large-Residual Problems262
10.4 Orthogonal Distance Regression 265
Nootes and References 267
Exerclses 269
11 Nonlinear Equations 270
11.1 Local A1gorithms 274
Newton's Method for Nonlinear Equations 274
Inexact Newton Methods 277
Broyden's Methods 279
Tensor Methods 283
11.2 Practical Methods 285
Merit Functions 285
Line Search Methods 287
Trust-Region Methods 290
11.3 Continuation/Homotopy Methods 296
Motivation 296
Practical Continuation Methods 297
Notes and References 302
Exercises 302
12 Theory of Constrained Optimization 304
Local and Global Solutions 305
Smoothness 306
12.1 Examples 307
A Single Equality Constraint 308
A Single Inequality Constraint 310
Two Inequality Constraints 313
12.2 Tangent Cone and Constraint Qualifications 315
12.3 First-Order Optimality Conditions 320
12.4 First-Order Optimality Conditions:Proof 323
Relating the Tangent Cone and the First-Order Feasible Direction Set 323
A Fundamental Necessary Condition 325
Farkas' Lemma 326
Proof ofTbeorem 12.1 329
12.5 Second-Order Conditions 330
Second-Order Conditions and projected Hessians 337
12.6 Other Constraint Qualifications 338
12.7 A Geometric Viewpoint 340
12.8 Lagrange Multipliers and Sensitivity 341
12.9 Duality343
Notes and References 349
Exercises 351
13 Linear Programming:Tbe Sirnplex Method 355
Linear Programming 356
13.1 Optimality and Duality 358
Optimality Conditions 358
Tbe Dual Problem 359
13.2 Geometry of the Feasible Set 362
Bases and Basic Feasible Points 362
A Single Step of the Feasible Polytope 365
13.3 The Sirnplex Metbod 366
Outline 366
A Single Step of the Metbod 370
13.4 Linear Algebra in the Sirnplex Metbod372
13.5 Other Important Detaills 375
Pricing and Selection of the Entering Index 375
Starting the Sirnplex Method378
Degenerate Steps and Cycling 381
13.6 Tbe Dual Sirnplex Method 382
13.7 Presolving 385
13.8 Where Does the Sirnplex Metbod Fit1 388
Notes and References 389
Exfercises 389
14 Linear Programming:lnterior-Point Methods 392
14.1 Primal-Dual Methods 393
Outlioe 393
The Central Path 397
Central Path Neighborhoods and path-Following Methods 399
14.2 Practical Primal-Dual Algorithms 407
Corrector and Centering Steps 407
Step Lengths 409
Starting Point 410
A Practiica1 Algorithm 411
Solving Linear Systems 411
14.3 Other Primal-Dual Algorithms and Extensions 413
0ther Parimal-Followmg Methods 413
Potential-Reduction Metheods 414
Extenlsions 415
14.4 Perspectives and Software 416
Notes and References 417
Exercises 418
15 Fundamentals of A1gorithms for Nonlinear Constrained Optization 421
15.1 Categorizing Optimization Algorithms 422
15.2 The Combmatorial Difficulty of Inequality Constrained Problems 424
15.3 Elimiuation of Variables 426
Simple Elimination usmg Lmear Constraints 428
General Reduction Strategies for Lmear Constraints 431
Effect of lnequality Constraints 434
15.4 Merit Functions and Filtes 435
Merit Functions 435
Filters 437
15.5 The Maratos Effect 440
15.6 Second-Order Correction and Nonmonotone Tecbniques 443
Nonmonotone (Watcbdog) Strategy 444
Notes and References 446
Exercises 446
16 Quadratic Programs 448
16.1 Equality-Constrained Quadratic Programs 451
Properties of Equality-Constrained QPs 451
16.2 Direct Solution of the KKT System 454
Factormg 也e Full KKT System 454
Scbur-Complement Method 455
Null-Space Method 457
16.3 Iterative Solution of the KKT System 459
CG Applied to the Reduced System 459
The ProjectedCG Method 461
16.4 Inequality-Constrained Problems 463
Optimality Conditions for Inequality-Constrained Problems 464
Degeneracy 465
16.5 Active-Set Methods for Convex QPs 467
Specification of the Active-Set Method for Convex QP 472
Further Remarks on the Active-Set Method 476
Finite Termination of Active-Set A1gorithm on Strictly Convex QPs 477
Updating Factorizations 478
16.6 Interior-Point Methods 480
Solving the PrinIal-Dual System 482
Step Length Selection 483
A Practical PrinIal-Dual Method 484
16.7 The Gradient Projection Method 485
Caucby Point Computation 486
Subspace Mininimization 488
16.8 Perspectives and Software 490
Notes and References 492
Exercises 492
17 Penalty and Angmented Lagrangian Methods 497
17.1 Tbe Quadratic penalty Method 498
Motivation 498
Algorithmic Framework 501
Convergence of the Quadratic Penalty Method 502
Ⅲ Conditioning and Reformulations 505
17.2 Nonsmooth Peualty Functions 507
A Practical e1 Penalty Method 511
A General Class ofNonsmooth Penalty Methods 513
17.3 Augmented Lagrangian Method:Equality Constraints 514
Motivation and A1gorithmic Framework 514
Properties of the Augmented Lagrangian 517
17.4 Practical Augmented Lagrangian Methods 519
Bound-Constrained Formulation 519
Linearly Constrained Formulation 522
Unconstrainde Formulation 523
17.5 Perspectives and Software 525
Notes and References 526
Exercises 527
18 Sequential Quadratic Programming 529
18.1 Local SQP Method 530
SQP Framework 531
Inequality Constraints 532
18.2 Preview ofPractical SQP Methods 533
IQP and EQP 533
Enforcing Convergence 534
18.3 Algorithmic Development 535
Handling Inconsistent Linearizations 535
FuIl Quasi-Newton Approxirnations 536
Reduced-Hessian Quasi-Newton Approxirnations 538
Merit Functions 540
Second-Order Correction 543
18.4 A Practical Line Search SQP Method 545
18.5 Trust-Region SQP Methods 546
A Relaxation Method for Equality-Constrained Optimization 547
St1QP(Sequential t1 Quadratic Programming) 549
Sequential Linear-Quadratic Programming (SLQP) 551
Aτèchnique for Updating the Penalty Parameter 553
18.6 Nonlinque Gradient Projection 554
18.7 Convergence Analysis 556
Rate of Convergence 557
18.8 Perspectives and Software 560
Notes and References 561
Exercises 561
19 Interior-Point Methods for Nonlinear Programming 563
19.1 Two InterPretations 564
19.2 A Basic Interior-Point A1gorithm 566
19.3 A1gorithmic Development 569
Primal vs.Primal-Dual System570
Solving the Primal-Dual System 570
Updating the Barrier Parameter 572
Handling Nonconvexity and Singularity 573
Step Acceptance:Merit Functions and Filters 575
Quasi-Newton Approximations 575
Feasible Interior-Point Methods 576
19.4 A Line Search Interior-Point Method 577
19.5 A Trust-Region Interior-Point Method 578
An A1gorithm for Solving the Barrier Problem 578
Step Computation 580
Lagrange MuItipliers Estimates and Step Acceptance 581
Description of a Trust-Region Interior-Point Method 582
19.6 The Primal Log-Barrier Method 583
19.7 Global Convergence Propertiles 587
Failure of tbe Line Search Approach 587
Modified Line Search Metbods 589
Global Convergence of the Trust-Region Approach 589
19.8 Superlinear Convergence 591
19.9 Perspectives and Sofware 592
Notes and References 593
Exercises 594
A Background Material 598
A.l Elements of Linear A1gebra 598
Vectors and Matriices 598
Norms 600
Subspaces 602
Eigenva1ues, Eigenvectors，and the Singular-Value Decomposition 603
Determinant and Trace 605
Matrix Factorizations:Cholesky,LU，QR 606
Synunetric Indefinite Factorization 610
Sherman-Morrison-Woodbury Formula 612
Interlacing Eigenvalue Theorem 613
Error Analysis and Floating-Point Arithmetic 613
Conditioning and Stability 616
A.2 Elements of Analysis,Geometry,Topology 617
Sequences 617
Rates of Convergence 619
Topology of tbe Euclideean Space Rn 620
Convex Sets in Rn 621
Continuity and Limits 623
Derivatives 625
Directional Derivatives 628
Mean Value Theorern 629
Implicit Function Theorem 630
Order Notation 631
Root-Finding for Scalar Equations 633
B A Reaularization Procedure 635
References 637
Index 653
京公网安备 11010102004214号