Optimization Theory and Methods: Nonlinear Programming (Springer Optimization and Its Applications)

OPTIMIZATION THEORY AND METHODS: NONLINEAR PROGRAMMING......Page 1
Springerlink......Page 0
Half-title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Contents......Page 6
Preface......Page 12
1.1 Introduction......Page 14
1.2 Mathematics Foundations......Page 15
1.2.1 Norm......Page 16
1.2.2 Inverse and Generalized Inverse of a Matrix......Page 22
1.2.3 Properties of Eigenvalues......Page 25
1.2.4 Rank-One Update......Page 30
1.2.5 Function and Differential......Page 35
1.3 Convex Sets and Convex Functions......Page 44
1.3.1 Convex Sets......Page 45
1.3.2 Convex Functions......Page 49
1.3.3 Separation and Support of Convex Sets......Page 63
1.4 Optimality Conditions for Unconstrained Optimization......Page 70
1.5 Structure of Optimization Methods......Page 76
Exercises......Page 81
2.1 Introduction......Page 84
2.2 Convergence Theory for Exact Line Search......Page 87
2.3.1 The Golden Section Method......Page 97
2.3.2 The Fibonacci Method......Page 100
2.4.1 Quadratic Interpolation Methods......Page 102
2.4.2 Cubic Interpolation Method......Page 111
2.5 Inexact Line Search Techniques......Page 115
2.5.1 Armijo and Goldstein Rule......Page 116
2.5.2 Wolfe–Powell Rule......Page 117
2.5.3 Goldstein Algorithm and Wolfe–Powell Algorithm......Page 119
2.5.4 Backtracking Line Search......Page 121
2.5.5 Convergence Theorems of Inexact Line Search......Page 122
Exercises......Page 129
3.1.1 The Steepest Descent Method......Page 132
3.1.2 Convergence of the Steepest Descent Method......Page 133
3.1.3 Barzilai and Borwein Gradient Method......Page 139
3.1.4 Appendix: Kantorovich Inequality......Page 142
3.2 Newton’s Method......Page 143
3.3 Modified Newton’s Method......Page 148
3.4 Finite-Difference Newton’s Method......Page 153
3.5 Negative Curvature Direction Method......Page 160
3.5.1 Gill–Murray Stable Newton’s Method......Page 161
3.5.2 Fiacco–McCormick Method......Page 164
3.5.3 Fletcher–Freeman Method......Page 165
3.5.4 Second-Order Step Rules......Page 168
3.6 Inexact Newton’s Method......Page 176
Exercises......Page 185
4.1 Conjugate Direction Methods......Page 188
4.2.1 Conjugate Gradient Method......Page 191
4.2.2 Beale’s Three-Term Conjugate Gradient Method......Page 198
4.2.3 Preconditioned Conjugate Gradient Method......Page 201
4.3.1 Global Convergence of Conjugate Gradient Methods......Page 204
4.3.2 Convergence Rate of Conjugate Gradient Methods......Page 211
Exercises......Page 213
5.1 Quasi-Newton Methods......Page 216
5.1.1 Quasi-Newton Equation......Page 217
5.1.2 Symmetric Rank-One (SR1) Update......Page 220
5.1.3 DFP Update......Page 223
5.1.4 BFGS Update and PSB Update......Page 230
5.1.5 The Least Change Secant Update......Page 236
5.2 The Broyden Class......Page 238
5.3 Global Convergence of Quasi-Newton Methods......Page 244
5.3.1 Global Convergence under Exact Line Search......Page 245
5.3.2 Global Convergence under Inexact Line Search......Page 251
5.4 Local Convergence of Quasi-Newton Methods......Page 253
5.4.1 Superlinear Convergence of General Quasi-Newton Methods......Page 254
5.4.2 Linear Convergence of General Quasi-Newton Methods......Page 263
5.4.3 Local Convergence of Broyden’s Rank-One Update......Page 268
5.4.4 Local and Linear Convergence of DFP Method......Page 271
5.4.5 Superlinear Convergence of BFGS Method......Page 274
5.4.6 Superlinear Convergence of DFP Method......Page 278
5.4.7 Local Convergence of Broyden’s Class Methods......Page 284
5.5.1 Motivation to SSVM Method......Page 286
5.5.2 Self-Scaling Variable Metric (SSVM) Method......Page 290
5.5.3 Choices of the Scaling Factor......Page 292
5.6 Sparse Quasi-Newton Methods......Page 295
5.7 Limited Memory BFGS Method......Page 305
Exercises......Page 314
6.1.1 Trust-Region Methods......Page 316
6.1.2 Convergence of Trust-Region Methods......Page 321
6.1.3 Solving A Trust-Region Subproblem......Page 329
6.2.1 Conic Model......Page 337
6.2.2 Generalized Quasi-Newton Equation......Page 339
6.2.3 Updates that Preserve Past Information......Page 343
6.2.4 Collinear Scaling BFGS Algorithm......Page 347
6.3.1 Tensor Method for Nonlinear Equations......Page 350
6.3.2 Tensor Methods for Unconstrained Optimization......Page 354
Exercises......Page 362
7.1 Introduction......Page 366
7.2 Gauss–Newton Method......Page 368
7.3.1 Motivation and Properties......Page 375
7.3.2 Convergence of Levenberg–Marquardt Method......Page 380
7.4 Implementation of L–M Method......Page 385
7.5 Quasi-Newton Method......Page 392
Exercises......Page 395
8.1 Constrained Optimization Problems......Page 398
8.2 First-Order Optimality Conditions......Page 401
8.3 Second-Order Optimality Conditions......Page 414
8.4 Duality......Page 419
Exercises......Page 422
9.1 Optimality Conditions for Quadratic Programming......Page 424
9.2 Duality for Quadratic Programming......Page 426
9.3 Equality-Constrained Quadratic Programming......Page 432
9.4 Active Set Methods......Page 440
9.5 Dual Method......Page 448
9.6 Interior Ellipsoid Method......Page 454
9.7 Primal-Dual Interior-Point Methods......Page 458
Exercises......Page 464
10.1 Penalty Function......Page 468
10.2 The Simple Penalty Function Method......Page 474
10.3 Interior Point Penalty Functions......Page 479
10.4 Augmented Lagrangian Method......Page 487
10.5 Smooth Exact Penalty Functions......Page 493
10.6 Nonsmooth Exact Penalty Functions......Page 495
Exercises......Page 503
11.1 Feasible Point Methods......Page 506
11.2 Generalized Elimination......Page 515
11.3 Generalized Reduced Gradient Method......Page 522
11.4 Projected Gradient Method......Page 525
11.5 Linearly Constrained Problems......Page 528
Exercises......Page 533
12.1 Lagrange–Newton Method......Page 536
12.2 Wilson–Han–Powell Method......Page 543
12.3 Superlinear Convergence of SQP Step......Page 550
12.4 Maratos Effect......Page 554
12.5 Watchdog Technique......Page 556
12.6 Second-Order Correction Step......Page 558
12.7 Smooth Exact Penalty Functions......Page 563
12.8 Reduced Hessian Matrix Method......Page 567
Exercises......Page 571
13.1 Introduction......Page 574
13.2 Linear Constraints......Page 576
13.3 Trust-Region Subproblems......Page 581
13.4 Null Space Method......Page 584
13.5 CDT Subproblem......Page 593
13.6 Powell–Yuan Algorithm......Page 598
Exercises......Page 607
14.1 Generalized Gradients......Page 610
14.2 Nonsmooth Optimization Problem......Page 620
14.3 The Subgradient Method......Page 622
14.4 Cutting Plane Method......Page 628
14.5 The Bundle Methods......Page 630
14.6 Basic Property of a Composite Nonsmooth Function......Page 633
14.7 Trust Region Method for Composite Nonsmooth Optimization......Page 636
14.8 Nonsmooth Newton’s Method......Page 641
Exercises......Page 647
§1. Test Functions for Unconstrained Optimization Problems......Page 650
§2. Test Functions for Constrained Optimization Problems......Page 651
Bibliography......Page 662
Index......Page 695