Second Edition - xn--vjq503akpco3w.top

1 This is page iiiPrinter: Opaque thisJorge Nocedal Stephen J. WrightNumerical OptimizationSecond EditionThis is pagPrinter: OJorge NocedalStephen J. WrightEECS DepartmentComputer Sciences DepartmentNorthwestern UniversityUniversity of WisconsinEvanston, IL 60208-31181210 West Dayton StreetUSAM adison, WI 53706 Editors:Thomas V. MikoschUniversity of CopenhagenLaboratory of Actuarial MathematicsDK-1017 I. ResnickCornell UniversitySchool of Operations Research andIndustrial EngineeringIthaca, NY M. RobinsonDepartment of Industrial and SystemsEngineeringUniversity of Wisconsin1513 University AvenueMadison, WI 53706 Subject Classification (2000): 90B30, 90C11, 90-01, 90-02 Library of Congress Control Number: 2006923897 ISBN-10: 0-387-30303-0 ISBN-13: 978-0387-30303-1 Printed on acid-free 2006 Springer Science+Business Media, rights reserved.

2 This work may not be translated or copied in whole or in part without the written permissionof the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except forbrief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of informationstorage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology nowknown or hereafter developed is use in this publication of trade names, trademarks, service marks, and similar terms, even if they are notidentified as such, is not to be taken as an expression of opinion as to whether or not they are subject to in the United States of America.

3 (TB/HAM) is page vPrinter: Opaque thisTo Sue, Isabel and MartinandTo Mum and DadThis is page viiPrinter: Opaque thisContentsPrefacexviiPreface to the Second Editionxxi1 Introduction1 MathematicalFormulation ..2 Example:ATransportationProblem ..6 GlobalandLocalOptimization ..6 Stochastic and Deterministic Optimization ..7 Convexity ..7 Optimization Algorithms ..8 NotesandReferences ..92 Fundamentals of Unconstrained ..12viiiCONTENTSR ecognizing a Local .. of ..20 Models for Trust-Region Methods ..25 Scaling .. Line Search.

4 31 The Wolfe Goldstein Conditions ..36 Sufficient Decrease and Backtracking .. sMethod .. s Method with Hessian a Multiple of the Identity ..51 Modified Cholesky Selection ..59A Line Search Algorithm for the Wolfe Conditions ..60 NotesandReferences .. Trust-Region Methods66 Outline of the Trust-Region Based on the Cauchy ..73 Two-Dimensional Subspace Minimization ..89 Convergence of Algorithms Based on Nearly Exact Solutions .. Convergence of Trust-Region Newton ..95 Scaling .. Conjugate Gradient 102 BasicPropertiesoftheConjugateGradientMet hod.

5 107 APracticalFormoftheConjugateGradientMeth od .. 112 Preconditioning .. 118 Practical Preconditioners .. 121 TheFletcher ReevesMethod .. 121 The Polak Ribi`ereMethodandVariants .. 122 Quadratic Termination and Restarts .. 124 BehavioroftheFletcher ReevesMethod .. 125 GlobalConvergence .. 127 NumericalPerformance .. 131 NotesandReferences .. 1336 Quasi-Newton 136 PropertiesoftheBFGSM ethod .. 141 Implementation .. 144 PropertiesofSR1 Updating .. 153 SuperlinearConvergenceoftheBFGSM ethod.

6 160 NotesandReferences .. 162xCONTENTS7 Large-Scale Unconstrained .. 166 Line Search Newton CG Method .. 168 Trust-Region Newton CG Method .. 170 Preconditioning the Trust-Region Newton CG 174 Trust-Region Newton Lanczos .. 176 Limited-MemoryBFGS .. 177 RelationshipwithConjugateGradientMethods .. 181 CompactRepresentationofBFGSU pdating .. 181 UnrollingtheUpdate .. for Partially Separable Functions .. 189 NotesandReferences .. 1918 Calculating Derivative Approximations.

7 195 ApproximatingaSparseJacobian .. 197 Approximating the 201 Approximating a Sparse 204 AnExample .. 205 TheForwardMode .. 207 VectorFunctionsandPartialSeparability .. 212 Calculating Hessians: Forward Mode .. 213 Calculating Hessians: Reverse Mode .. 215 CurrentLimitations .. 216 NotesandReferences .. 2179 Derivative-Free Differences and Noise .. 226 UpdatingtheInterpolationSet .. 227 CONTENTSxiA Method Based on Minimum-Change and Pattern-Search Methods .. 229 Coordinate Search Method.

8 MeadMethod .. 240 NotesandReferences .. 24210 Least-Squares Background .. Least-Squares for Nonlinear Least-Squares Problems .. 254 The Gauss Newton Method .. 254 Convergence of the Gauss Newton Method .. 255 TheLevenberg 258 ImplementationoftheLevenberg 259 ConvergenceoftheLevenberg Distance 265 NotesandReferences .. 26911 Nonlinear 274 Newton sMethodforNonlinearEquations .. 274 InexactNewtonMethods .. 277 Broyden sMethod .. 279 TensorMethods .. PracticalMethods.

9 285 MeritFunctions .. 287 Trust-Region Continuation/HomotopyMethods .. 297 NotesandReferences .. 30212 Theory of Constrained Optimization304 LocalandGlobalSolutions .. 305xiiCONTENTSS moothness .. 310 TwoInequalityConstraints .. TangentConeandConstraintQualifications .. Optimality Conditions .. Optimality Conditions: Proof .. 323 Relating the Tangent Cone and the First-Order Feasible Direction Set ..323A Fundamental Necessary Condition .. 325 Farkas Conditions.

10 330 Second -Order Conditions and Projected Hessians .. AGeometricViewpoint .. 343 NotesandReferences .. 35113 Linear Programming: The Simplex OptimalityandDuality .. 358 Optimality 362 BasesandBasicFeasiblePoints .. LinearAlgebraintheSimplexMethod .. 375 StartingtheSimplexMethod .. 378 DegenerateStepsandCycling .. Presolving .. WhereDoestheSimplexMethodFit?.. 388 NotesandReferences .. 389 CONTENTS xiii14 Linear Programming: Interior-Point Primal-DualMethods.