INSEAD Library

Includes bibliographical references and index

Digitized

Springer Series in Operations Research Numerical Optimization Contents Preface Preface to the Second Edition xvii 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 ? ....................................................................................................................................................... 12 2.1 What Is a Solution 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 .................................... 111 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 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 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 Newton's Method for Nonlinear Equations ................................................... 274 Inexact Newton Methods ............................................................................... 277 Broyden's 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 ................................................................................ 16.6 Interior-Point Methods ..................................................................................... Solving the Primal-Dual System .................................................................. Step Length Selection ................................................................................... A Practical Primal-Dual Method .................................................................. 16.7 The Gradient Projection Method ..................................................................... Cauchy Point Computation ........................................................................... Subspace Minimization ................................................................................. 16.8 Perspectives and Software ............................................................................... Notes and References ............................................................................................... Exercises ................................................................................................................... 478 480 482 483 484 485 486 488 490 492 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 Ill Conditioning and Reformulations ............................................................ 505 17.2 Nonsmooth Penalty Functions ......................................................................... 507 A Practical l1 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 Sl 1 QP (Sequential l1 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 Rn .................................................................................................... 620 Convex Sets in Rn .......................................................................................... 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 References Index 635 637 653