Numerical Optimization Jorge Nocedal Stephen J. Wright Springer Springer Series in Operations Research Editors: PeterGlynn StephenM.Robinson Springer NewYork Berlin Heidelberg Barcelona HongKong London Milan Paris Singapore Tokyo Jorge Nocedal Stephen J. Wright Numerical Optimization With85Illustrations 1 3 JorgeNocedal StephenJ.Wright ECEDepartment MathematicsandComputer NorthwesternUniversity ScienceDivision Evanston,IL60208-3118 ArgonneNationalLaboratory USA 9700SouthCassAvenue Argonne,IL60439-4844 USA SeriesEditors: PeterGlynn StephenM.Robinson DepartmentofOperationsResearch DepartmentofIndustrialEngineering StanfordUniversity UniversityofWisconsin–Madison Stanford,CA94305 1513UniversityAvenue USA Madison,WI53706-1572 USA CoverillustrationisfromPre-HispanicMexicanStampDesignsbyFrederickV.Field,courtesyofDoverPubli- cations,Inc. LibraryofCongressCataloging-in-PublicationData Nocedal,Jorge. Numericaloptimization/JorgeNocedal,StephenJ.Wright. p. cm.—(Springerseriesinoperationsresearch) Includesbibliographicalreferencesandindex. ISBN0-387-98793-2(hardcover) 1.Mathematicaloptimization. I.Wright,StephenJ.,1960– . II.Title. III.Series. QA402.5.N62 1999 519.3—dc21 99–13263 ©1999Springer-VerlagNewYork,Inc. Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewrittenpermission ofthepublisher(Springer-VerlagNewYork,Inc.,175FifthAvenue,NewYork,NY10010,USA),exceptforbrief excerptsinconnectionwithreviewsorscholarlyanalysis.Useinconnectionwithanyformofinformationstorage andretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynowknownor hereafterdevelopedisforbidden. Theuseofgeneraldescriptivenames,tradenames,trademarks,etc.,inthispublication,eveniftheformerare notespeciallyidentified,isnottobetakenasasignthatsuchnames,asunderstoodbytheTradeMarksand MerchandiseMarksAct,mayaccordinglybeusedfreelybyanyone. ISBN0-387-98793-2 Springer-Verlag NewYork Berlin Heidelberg SPIN10764949 To Our Parents: Rau´l and Concepcio´n Peter and Berenice Preface Thisisabookforpeopleinterestedinsolvingoptimizationproblems.Becauseofthewide (and growing) use of optimization in science, engineering, economics, and industry, it is essentialforstudentsandpractitionersaliketodevelopanunderstandingofoptimization algorithms.Knowledgeofthecapabilitiesandlimitationsofthesealgorithmsleadstoabetter understandingoftheirimpactonvariousapplications,andpointsthewaytofutureresearch onimprovingandextendingoptimizationalgorithmsandsoftware.Ourgoalinthisbook is to give a comprehensive description of the most powerful, state-of-the-art, techniques forsolvingcontinuousoptimizationproblems.Bypresentingthemotivatingideasforeach algorithm,wetrytostimulatethereader’sintuitionandmakethetechnicaldetailseasierto follow.Formalmathematicalrequirementsarekepttoaminimum. Becauseofourfocusoncontinuousproblems,wehaveomitteddiscussionofimportant optimizationtopicssuchasdiscreteandstochasticoptimization.However,thereareagreat manyapplicationsthatcanbeformulatedascontinuousoptimizationproblems;forinstance, findingtheoptimaltrajectoryforanaircraftorarobotarm; identifyingtheseismicpropertiesofapieceoftheearth’scrustbyfittingamodelof theregionunderstudytoasetofreadingsfromanetworkofrecordingstations; viii Preface designingaportfolioofinvestmentstomaximizeexpectedreturnwhilemaintaining anacceptablelevelofrisk; controlling a chemical process or a mechanical device to optimize performance or meetstandardsofrobustness; computingtheoptimalshapeofanautomobileoraircraftcomponent. Everyyearoptimizationalgorithmsarebeingcalledontohandleproblemsthatare much larger and complex than in the past. Accordingly, the book emphasizes large-scale optimizationtechniques,suchasinterior-pointmethods,inexactNewtonmethods,limited- memorymethods,andtheroleofpartiallyseparablefunctionsandautomaticdifferentiation. Ittreatsimportanttopicssuchastrust-regionmethodsandsequentialquadraticprogram- mingmorethoroughlythanexistingtexts,andincludescomprehensivediscussionofsuch “core curriculum” topics as constrained optimization theory, Newton and quasi-Newton methods,nonlinearleastsquaresandnonlinearequations,thesimplexmethod,andpenalty andbarriermethodsfornonlinearprogramming. THE AUDIENCE Weintendthatthisbookwillbeusedingraduate-levelcoursesinoptimization,asof- feredinengineering,operationsresearch,computerscience,andmathematicsdepartments. Thereisenoughmaterialhereforatwo-semester(orthree-quarter)sequenceofcourses. Wehope,too,thatthisbookwillbeusedbypractitionersinengineering,basicscience,and industry,andourpresentationstyleisintendedtofacilitateself-study.Sincethebooktreats anumberofnewalgorithmsandideasthathavenotbeendescribedinearliertextbooks,we hopethatthisbookwillalsobeausefulreferenceforoptimizationresearchers. Prerequisitesforthisbookincludesomeknowledgeoflinearalgebra(includingnu- mericallinearalgebra)andthestandardsequenceofcalculuscourses.Tomakethebookas self-containedaspossible,wehavesummarizedmuchoftherelevantmaterialfromthesear- easintheAppendix.Ourexperienceinteachingengineeringstudentshasshownusthatthe materialisbestassimilatedwhencombinedwithcomputerprogrammingprojectsinwhich thestudentgainsagoodfeelingforthealgorithms—theircomplexity,memorydemands,and elegance—andfortheapplications.Inmostchaptersweprovidesimplecomputerexercises thatrequireonlyminimalprogrammingproficiency. EMPHASIS AND WRITING STYLE Wehaveusedaconversationalstyletomotivatetheideasandpresentthenumerical algorithms.Ratherthanbeingasconciseaspossible,ouraimistomakethediscussionflow inanaturalway.Asaresult,thebookiscomparativelylong,butwebelievethatitcanbe readrelativelyrapidly.Theinstructorcanassignsubstantialreadingassignmentsfromthe textandfocusinclassonlyonthemainideas. Preface ix Atypicalchapterbeginswithanonrigorousdiscussionofthetopicathand,including figuresanddiagramsandexcludingtechnicaldetailsasfaraspossible.Insubsequentsections, thealgorithmsaremotivatedanddiscussed,andthenstatedexplicitly.Themajortheoretical results are stated, and in many cases proved, in a rigorous fashion. These proofs can be skippedbyreaderswhowishtoavoidtechnicaldetails. The practice of optimization depends not only on efficient and robust algorithms, butalsoongoodmodelingtechniques,carefulinterpretationofresults,anduser-friendly software.Inthisbookwediscussthevariousaspectsoftheoptimizationprocess—modeling, optimalityconditions,algorithms,implementation,andinterpretationofresults—butnot withequalweight.Examplesthroughoutthebookshowhowpracticalproblemsareformu- latedasoptimizationproblems,butourtreatmentofmodelingislightandservesmainly to set the stage for algorithmic developments. We refer the reader to Dantzig [63] and Fourer,Gay,andKernighan[92]formorecomprehensivediscussionofthisissue.Ourtreat- mentofoptimalityconditionsisthoroughbutnotexhaustive;someconceptsarediscussed moreextensivelyinMangasarian[154]andClarke[42].Asmentionedabove,wearequite comprehensiveindiscussingoptimizationalgorithms. TOPICS NOT COVERED Weomitsomeimportanttopics,suchasnetworkoptimization,integerprogramming, stochasticprogramming,nonsmoothoptimization,andglobaloptimization.Networkand integeroptimizationaredescribedinsomeexcellenttexts:forinstance,Ahuja,Magnanti,and Orlin[1]inthecaseofnetworkoptimizationandNemhauserandWolsey[179],Papadim- itriouandSteiglitz[190],andWolsey[249]inthecaseofintegerprogramming.Bookson stochasticoptimizationareonlynowappearing;wementionthoseofKallandWallace[139], BirgeandLouveaux[11].Nonsmoothoptimizationcomesinmanyflavors.Therelatively simplestructuresthatariseinrobustdatafitting(whichissometimesbasedonthe(cid:1) norm) 1 aretreatedbyOsborne[187]andFletcher[83].Thelatterbookalsodiscussesalgorithms fornonsmoothpenaltyfunctionsthatariseinconstrainedoptimization;wediscussthese briefly,too,inChapter18.Amoreanalyticaltreatmentofnonsmoothoptimizationisgiven by Hiriart-Urruty and Lemare´chal [137]. We omit detailed treatment of some important topicsthatarethefocusofintensecurrentresearch,includinginterior-pointmethodsfor nonlinearprogrammingandalgorithmsforcomplementarityproblems. ADDITIONAL RESOURCE The material in the book is complemented by an online resource called the NEOS Guide,whichcanbefoundontheWorld-WideWebat http://www.mcs.anl.gov/otc/Guide/ TheGuidecontainsinformationaboutmostareasofoptimization,andpresentsanumberof casestudiesthatdescribeapplicationsofvariousoptimizationalgorithmstoreal-worldprob- x Preface lemssuchasportfoliooptimizationandoptimaldieting.Someofthismaterialisinteractive innatureandhasbeenusedextensivelyforclassexercises. Forthemostpart,wehaveomitteddetaileddiscussionsofspecificsoftwarepackages, andreferthereadertoMore´andWright[173]ortotheSoftwareGuidesectionoftheNEOS Guide,whichcanbefoundat http://www.mcs.anl.gov/otc/Guide/SoftwareGuide/ Users of optimization software refer in great numbers to this web site, which is being constantlyupdatedtoreflectnewpackagesandchangestoexistingsoftware. ACKNOWLEDGMENTS Wearemostgratefultothefollowingcolleaguesfortheirinputandfeedbackonvarious sectionsofthiswork:ChrisBischof,RichardByrd,GeorgeCorliss,BobFourer,DavidGay, Jean-Charles Gilbert, Phillip Gill, Jean-Pierre Goux, Don Goldfarb, Nick Gould, Andreas Griewank,MatthiasHeinkenschloss,MarceloMarazzi,HansMittelmann,JorgeMore´,Will Naylor, Michael Overton, Bob Plemmons, Hugo Scolnik, David Stewart, Philippe Toint, LuisVicente,AndreasWaechter,andYa-xiangYuan.WethankGuanghuiLiu,whoprovided helpwithmanyoftheexercises,andJillLavellewhoassistedusinpreparingthefigures.We alsoexpressourgratitudetooursponsorsattheDepartmentofEnergyandtheNational ScienceFoundation,whohavestronglysupportedourresearcheffortsinoptimizationover theyears. Oneofus(JN)wouldliketoexpresshisdeepgratitudetoRichardByrd,whohastaught himsomuchaboutoptimizationandwhohashelpedhiminverymanywaysthroughout thecourseofhiscareer. FINAL REMARK Intheprefacetohis1987book[83],RogerFletcherdescribedthefieldofoptimization asa“fascinatingblendoftheoryandcomputation,heuristicsandrigor.”Theever-growing realmofapplicationsandtheexplosionincomputingpowerisdrivingoptimizationresearch innewandexcitingdirections,andtheingredientsidentifiedbyFletcherwillcontinueto playimportantrolesformanyyearstocome. JorgeNocedal StephenJ.Wright Evanston,IL Argonne,IL