numerical optimization

Optimization is an important tool used in decision science and for the analysis of physical systems used in engineering. One can trace its roots to the Calculus of Variations and the work of Euler and Lagrange. This natural and reasonable approach to mathematical programming covers numerical methodsJ. Frederic Bonnans. J. Charles GilbertClaude Lemarechal. Claudia A. SagastizabalTheoretical and Practical AspectsSecond editionWith 52 FiguresSpringerJ. Frederic bonnansJ. Charles GilbertCentre de Mathematiques AppliqueesINRIA RocquencourtEcole polytechniqueBP10591128 Palaiseau78153 Le Chesnayfrancfrancec-mail: Frederic. Bonnans@inria. frc-mail: Jcan- Charles Gilbert@inria.frClaude lemarechalClaudia A. SagastizabalINRIA Rhone-AlpesOn leave from INRIA Rocquencourt655, avenue de EuropeCorrespondence toMontbonnotIMPA38334 Saint Ismier110, Estrada dona castorinafrance460-320 Jardim Botanicoe-mail: Claude, Lemarechal@inria. frRio de janeiro-RJBrazile-mail: sagastiz@impa. brOriginal French edition"Optimisation Numerique"was published by Springer-VerlagBerlin Heidelberg, 1997.Mathematics Subject Classification(2000): 65K1o, 90-08, 90-01, 90CXXLibrary of Congress Control Number: 2006930998ISBN: 3-540-35445-X Springer-Verlag Berlin Heidelberg New YorkThis work is subjcct to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the GermanCopyright Law of September 9, 1965, in its current version, and permission for use must alwaysbe obtained from Springer. Violations are liable for prosecution under the German Copyright LawSpringer-Verlag Berlin Heidelberg New Yorkber of Bertelsmann Springer Science+BC Springer-Verlag Berlin Heidelberg 2006The use of general descriptive names, registered names, trademarks, etc. in this publication donot imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general usedesign: Erich Kirchner, HeidelTypesetting by the authors using a ETeX macro packagePrinted on acid-free paperPrefaceThis book is entirely devoted to numerical algorithms for optimization, theirtheoretical foundations and convergence properties, as well as their implementation, thcir usc, and other practical aspccts. The aim is to familiarizethe reader with these numerical algorithms: understanding their behaviourin practice, properly using existing software libraries, adequately designingand implementing"home-made"methods correctly diagnosing the causesof possible difficulties. Expecled readers are engineers. Master or Ph.D.students. confirmed researchers, in applied mathematics or from various otherdisciplines where optimization is a needOur aim is therefore not to give most accurate results in optimization, norto detail the latest refinements of such and such method. First of all. little issaid concerning optimization theory itself (optimality conditions, constraint.qualification, stability theory). As for algorithms, we limit ourselves most ofthe time to stable and well-established material. Throughout we keep as aleading thread the actual practical value of optimization methods, in terms oftheir efficiency to solve real-world problems. Nevertheless, serious attention ispaid to the theoretical properties of optimization methods this book is mainlybascd upon theorems Bcsidcs, somc ncw and promising rcsults or approachescould not be completely discarded; they are also presented, generally in theform of special sections, mainly aimed at orienting the reader to the relevant.bibliographyAn introductory chapter gives some generalities on optimization and it-erative algorithms. It contains in particular Motivating examples, rankingfrom meteorological forecast to power production management; they illus-trate the large field of branches where optimization finds its applicationsThfts, rather indcpcndent of cach other. The firstdevoted to algorithms for unconstrained optimization which, in addition totheir direct usefulness, are a basis for more complex problems. The secondpart concerns rather special methods, applicable when the usual differentiability assumptions are not satisfied. Such methods appear in the decompo-silion of large-scale problens and the relaxation of combinatorial problelmsNonlinearly constrained optimization forms the third part, substantially moretcchnical, as the subjcct is still in evolution. Finally, the fourth part gives adeep account of the more recent interior point methods, originally designedI’ refacefor the simpler problens of linear anld quadratic programing, and whoseapplication to more general situations is the subject of active researchThis book is a translated and improved version of the monograph [43written in French. The French monograph was used as the textbook of anintensive two week course given several times by the authors, both in franceand abroad. Each topic was prcscntcd from a thcorctical point of vicw inmorning lectures. The afternoons were devoted to implementation issues andrelated computational work. The conception of such a course is due to J -BHiriart-Urruty, to whom the authors are deeply indebtedFinally, three of the authors express their warm gratitude to ClaudeLemarechal for having given the impetus to this new work by providing afirst English versiNotes on this revised edition. Besides minor corrections. the presentversiOn contains substantial changes with respect to the Iirst editioN. Firstof all, (simplified but) nontrivial application problems have been insertedThey involve the typical operations to be performed when one is faced with arcal-lifc application: modelling, choice of mcthodolog y and somc thcorcticalwork to motivate it, computcr implementation. Such computational cxcrciscshelp getting a better underst anding of optimization met hods beyond theirtheoretical description, by addressing important features to be taken intoaccount when passing to implementation of any numerical algorithmIn addilion, Che theorelical background in Part I now includes a discusion on global convergence, and a section on the classical pivotal approachto quadratic programming. Part II has been completely reorganized and ex-pandcd. The introductory chaptcr, on basic subdifferential calculus and duality theory, has two examples of nonsmooth functions that appear often inpractice and serve as motivation (pointwise maximum and dual functionsA new section on convergence results for bundle methods has been addedThe chapter on applicalions of llOlSinooth optinnizaliOl, previously focusingon decomposition of complex problems via Lagrangian duality, describes alsoextensions of bundle methods for handling varying dimensions, for solvingconstrained problems, and for solving generalized equations. Also, a briefcommented revicw of cxisting softwarc for nonlincar optimization hasbccnadded in part ilFinallythereaderwillfindadditionalinformationathttp://www-rocqinria.fr/gilbert/bgls. The page gathers the data for running the testproblems, various optimization codes, including an SQP solver (in Matlaband pieces of soltware that solve the computational exercisesParis. Grenoble. rio de janeiroJFrederic bonnansMay 2006. Charles GilbertClaude lemarechalClaudiu A. SayuslizdbulTable of contentsPreliminaries1 General Introduction1. 1 Genera. lities on Optimization1.1.1 The problem1.1.2 Classilicali1.2 Motivation and Examples1.2.1 Molecular biology1.2.2 Meteorology3334556891.2.3 Trajectory of a Dccpwatcr Vchicle1.2.4 Optimization of Power Management1.3 General Principles of Resolution1.4 Convergence: Global Aspects121.5 Convergence: Local Aspects1.6 Computing the gradientBibliographical comments19Part I Unconstrained problems2 Basic methods252.1 Existence Questions252.2 Optimality Conditions262.3 First -O2.3.1 Gauss-Seide272.3.2 Method of Successive Approximations, or GradientMethod2.4 Link with tle general de24.1 Choosing the1Nom……292.4.2Chorm302.5 Stccpcst-Dcscent Method302.6 ImpleBibliographical Comments35VIll Table of contents3 Line-Searches3.1 General sche373.2 Computing the New t33 Optimal stepsize( for the record only)..……423.4 Modern line-search: Wolfe,s rule3.5 Other Line-Searches: Goldstein and Price, Armijo3.5.1 Goldstein and price473.5.2Ar43.5.3 Remark on the Choice of Constants3.6 Implementation Considerations4Bibliographical Commcnts4 Newtonian methods514.1 Preliminaries514.2 Forcing Global Convergence4.3 Alleviating thc Mcthod4.4 Quasi-Newton Methods4.5 Global Convergence4.6 LocaI Convergence: Generalities594.7 Local Convergence: BFGS61Bibliographical Coillinents5 Conjugate gradient,675.1 Outline of Conjugate gradient675.2 Developing the Metho695.3 Computing the Direction705.4 The AlgorithIn Seen as an Orthogonalization Process705.5 Application to Non-Quadratic Functions725.6 Rclation with Quasi-Ncwton74Bibliographical Comments6 Special Methods.......6.1 Trust -R776.1. 1 The Elementary Problem6.1.2 Thc Elementary Mcchanism: Curvilinear Scarch796.1.3 Incidence on the Sequence x86.2 Least-Squares Problems: Gauss-Newton826.3 Large-Scale Problems: Limited-Memory Quasi-Newton6.4wto6.5 Quadratic Programming6.5.1 The basic mechanism86.5.2 The solution algorithm6.5.3 ConvergenceBibliographical comments....9Table of contents7 A Case Study: Seismic Reflection Tomography7.1 Modellin977.2 Computation of the Rcflcction Points997.3 Gradient of the traveltime.1007.4 The Least-Squares Problem to Solve.1017.5 Solving the Seismic Refection Tomography Problem102General Conclusion103Part II Nonsmooth Optimization8 Introduction to Nonsmooth Optimization1098.1 First Elements of Convex Analysis1098.2 Lagrangian Relaxation and dualit8.2.1 Primal-Dual relations1118.2.2 Back to the Primal. Recovering Primal Solutions... 1138. 3 Two Convex Nondiffcrcntiablc Functions1168. 3. 1 Finite minimax Problems1168.3.2 Dual Functions in Lagrangian Duality179 Some Methods in Nonsmooth Optimization1199. 1 Why special meth1199.2 Descent methods1209.2.1 Steepest-Descent Met hoc12l9.2.2 Stabilization. A Dual Approach. The e-subdifferential 1249.3 Two Black-Box Method1269.3.1 Subgradient methods1279.3.2 Cutting-Planes Method13010 Bundle Methods. The Quest for Descent13710.1 Stabilization. A Primal Approach10.2 Some ExaMples of Stabilized Problens14010.3 Penalized Bundle methods14110.3.1 A Trip to the dual14410.3.2 Managing the Bundle. Aggregation14710.3.3 Updating the Penalization ParameterReversal forms1510.3.4 Convergence Analysis.1541 Applications of Nonsmooth Optimization16111.1 Divide to conquer. Decomposition mcthods..,.,16111.1.1 Price Decomposition1631. 1. 2 Resource Decomposition16711.1.3 Variable Partitioning or Benders Decomposition... 16911.1.4 OCher Decomposition Methods171Table of contents11.2 Tralspassing Frontier17211.2.1 Dynamic Bundle methods17311.2.2 Constrained Bundle mcthods11.2.3 Bundle Methods for Generalized Equations18012 Computational Exercises18312.1 Building Prototypical NSo Black Boxes12.1.1 The Function MAXQUAD12.12 The Function MAXANAL·……18412.2 Implementation of Some NSO Methods12.3 Running the Codes18612.4 lmproving the bundle Implementation18712.5 Decomposition Application187Part III Newton's Methods in Constrained Optimization13 Background,19713.1 Differential Calculus⊥9713.2 Existence and Uniqueness of solutions19913.3 First-Order Optimality Conditions13.4 Second-Order Optimality Conditions13.5 Speed of Convergence.20313.6 Projection onto a Closed Convex Set..2053.7 Thc Nowton mcthod13.8 The Hanging Chain Project I.208213Xercises14 Local Mcthods for Problcms with Equality Constraints. 21514.1 Newton’ s Method14.2 Adapted Decompositions of IR14.3 Local Analysis of Newton's Method22714.4 Computation of the Newton Step23014.5 Reduced Hessian Algorith23514.6 A Comparison of the Algorithms24314.7 The Hanging Chain Project II..,,,,,,,245250E25115 Local Methods for Problems with Equality and InequalityConstraints25515.1 The SQP Al25615.2 Primal-Dual Quadratic Convergence25915.3 Primal Superlinear Convergence264