Artikel werden geladen
Autoren:
Verlag:
Springer-Verlag Weitere Titel dieses Verlages anzeigen
| Preface | xvii | |
| Preface to the Second Edition | xxi | |
| 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 | |
| Stochastic and Deterministic Optimization | 7 | |
| Convexity | 7 | |
| Optimization Algorithms | 8 | |
| Notes and References | 9 | |
| 2 | Fundamentals of Unconstrained Optimization | 10 |
| 2.1 | What Is a Solution? | 12 |
| Recognizing a Local Minimum | 14 | |
| Nonsmooth Problems | 17 | |
| 2.2 | Overview of Algorithms | 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 Identity | 51 | |
| Modified Cholesky Factorization | 52 | |
| Modified Symmetric Indefinite Factorization | 54 | |
| 3.5 | Step-Length Selection Algorithms | 56 |
| Interpolation | 57 | |
| Initial Step Length | 59 | |
| A Line Search Algorithm 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 | Algorithms Based on the Cauchy Point | 71 |
| The Cauchy Point | 71 | |
| Improving on the Cauchy Point | 73 | |
| The Dogleg Method | 73 | |
| Two-Dimensional Subspace Minimization | 76 | |
| 4.2 | Global Convergence | 77 |
| Reduction Obtained by the Cauchy Point | 77 | |
| Convergence to Stationary Points | 79 | |
| 4.3 | Iterative 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 of Trust-Region Newton Methods | 92 |
| 4.5 | Other Enhancements | 95 |
| Scaling | 95 | |
| Trust Regions in Other 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 the Conjugate Gradient Method | 107 | |
| A Practical Form of the Conjugate Gradient Method......................Ill | ||
| Rate of Convergence | 112 | |
| Preconditioning | 118 | |
| Practical Preconditioners | 120 | |
| 5.2 | Nonlinear Conjugate Gradient Methods | 121 |
| The Fletcher-Reeves Method | 121 | |
| The Polak-Ribiere Method and Variants | 122 | |
| Quadratic Termination and Restarts | 124 | |
| Behavior of the Fletcher-Reeves Method | 125 | |
| Global Convergence | 127 | |
| Numerical Performance | 131 | |
| Notes and References | 132 | |
| Exercises | 133 | |
| 6 | Quasi-Newton Methods | 135 |
| 6.1 | The BFGS Method | 136 |
| Properties of the BFGS Method | 141 | |
| Implementation | 142 | |
| 6.2 | The SRI Method | 144 |
| Properties of SRI 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 SRI Method | 160 | |
| Notes and References | 161 | |
| Exercises | 162 | |
| 7 | Large-Scale Unconstrained Optimization | 164 |
| 7.1 | Inexact 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 Limited-Memory Updating | 181 | |
| Compact Representation of BFGS Updating | 181 | |
| Unrolling the Update | 184 | |
| 7.3 | Sparse Quasi-Newton Updates | 185 |
| 7.4 | Algorithms for Partially Separable Functions | 186 |
| 7.5 | Perspectives and Software | 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 | |
| Approximating the Hessian | 201 | |
| Approximating a Sparse Hessian | 202 | |
| 8.2 | Automatic Differentiation | 204 |
| An Example | 205 | |
| The Forward Mode | 206 | |
| The Reverse Mode | 207 | |
| Vector Functions and Partial Separability | 210 | |
| Calculating Jacobians of Vector Functions | 212 | |
| Calculating Hessians: Forward Mode | 213 | |
| Calculating Hessians: Reverse Mode | 215 | |
| Current Limitations | 216 | |
| Notes and References | 217 | |
| Exercises | 217 | |
| 9 | Derivative-Free Optimization | 220 |
| 9.1 | Finite Differences and Noise | 221 |
| 9.2 | Model-Based Methods | 223 |
| Interpolation and Polynomial 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-Squares 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 Problems | 262 | |
| 10.4 | Orthogonal Distance Regression | 265 |
| Notes and References | 267 | |
| Exercises | 269 | |
| 11 | Nonlinear Equations | 270 |
| 11.1 | Local Algorithms | 274 |
| Newtons Method for Nonlinear Equations | 274 | |
| Inexact Newton Methods | 277 | |
| Broydens Method | 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 of Theorem 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 | Duality | 343 |
| Notes and References | 349 | |
| Exercises | 351 | |
| 13 | Linear Programming: The Simplex Method | 355 |
| Linear Programming | 356 | |
| 13.1 | Optimality and Duality | 358 |
| Optimality Conditions | 358 | |
| The Dual Problem | 359 | |
| 13.2 | Geometry of the Feasible Set | 362 |
| Bases and Basic Feasible Points | 362 | |
| Vertices of the Feasible Polytope | 365 | |
| 13.3 | The Simplex Method | 366 |
| Outline | 366 | |
| A Single Step of the Method | 370 | |
| 13.4 | Linear Algebra in the Simplex Method | 372 |
| 13.5 | Other Important Details | 375 |
| Pricing and Selection of the Entering Index | 375 | |
| Starting the Simplex Method | 378 | |
| Degenerate Steps and Cycling | 381 | |
| 13.6 | The Dual Simplex Method | 382 |
| 13.7 | Presolving | 385 |
| 13.8 | Where Does the Simplex Method Fit? | 388 |
| Notes and References | 389 | |
| Exercises | 389 | |
| 14 | Linear Programming: Interior-Point Methods | 392 |
| 14.1 | Primal-Dual Methods | 393 |
| Outline | 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 Practical Algorithm | 411 | |
| Solving the Linear Systems | 411 | |
| 14.3 | Other Primal-Dual Algorithms and Extensions | 413 |
| Other Path-Following Methods | 413 | |
| Potential-Reduction Methods | 414 | |
| Extensions | 415 | |
| 14.4 | Perspectives and Software | 416 |
| Notes and References | 417 | |
| Exercises | 418 | |
| 15 | Fundamentals of Algorithms for Nonlinear Constrained Optimization | 421 |
| 15.1 | Categorizing Optimization Algorithms | 422 |
| 15.2 | The Combinatorial Difficulty of Inequality-Constrained Problems | 424 |
| 15.3 | Elimination of Variables | 426 |
| Simple Elimination using Linear Constraints | 428 | |
| General Reduction Strategies for Linear Constraints | 431 | |
| Effect of Inequality Constraints | 434 | |
| 15.4 | Merit Functions and Filters | 435 |
| Merit Functions | 435 | |
| Filters | 437 | |
| 15.5 | The Maratos Effect | 440 |
| 15.6 | Second-Order Correction and Nonmonotone Techniques | 443 |
| Nonmonotone (Watchdog) Strategy | 444 | |
| Notes and References | 446 | |
| Exercises | 446 | |
| 16 | Quadratic Programming | 448 |
| 16.1 | Equality-Constrained Quadratic Programs | 451 |
| Properties of Equality-Constrained QPs | 451 | |
| 16.2 | Direct Solution of the KKT System | 454 |
| Factoring the Full KKT System | 454 | |
| Schur-Complement Method | 455 | |
| Null-Space Method | 457 | |
| 16.3 | Iterative Solution of the KKT System | 459 |
| CG Applied to the Reduced System | 459 | |
| The Projected CG 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 Algorithm on Strictly Convex QPs | 477 | |
| Updating Factorizations | 478 | |
| 16.6 | Interior-Point Methods | 480 |
| Solving the Primal-Dual System | 482 | |
| Step Length Selection | 483 | |
| A Practical Primal-Dual Method | 484 | |
| 16.7 | The Gradient Projection Method | 485 |
| Cauchy Point Computation | 486 | |
| Subspace Minimization | 488 | |
| 16.8 | Perspectives and Software | 490 |
| Notes and References | 492 | |
| Exercises | 492 | |
| 17 | Penalty and Augmented Lagrangian Methods | 497 |
| 17.1 | The Quadratic Penalty Method | 498 |
| Motivation | 498 | |
| Algorithmic Framework | 501 | |
| Convergence of the Quadratic Penalty Method | 502 | |
| 111 | Conditioning and Reformulations | 505 |
| 17.2 | Nonsmooth Penalty Functions | 507 |
| A Practical tx Penalty Method | 511 | |
| A General Class of Nonsmooth Penalty Methods | 513 | |
| 17.3 | Augmented Lagrangian Method: Equality Constraints | 514 |
| Motivation and Algorithmic Framework | 514 | |
| Properties of the Augmented Lagrangian | 517 | |
| 17.4 | Practical Augmented Lagrangian Methods | 519 |
| Bound-Constrained Formulation | 519 | |
| Linearly Constrained Formulation | 522 | |
| Unconstrained 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 of Practical SQP Methods | 533 |
| IQP and EQP | 533 | |
| Enforcing Convergence | 534 | |
| 18.3 | Algorithmic Development | 535 |
| Handling Inconsistent Linearizations | 535 | |
| Full Quasi-Newton Approximations | 536 | |
| Reduced-Hessian Quasi-Newton Approximations | 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 | |
| SiiQP (Sequential i\ Quadratic Programming) | 549 | |
| Sequential Linear-Quadratic Programming (SLQP) | 551 | |
| A Technique for Updating the Penalty Parameter | 553 | |
| 18.6 | Nonlinear 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 Algorithm | 566 |
| 19.3 | Algorithmic Development | 569 |
| Primal vs. Primal-Dual System | 570 | |
| 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 Algorithm for Solving the Barrier Problem | 578 | |
| Step Computation | 580 | |
| Lagrange Multipliers 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 Properties | 587 |
| Failure of the Line Search Approach | 587 | |
| Modified Line Search Methods | 589 | |
| Global Convergence of the Trust-Region Approach | 589 | |
| 19.8 | Superlinear Convergence | 591 |
| 19.9 | Perspectives and Software | 592 |
| Notes and References | 593 | |
| Exercises | 594 | |
| A Background Material | 598 | |
| A. 1 Elements of Linear Algebra | 598 | |
| Vectors and Matrices | 598 | |
| Norms | 600 | |
| Subspaces | 602 | |
| Eigenvalues, Eigenvectors, and the Singular-Value Decomposition | 603 | |
| Determinant and Trace | 605 | |
| Matrix Factorizations: Cholesky, LU, QR | 606 | |
| Symmetric 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 the Euclidean Space R" | 620 | |
| Convex Sets in R" | 621 | |
| Continuity and Limits | 623 | |
| Derivatives | 625 | |
| Directional Derivatives | 628 | |
| Mean Value Theorem | 629 | |
| Implicit Function Theorem | 630 | |
| Order Notation | 631 | |
| Root-Finding for Scalar Equations | 633 | |
| B A Regularization Procedure | 635 | |
| References | 637 | |
| Index | 653 | |
Accumulation point, see Limit point Active set, 308, 323, 336, 342
Affine scaling
direction, 395, 398, 414
method, 417
Alternating variables method, see also Coordinate search method, 104, 230
Angle test, 41
Applications
design optimization, 1
finance, 7
portfolio optimization, 1, 449-450, 492
transportation, 4
Armijo line search, see Line search, Armijo Augmented Lagrangian function, 423
as merit function, 436
definition, 514
exactness of, 517-518
example, 516
Augmented Lagrangian method, 422, 498, 514-526
convergence, 518-519
framework for, 515
implementation, 519-523
LANCELOT, 175, 519-522
motivation, 514-515
Automatic differentiation, 170, 194
adjoint variables, 208, 209
and graph-coloring algorithms, 212, 216-218
checkpointing, 210
common expressions, 211
computational graph, 205-206, 208, 210,211,213,215
Automatic (cont.)
computational requirements, 206-207,
210,214,216,219
forward mode, 206-207, 278
forward sweep, 206, 208, 210, 213-215, 219
foundations in elementary arithmetic,
194, 204
Hessian calculation
forward mode, 213-215
interpolation formulae, 214-215
reverse mode, 215-216
intermediate variables, 205-209, 211, 212,218
Jacobian calculation, 210-213
forward mode, 212
reverse mode, 212-213
limitations of, 216-217
reverse mode, 207-210
reverse sweep, 208-210, 218
seed vectors, 206, 207, 212, 213, 216
software, 194,210,217
Backtracking, 37, 240
Barrier functions, 566, 583
Barrier method, 563-566
primal, 583
Basic variables, 429
Basis matrix, 429-431
BFGS method, 24, 29, 136-143
damping, 537
implementation, 142-143
properties, 141-142, 161
self-correction, 142
skipping, 143, 537
Bound-constrained optimization, 97,
485-490
BQPD, 490
Broyden class, see Quasi-Newton method,
Broyden class Broyden's method, 273, 274, 284, 285, 302, 634
derivation of, 279-281
limited-memory variants, 283
rate of convergence, 281-283
statement of algorithm, 281
Byrd-Omojokun method, 547, 579
Calculus of variations, 9
Cancellation error, see Floating-point
arithmetic, cancellation Cauchy point, 71-73, 76, 77, 93, 100, 170, 172, 262, 486
calculation of, 71-72, 96
for nonlinear equations, 291-292
role in global convergence, 77-79
Cauchy sequence, 618
Cauchy-Schwarz inequality, 75, 99, 151, 600
Central path, 397-399, 417
for nonlinear problems, 565, 584, 594
neighborhoods of, 399-401, 403, 406, 413
Chain rule, 29, 194, 204, 206-208, 213,
625, 627, 629
Cholesky factorization, 87, 141, 143,
161, 251, 259, 289, 292, 454, 599, 608-609, 617
incomplete, 174
modified, 48, 51-54, 63, 64, 76
bounded modified factorization property, 48
sparse, 412-413
stability of, 53, 617
Classification of algorithms, 422
Combinatorial difficulty, 424
Complementarity condition, 70, 313, 321, 333, 397
strict, 321, 337, 342, 533, 565, 591
Complementarity problems linear (LCP), 415
nonlinear (NCP), 417
Complexity of algorithms, 388-389, 393,
406,415,417
Conditioning, see also Matrix, condition number, 426, 430-432, 616-617
ill conditioned, 29, 502, 514, 586, 616
well conditioned, 616
Cone, 621
Cone of feasible directions, see Tangent cone
Conjugacy, 25, 102
Conjugate direction method, 103
expanding subspace minimization, 106,
172,173
termination of, 103
Conjugate gradient method, 71, 101-132, 166, 170-173, 253, 278
ft-step quadratic convergence, 133
clustering of eigenvalues, 116
effect of condition number, 117
expanding subspace minimization, 112
Fletcher-Reeves, see Fletcher-Reeves
method for reduced system, 459-461
global convergence, 40
Ffestenes-Stiefel, 123
Krylov subspace, 113
modified for indefiniteness, 169-170
nonlinear, 25, 121-131
numerical performance, 131
optimal polynomial, 113
optimal process, 112
Polak-Ribiere, see Polak-Ribiere
method practical version, 111
preconditioned, 118-119, 170, 460
projected, 461-463, 548, 571, 581, 593
rate of convergence, 112
relation to limited-memory, 180
restarts, 124
superlinear convergence, 132
superquadratic, 133
termination, 115, 124
Constrained optimization, 6
nonlinear, 4, 6, 211, 293, 356, 421, 498, 500
Constraint qualifications, 315-320, 333,
338-340, 350
linear independence (LICQ), 320, 321, 323, 339, 341, 358, 464, 503, 517, 533, 557, 565, 591
Mangasarian-Fromovitz (MFCQ),
339-340
Constraints, 2, 307
bounds, 434,519, 520
equality, 305
inequality, 305
Continuation methods for nonlinear equations, 274, 303
application to KKT conditions for
nonlinear optimization, 565
convergence of, 300-301
formulation as initial-value ODE,
297-299
motivation, 296-297
predictor-corrector method, 299-300
zero path, 296-301, 303
divergence of, 300-301
tangent, 297-300
turning point, 296, 297, 300
Convergence, rate of, 619-620
ft-step quadratic, 133
linear, 262, 619, 620
quadratic, 23, 29, 49, 168, 257, 619, 620
sublinear, 29
superlinear, 23, 29, 73, 132, 140, 142, 160, 161, 168, 262-265, 414, 619, 620
superquadratic, 133
Convex combination, 621
Convex hull, 621
Convex programming, 7, 8, 335
Convexity, 7-8
of functions, 8, 16-17, 28, 250
of sets, 8, 28, 352
strict, 8
Coordinate descent method, see
Alternating variables method, 233
Coordinate relaxation step, 431
Coordinate search method, 135, 230-231
CPLEX, 490
Critical cone, 330
Data-fitting problems, 11-12, 248
Degeneracy, 465
of basis, 366, 369, 372, 382
of linear program, 366
Dennis and Moré characterization, 47
Descent direction, 21, 29, 30
DFP method, 139
Differential equations ordinary, 299
partial, 216, 302
Direct sum, 603
Directional derivative, 206, 207, 437,
628-629
Discrete optimization, 5-6
Index
Dual slack variables, 359
Dual variables, see also Lagrange
multipliers, 359
Duality, 350
in linear programming, 359-362
in nonlinear programming, 343-349
weak, 345, 361
Eigenvalues, 84, 252, 337, 599, 603, 613
negative, 77, 92
of symmetric matrix, 604
Eigenvectors, 84, 252, 603
Element function, 186
Elimination of variables, 424
linear equality constraints, 428-433
nonlinear, 426-428
when inequality constraints are present, 434
Ellipsoid algorithm, 389, 393, 417
Error
absolute, 614
relative, 196, 251,252,614,617
truncation, 216
Errors-in-variables models, 265
Feasibility restoration, 439-440
Feasible sequences, 316-325, 332-333, 336
limiting directions of, 316-325, 329, 333
Feasible set, 3, 305, 306, 338
geometric properties of, 340-341
primal, 358
primal-dual, 397, 399, 405, 414
Filter method, 437-440
Filters, 424, 437-440, 575, 589
for interior-point methods, 575
Finite differencing, 170,193-204,216,268, 278
and graph-coloring algorithms, 202-204
and noise, 221
central-difference formula, 194,
196-197, 202,217
forward-difference formula, 195, 196, 202,217
gradient approximation, 195-197
graph-coloring algorithms and, 200-201
Hessian approximation, 201-204
Jacobian approximation, 197-201, 283
First-order feasible descent direction, 310-315
First-order optimality conditions, see
also Karush-Kuhn-Tucker (KKT) conditions, 90, 275, 307-329, 340, 352
derivation of, 315-329
examples, 308-315, 317-319, 321-322
fundamental principle of, 325-326
unconstrained optimization, 14-15, 513
Fixed-regressor model, 248
Fletcher-Reeves method, 102, 121-131
convergence of, 125
numerical performance, 131
Floating-point arithmetic, 216, 614-615, 617
cancellation, 431, 615
double-precision, 614
roundoff error, 195, 217, 251, 615
unit roundoff, 196, 217, 614
Floating-point numbers, 614
exponent, 614
fractional part, 614
Forcing sequence, see Newton's method,
inexact, forcing sequence Function
continuous, 623-624
continuously differentiable, 626, 631
derivatives of, 625-630
differentiable, 626
Lipschitz continuous, 624, 630
locally Lipschitz continuous, 624
one-sided limit, 624
univariate, 625
Functions
smooth, 10, 14, 306-307, 330
Fundamental theorem of algebra, 603
Gauss-Newton method, 254-258, 263, 266, 275
connection to linear least squares, 255
line search in, 254
performance on large-residual problems, 262
Gaussian elimination, 51, 430,455, 609
sparse, 430,433
stability of, 617
with row partial pivoting, 607, 617
Global convergence, 77-92, 261, 274
Global minimizer, 12-13, 16, 17, 502, 503
Global optimization, 6-8, 422
Global solution, see also Global minimizer,
6, 69-70, 89-91, 305, 335, 352
GMRES, 278, 459, 492, 571
Goldstein condition, 36, 48
Gradient, 625
generalized, 18
Gradient projection method, 464,
485-490, 492, 521
Group partial separability, see Partially
separable function, group partially separable
Hessian, 14, 19, 20, 23, 26, 626
average, 138, 140
Homotopy map, 296
Homotopy methods, see Continuation methods for nonlinear equations
Implicit filtering, 240-242
Implicit function theorem, 324, 630-631
Inexact Newton method, see Newton's
method, inexact Infeasibility measure, 437
Inner product, 599
Integer programming, 5, 416
branch-and-bound algorithm, 6
Integral equations, 302
Interior-point methods, see Primal-dual interior-point methods nonlinear, see Nonlinear interior-point method
Interlacing eigenvalue theorem, 613
Interpolation conditions, 223
Invariant subspace, see Partially separable
optimization, invariant subspace Iterative refinement, 463
Jacobian, 246, 254, 256, 269, 274, 324, 395, 504, 627, 630
Karmarkar's algorithm, 389, 393, 417
Karush-Kuhn-Tucker (KKT) conditions, 330, 332, 333, 335-337, 339, 350, 354, 503,517, 520, 528
for general constrained problem, 321
for linear programming, 358-360, 367,
368, 394-415
for linear programming, 394
KNITRO, 490, 525, 583, 592
Krylov subspace, 108
method, 459
L-BFGS algorithm, 177-180, 183
Lagrange multipliers, 310, 330, 333, 337, 339, 341-343, 353, 358, 360, 419, 422
estimates of, 503, 514, 515, 518, 521, 522, 584
Lagrangian function, 90, 310, 313, 320, 329, 330, 336
for linear program, 358, 360
Hessian of, 330, 332, 333, 335, 337, 358
LANCELOT, 520, 525, 592
Lanczos method, 77, 166, 175-176
LAPACK, 607
Least-squares multipliers, 581
Least-squares problems, linear, 250-254
normal equations, 250-251, 255, 259, 412
sensitivity of solutions, 252
solution via QR factorization, 251-252
solution via SVD, 252-253
Least-squares problems, nonlinear, 12, 210
applications of, 246-248
Dennis-Gay-Welsch algorithm,
263-265
Fletcher-Xu algorithm, 263
large-residual problems, 262-265
large-scale problems, 257
scaling of, 260-261
software for, 263, 268
statistical justification of, 249-250
structure, 247, 254
Least-squares problems, total, 265
Level set, 92, 261
Levenberg-Marquardt method, 258-262, 266, 289
as trust-region method, 258-259, 292
for nonlinear equations, 292
implementation via orthogonal transformations, 259-260
inexact, 268
Index
Levenberg-Marquardt (cont.) local convergence of, 262
performance on large-residual problems, 262
lim inf, lim sup, 618-619
Limit point, 28, 79, 92, 99, 502, 503, 618, 620
Limited-memory method, 25, 176-185, 190
compact representation, 181-184
for interior-point method, 575, 597
L-BFGS, 176-180, 538
memoryless BFGS method, 180
performance of, 179
relation to CG, 180
scaling, 178
SRI, 183
two-loop recursion, 178
Line search, see also Step length selection Armijo, 33, 48, 240
backtracking, 37
curvature condition, 33
Goldstein, 36
inexact, 31
Newton's method with, 22-23
quasi-Newton methods with, 23-25
search directions, 20-25
strong Wolfe conditions, see Wolfe
conditions, strong sufficient decrease, 33
Wolfe conditions, see Wolfe conditions Line search method, 19-20, 30-48, 66, 67, 71,230-231,247
for nonlinear equations, 271, 285, 287-290
global convergence of, 287-288
poor performance of, 288-289
Linear programming, 4, 6, 7, 9, 293
artificial variables, 362, 378-380
basic feasible points, 362-366
basis B, 362-368, 378
basis matrix, 363
dual problem, 359-362
feasible polytope, 356
vertices of, 365-366
fundamental theorem of, 363-364
infeasible, 356, 357
nonbasic matrix, 367
primal solution set, 356
slack and surplus variables, 356, 357,
362, 379, 380
splitting variables, 357
standard form, 356-357
unbounded, 356, 357, 369
warm start, 410, 416
Linearly constrained Lagrangian methods, 522-523,527
MINOS, 523, 527
Linearly dependent, 337
Linearly independent, 339, 503, 504, 517, 519, 602
Lipschitz continuity, see also Function, Lipschitz continuous, 80, 93, 256, 257, 261, 269, 276-278, 287, 294
Local minimizer, 12, 14, 273
isolated, 13, 28
strict, 13, 14, 16, 28,517
weak, 12
Local solution, see also Local minimizer, 6, 305-306, 316, 325, 329, 332, 340, 342, 352,513
isolated, 306
strict, 306, 333, 335, 336
strong, 306
Log-barrier function, 417, 597
definition, 583-584
difficulty of minimizing, 584-585
example, 586
ill conditioned Hessian of, 586
Log-barrier method, 498, 584
LOQO, 490, 592
LSQR method, 254, 268, 459, 492, 571
LU factorization, 606-608
Maratos effect, 440-446, 543, 550
example of, 440, 543
remedies, 442
Matlab, 416
Matrix
condition number, 251, 601-602, 604, 610,616
determinant, 154, 605-606
diagonal, 252, 412, 429, 599
full-rank, 298, 300, 504, 609
identity, 599
indefinite, 76
inertia, 55, 454
lower triangular, 599, 606, 607
modification, 574
nonsingular, 325, 337, 601, 612
null space, 298, 324, 337, 430, 432, 603, 608, 609
orthogonal, 251, 252, 337, 432, 599, 604, 609
permutation, 251, 429, 606
positive definite, 15, 16, 23, 28, 68, 76,
337, 599, 603, 609
positive semidefinite, 8, 15, 70, 415, 599
projection, 462
range space, 430, 603
rank-deficient, 253
rank-one, 24
rank-two, 24
singular, 337
sparse, 411,413, 607
Cholesky factorization, 413
symmetric, 24, 68, 412, 599, 603
symmetric indefinite, 413
symmetric positive definite, 608
trace, 154, 605
transpose, 599
upper triangular, 251, 337, 599, 606, 607, 609
Maximum likelihood estimate, 249
Mean value theorem, 629-630
Merit function, see also Penalty function, 435-437, 446 11, 293, 435-436, 513, 540-543, 550
choice of parameter, 543
exact, 435-436
definition of, 435
nonsmoothness of, 513
Fletcher's augmented Lagrangian, 436, 540
for feasible methods, 435
for nonlinear equations, 273, 285-287,
289, 290, 293, 296, 301-303, 505
for SQP, 540-543
Merit functions, 424, 575
Method of multipliers, see Augmented Lagrangian method
MINOS, see also Linearly constrained
Lagrangian methods, 523, 525, 592
Model-based methods for derivative-free optimization, 223-229
minimum Frobenius change, 228
Modeling, 2, 9, 11, 247-249
Monomial basis, 227
MOSEK, 490
Multiobjective optimization, 437
Negative curvature direction, 49, 50, 63,
76, 169-172, 175, 489, 491
Neighborhood, 13, 14, 28, 256, 621
Network optimization, 358
Newton's method, 25, 247, 254, 257, 263
for log-barrier function, 585
for nonlinear equations, 271, 274-277, 281, 283, 285, 287-290, 294, 296, 299, 302
cycling, 285
inexact, 277-279, 288
for quadratic penalty function, 501, 506
global convergence, 40
Hessian-free, 165, 170
in one variable, 84-87, 91, 633
inexact, 165-168, 171,213
forcing sequence, 166-169, 171,277
large scale
LANCELOT, 175
line search method, 49
TRON, 175
modified, 48-49
adding a multiple of I, 51
eigenvalue modification, 49-51
Newton-CG, 202
line search, 168-170
preconditioned, 174-175
trust-region, 170-175
Newton-Lanczos, 175-176, 190
rate of convergence, 44, 76, 92, 166-168,
275-277, 281-282, 620
scale invariance, 27
Noise in function evaluation, 221-222
Nondifferentiable optimization, 511
Nonlinear equations, 197, 210, 213, 633
degenerate solution, 274, 275, 283, 302
examples of, 271-272, 288-289, 300-301
Nonlinear (cont.)
merit function, see Merit function, for
nonlinear equations multiple solutions, 273-274
nondegenerate solution, 274
quasi-Newton methods, see Broyden's method
relationship to least squares, 271-272,
275, 292-293, 302
relationship to optimization, 271
relationship to primal-dual
interior-point methods, 395
solution, 271
statement of problem, 270-271
Nonlinear interior-point method, 423, 563-593
barrier formulation, 565
feasible version, 576
global convergence, 589
homotopy formulation, 565
superlinear convergence, 591
trust-region approach, 578
Nonlinear least-squares, see Least-squares
problems, nonlinear Nonlinear programming, see Constrained
optimization, nonlinear Nonmonotone strategy, 18, 444-446
relaxed steps, 444
Nonnegative orthant, 97
Nonsmooth functions, 6, 17-18, 306, 307, 352
Nonsmooth penalty function, see Penalty function, nonsmooth
Norm dual, 601
Euclidean, 25, 51, 251, 280, 302, 600,
601,605,610
Frobenius, 50, 138, 140, 601
matrix, 601-602
vector, 600-601
Normal cone, 340-341
Normal distribution, 249
Normal subproblem, 580
Null space, see Matrix, null space Numerical analysis, 355
Objective function, 2, 10, 304
One-dimensional minimization, 19, 56
OOPS, 490
OOQP, 490
Optimality conditions, see also First-order optimality conditions, Second- order optimality conditions, 2, 9, 305
for unconstrained local minimizer, 14-17
Order notation, 631-633
Orthogonal distance regression, 265-267
contrast with least squares, 265-266
structure, 266-267
Orthogonal transformations, 251, 259-260
Givens, 259, 609
Householder, 259, 609
Partially separable function, 25, 186-189, 211
automatic detection, 211
definition, 211
Partially separable optimization, 165
BFGS, 189
compactifying matrix, 188
element variables, 187
quasi-Newton method, 188
SRI, 189
Penalty function, see also Merit function, 498
iu 507-513
exact, 422-423, 507-513
nonsmooth, 497, 507-513
quadratic, see also Quadratic penalty method, 422, 498-507, 525-527, 586
difficulty of minimizing, 501-502
Hessian of, 505-506
relationship to augmented Lagrangian, 514
unbounded, 500
Penalty parameter, 435, 436, 498, 500, 501, 507,514, 521,525
update, 511, 512
PENNON, 526
Pivoting, 251,617
Polak-Ribiere method, 122
convergence of, 130
Polak-Ribiere method
numerical performance, 131
Polynomial bases, 226
monomials, 227
Portfolio optimization, see Applications,
portfolio optimization Preconditioners, 118-120
banded, 120
constraint, 463
for constrained problems, 462
for primal-dual system, 571
for reduced system, 460
incomplete Cholesky, 120
SSOR, 120
Preprocessing, see Presolving Presolving, 385-388
Primal interior-point method, 570
Primal-dual interior-point methods, 389, 597
centering parameter, 396, 398, 401, 413
complexity of, 393, 406, 415
contrasts with simplex method, 356, 393
convex quadratic programs, 415
corrector step, 414
duality measure, 395, 398
infeasibility detection, 411
linear algebra issues, 411-413
Mehrotra's predictor-corrector
algorithm, 393, 407-411
path-following algorithms, 399-414
long-step, 399-406
predictor-corrector (Mizuno- Todd-Ye) algorithm, 413
short-step, 413
potential function, 414
Tanabe-Todd-Ye, 414
potential-reduction algorithms, 414
predictor step, 413
quadratic programming, 480-485
relationship to Newton's method, 394, 395
starting point, 410-411
Primal-dual system, 567
Probability density function, 249
Projected conjugate gradient method, see Conjugate gradient method, projected
Projected Hessian, 558
two-sided, 559
Proximal point method, 523
QMR method, 459, 492, 571
QPA, 490
QPOPT, 490
QR factorization, 251, 259, 290, 292, 298, 337, 432, 433, 609-610
cost of, 609
relationship to Cholesky factorization, 610
Quadratic penalty method, see also Penalty function, quadratic, 497, 501-502, 514
convergence of, 502-507
Quadratic programming, 422, 448-492
active-set methods, 467-480
big M method, 473
blocking constraint, 469
convex, 449
cycling, 477
duality, 349, 490
indefinite, 449, 467, 491-492
inertia controlling methods, 491,492
initial working set, 476
interior-point method, 480-485
nonconvex, see Quadratic programming,
indefinite null-space method, 457-459
optimal active set, 467
optimality conditions, 464
phase I, 473
Schur-complement method, 455-456
software, 490
strictly convex, 349, 449, 472,
477-478
termination, 477-478
updating factorizations, 478
working set, 468-478
Quasi-Newton approximate Hessian, 23,
24, 73, 242, 634
Quasi-Newton method, 25, 165, 247, 263, 501, 585
BFGS, see BFGS method, 263
bounded deterioration, 161
Broyden class, 149-152
curvature condition, 137
Quasi-Newton (cont.)
DFP, see DFP method, 190, 264
for interior-point method, 575
for nonlinear equations, see Broyden's method
for partially separable functions, 25
global convergence, 40
large-scale, 165-189
limited memory, see Limited memory
method rate of convergence, 46, 620
secant equation, 24, 137, 139, 263-264, 280, 634
sparse, see Sparse quasi-Newton method
Range space, see Matrix, range space Regularization, 574
Residuals, 11, 245, 262-265, 269
preconditioned, 462
vector of, 18, 197, 246
Restoration phase, 439
Robust optimization, 7
Root, see Nonlinear equations, solution Rootfinding algorithm, see also Newton's method, in one variable, 259, 260, 633
for trust-region subproblem, 84-87
Rosenbrock function
extended, 191
Roundoff error, see Floating-point
arithmetic, roundoff error Row echelon form, 430
SiiQP method, 293, 549
Saddle point, 28, 92
Scale invariance, 27, 138, 141
of Newton's method, see Newton's method, scale invariance Scaling, 26-27, 95-97, 342-343, 585
example of poor scaling, 26-27
matrix, 96
Schur complement, 456, 611
Secant method, see also Quasi-Newton
method, 280, 633, 634
Second-order correction, 442-444, 550
Second-order optimality conditions, 330-337,342,602
for unconstrained optimization, 15-16
necessary, 92, 331
sufficient, 333-336, 517, 557
Semidefinite programming, 415
Sensitivity, 252, 616
Sensitivity analysis, 2, 194, 341-343, 350, 361
Separable function, 186
Separating hyperplane, 327
Sequential linear-quadratic programming
(SLQP), 293, 423, 534
Sequential quadratic programming, 423, 512, 523, 529-560
Byrd-Omojokun method, 547
derivation, 530-533
full quasi-Newton Hessian, 536
identification of optimal active set, 533
IQP vs. EQP, 533
KKT system, 275
least-squares multipliers, 539
line search algorithm, 545
local algorithm, 532
Newton-KKT system, 531
null-space, 538
QP multipliers, 538
rate of convergence, 557-560
reduced-Hessian approximation,
538-540
relaxation constraints, 547
Si iQP method, see Si iQP method step computation, 545
trust-region method, 546-549
warm start, 545
Set
affine, 622
affine hull of, 622
bounded, 620
closed, 620
closure of, 621
compact, 621
interior of, 621
open, 620
relative interior of, 622, 623
Sherman-Morrison-Woodbury formula, 139, 140, 144, 162, 283, 377, 612-613
Simplex method
as active-set method, 388
basis By 365
complexity of, 388-389
cycling, 381-382
lexicographic strategy, 382
perturbation strategy, 381-382
degenerate steps, 372, 381
description of single iteration, 366-372
discovery of, 355
dual simplex, 366, 382-385
entering index, 368, 370, 372, 375-378
finite termination of, 368-370
initialization, 378-380
leaving index, 368, 370
linear algebra issues, 372-375
Phase I/Phase II, 378-380
pivoting, 368
pricing, 368, 370, 375-376
multiple, 376
partial, 376
reduced costs, 368
revised, 366
steepest-edge rule, 376-378
Simulated annealing, 221
Singular values, 255, 604
Singular-value decomposition (SVD), 252,
269, 303, 603-604
Slack variables, see also Linear
programming, slack/surplus variables, 424, 519
SNOPT, 536, 592
Software BQPD, 490
CPLEX, 490
for quadratic programming, 490
IPOPT, 183, 592
KNITRO, 183, 490, 525, 592
L-BFGS-B, 183
LANCELOT, 520, 525, 592
LOQO, 490, 592
MINOS, 523, 525, 592
MOSEK, 490
OOPS, 490
OOQP, 490
PENNON, 526
QPA, 490
QPOPT, 490
SNOPT, 592
TRON, 175
VE09, 490
XPRESS-MP, 490
Sparse quasi-Newton method, 185-186, 190
SRI method, 24, 144, 161
algorithm, 146
for constrained problems, 538, 540
limited-memory version, 177, 181,183
properties, 147
safeguarding, 145
skipping, 145, 160
Stability, 616-617
Starting point, 18
Stationary point, 15, 28, 289, 436, 505
Steepest descent direction, 20, 21, 71, 74
Steepest descent method, 21, 25-27, 31, 73, 95, 585
rate of convergence, 42, 44, 620
Step length, 19, 30
unit, 23, 29
Step length selection, see also Line search, 56-62
bracketing phase, 57
cubic interpolation, 59
for Wolfe conditions, 60
initial step length, 59
interpolation in, 57
selection phase, 57
Stochastic optimization, 7
Stochastic simulation, 221
Strict complementarity, see
Complementarity condition, strict Subgradient, 17
Subspace, 602
basis, 430, 603
orthonormal, 432
dimension, 603
spanning set, 603
Sufficient reduction, 71, 73, 79
Sum of absolute values, 249
Sum of squares, see Least-squares
problems, nonlinear Symbolic differentiation, 194
Symmetric indefinite factorization, 455, 570,610-612
Bunch-Kaufman, 612
Index
Symmetric (cont.) Bunch-Parlett, 611
modified, 54-56, 63
sparse, 612
Symmetric rank-one update, see SRI
method
Tangent, 315-325
Tangent cone, 319, 340-341
Taylor series, 15, 22, 28, 29, 67, 274, 309,
330, 332, 334, 502
Taylor's theorem, 15, 21-23, 80, 123, 138, 167, 193-195, 197, 198, 202, 274, 280, 294, 323, 325, 332, 334, 341, 630
statement of, 14
Tensor methods, 274
derivation, 283-284
Termination criterion, 92
Triangular substitution, 433, 606, 609, 617
Truncated Newton method, see Newton's method, Newton-CG, line-search Trust region boundary, 69, 75, 95,171-173
box-shaped, 19, 293
choice of size for, 67, 81
elliptical, 19, 67, 95, 96, 100
radius, 20, 26, 68, 69, 73, 258, 294
spherical, 95, 258
Trust-region method, 19-20, 69, 77, 79, 80, 82, 87,91,247, 258, 633
contrast with line search method, 20, 66-67
dogleg method, 71, 73-77, 79, 84, 91,
95, 99, 173, 291-293, 548
double-dogleg method, 99
for derivative-free optimization, 225
for nonlinear equations, 271, 273, 285, 290-296
global convergence of, 292-293
local convergence of, 293-296
global convergence, 71, 73, 76-92, 172
local convergence, 92-95
Newton variant, 26, 68, 92
software, 98
Steihaug's approach, 77, 170-173, 489
strategy for adjusting radius, 69
subproblem, 19, 25-26, 68, 69, 72, 73, 76, 77,91,95-97, 258
approximate solution of, 68, 71
exact solution of, 71, 77, 79, 83-92
hard case, 87-88
nearly exact solution of, 95, 292-293
two-dimensional subspace
minimization, 71, 76-77, 79, 84, 95, 98, 100
Unconstrained optimization, 6, 352, 427, 432, 499, 501
of barrier function, 584
Unit ball, 91
Unit roundoff, see Floating-point arithmetic, unit roundoff
Variable metric method, see Quasi-Newton method
Variable storage method, see Limited memory method
VE09, 490
Watchdog technique, 444-446
Weakly active constraints, 342
Wolfe conditions, 33-36, 48, 78, 131, 137, 138, 140-143, 146, 160, 179, 255, 287, 290
scale invariance of, 36
strong, 34, 35, 122, 125, 126, 128, 131, 138, 142, 162, 179
XPRESS-MP, 490
Zoutendijk condition, 38-41, 128, 156, 287
