Nonlinear Parameter Optimization Using R Tools Nonlinear Parameter Optimization Using R Tools John C. Nash TelferSchoolofManagement UniversityofOttawa Thiseditionfirstpublished2014 ©2014JohnWileyandSonsLtd Registeredoffice JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester,WestSussex,PO198SQ,UnitedKingdom Fordetailsofourglobaleditorialoffices,forcustomerservicesandforinformationabouthowtoapplyforper- missiontoreusethecopyrightmaterialinthisbookpleaseseeourwebsiteatwww.wiley.com. TherightoftheauthortobeidentifiedastheauthorofthisworkhasbeenassertedinaccordancewiththeCopy- right,DesignsandPatentsAct1988. Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmitted,in anyformorbyanymeans,electronic,mechanical,photocopying,recordingorotherwise,exceptaspermittedby theUKCopyright,DesignsandPatentsAct1988,withoutthepriorpermissionofthepublisher. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprintmaynotbe availableinelectronicbooks. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbesteffortsinpreparing thisbook,theymakenorepresentationsorwarrantieswithrespecttotheaccuracyorcompletenessofthecontents ofthisbookandspecificallydisclaimanyimpliedwarrantiesofmerchantabilityorfitnessforaparticularpurpose. Itissoldontheunderstandingthatthepublisherisnotengagedinrenderingprofessionalservicesandneither thepublishernortheauthorshallbeliablefordamagesarisingherefrom.Ifprofessionaladviceorotherexpert assistanceisrequired,theservicesofacompetentprofessionalshouldbesought. MATLAB®isatrademarkofTheMathWorks,Inc.andisusedwithpermission.TheMathWorksdoesnotwarrant theaccuracyofthetextorexercisesinthisbook.Thisbook’suseordiscussionofMATLAB®softwareorrelated productsdoesnotconstituteendorsementorsponsorshipbyTheMathWorksofaparticularpedagogicalapproach orparticularuseoftheMATLAB®software. LibraryofCongressCataloging-in-PublicationData Nash,JohnC.,1947- NonlinearparameteroptimizationusingRtools/JohnC.Nash. pagescm Includesbibliographicalreferencesandindex. ISBN978-1-118-56928-3(cloth) 1.Mathematicaloptimization.2.Nonlineartheories.3.R(Computerprogramlanguage)I.Title. QA402.5.N342014 519.60285′5133–dc23 2013051141 AcataloguerecordforthisbookisavailablefromtheBritishLibrary. ISBN:9781118569283 Typesetin10/12ptTimesLTStdbyLaserwordsPrivateLimited,Chennai,India PrintedandboundinSingaporebyMarkonoPrintMediaPteLtd. 1 2014 Thisworkisapartofandisdedicatedtothateffortbythemany community-minded peoplewhocreate,support,promote,andusefree andopensourcesoftware,andwhogenerouslysharetheseideas, withoutwhichRinparticularwouldnotexist. Contents Preface xv 1 Optimizationproblemtasksandhowtheyarise 1 1.1 Thegeneraloptimizationproblem 1 1.2 Whythegeneralproblemisgenerallyuninteresting 2 1.3 (Non-)Linearity 4 1.4 Objectivefunctionproperties 4 1.4.1 Sumsofsquares 4 1.4.2 Minimaxapproximation 5 1.4.3 Problemswithmultipleminima 5 1.4.4 Objectivesthatcanonlybeimpreciselycomputed 5 1.5 Constrainttypes 5 1.6 Solvingsetsofequations 6 1.7 Conditionsforoptimality 7 1.8 Otherclassifications 7 References 8 2 Optimizationalgorithms–anoverview 9 2.1 Methodsthatusethegradient 9 2.2 Newton-likemethods 12 2.3 ThepromiseofNewton’smethod 13 2.4 Caution:convergenceversustermination 14 2.5 DifficultieswithNewton’smethod 14 2.6 Leastsquares:Gauss–Newtonmethods 15 2.7 Quasi-Newtonorvariablemetricmethod 17 2.8 Conjugategradientandrelatedmethods 18 2.9 Othergradientmethods 19 2.10 Derivative-freemethods 19 2.10.1 Numericalapproximationofgradients 19 2.10.2 Approximateanddescend 19 2.10.3 Heuristicsearch 20 2.11 Stochasticmethods 20 2.12 Constraint-basedmethods–mathematicalprogramming 21 References 22 viii CONTENTS 3 Softwarestructureandinterfaces 25 3.1 Perspective 25 3.2 Issuesofchoice 26 3.3 Softwareissues 27 3.4 Specifyingtheobjectiveandconstraintstotheoptimizer 28 3.5 Communicatingexogenousdatatoproblem definitionfunctions 28 3.5.1 Useof“global”dataandvariables 31 3.6 Masked(temporarilyfixed)optimizationparameters 32 3.7 Dealingwithinadmissibleresults 33 3.8 Providingderivativesforfunctions 34 3.9 Derivativeapproximationswhenthereareconstraints 36 3.10 Scalingofparametersandfunction 36 3.11 Normalendingofcomputations 36 3.12 Terminationtests–abnormalending 37 3.13 Outputtomonitorprogressofcalculations 37 3.14 Outputoftheoptimizationresults 38 3.15 Controlsfortheoptimizer 38 3.16 Defaultcontrolsettings 39 3.17 Measuringperformance 39 3.18 Theoptimizationinterface 39 References 40 4 One-parameterroot-findingproblems 41 4.1 Roots 41 4.2 Equationsinonevariable 42 4.3 Someexamples 42 4.3.1 Exponentiallyspeaking 42 4.3.2 Anormalconcern 44 4.3.3 LittlePollyNomial 46 4.3.4 Ahypothequialquestion 49 4.4 Approachestosolving1Droot-findingproblems 51 4.5 Whatcangowrong? 52 4.6 Beingasmartuserofroot-findingprograms 54 4.7 Conclusionsandextensions 54 References 55 5 One-parameterminimizationproblems 56 5.1 Theoptimize()function 56 5.2 Usingaroot-finder 57 5.3 Butwhereistheminimum? 58 5.4 Ideasfor1Dminimizers 59 5.5 Theline-searchsubproblem 61 References 62 CONTENTS ix 6 Nonlinearleastsquares 63 6.1 nls()frompackagestats 63 6.1.1 Asimpleexample 63 6.1.2 Regressionversusleastsquares 65 6.2 Amoredifficultcase 65 6.3 Thestructureofthenls()solution 72 6.4 Concernswithnls() 73 6.4.1 Smallresiduals 74 6.4.2 Robustness–“singulargradient”woes 75 6.4.3 Boundswithnls() 77 6.5 Someancillarytoolsfornonlinearleastsquares 79 6.5.1 Startingvaluesandself-startingproblems 79 6.5.2 Convertingmodelexpressionstosum-of-squaresfunctions 80 6.5.3 Helpfornonlinearregression 80 6.6 MinimizingRfunctionsthatcomputesumsofsquares 81 6.7 Choosinganapproach 82 6.8 Separablesumsofsquaresproblems 86 6.9 Strategiesfornonlinearleastsquares 93 References 93 7 Nonlinearequations 95 7.1 Packagesandmethodsfornonlinearequations 95 7.1.1 BB 96 7.1.2 nleqslv 96 7.1.3 Usingnonlinearleastsquares 96 7.1.4 Usingfunctionminimizationmethods 96 7.2 Asimpleexampletocompareapproaches 97 7.3 Astatisticalexample 103 References 106 8 FunctionminimizationtoolsinthebaseRsystem 108 8.1 optim() 108 8.2 nlm() 110 8.3 nlminb() 111 8.4 Usingthebaseoptimizationtools 112 References 114 9 Add-infunctionminimizationpackagesforR 115 9.1 Packageoptimx 115 9.1.1 Optimizersinoptimx 116 9.1.2 Exampleuseof optimx() 117 9.2 Someotherfunctionminimizationpackages 118 9.2.1 nloptrandnloptwrap 118 9.2.2 trustandtrustOptim 119 x CONTENTS 9.3 Shouldwereplaceoptim()routines? 121 References 122 10 Calculatingandusingderivatives 123 10.1 Whyandhow 123 10.2 Analyticderivatives–byhand 124 10.3 Analyticderivatives–tools 125 10.4 ExamplesofuseofRtoolsfordifferentiation 125 10.5 Simplenumericalderivatives 127 10.6 Improvednumericalderivativeapproximations 128 10.6.1 TheRichardsonextrapolation 128 10.6.2 Complex-stepderivativeapproximations 128 10.7 Strategyandtacticsforderivatives 129 References 131 11 Boundsconstraints 132 11.1 Singlebound:useofalogarithmictransformation 132 11.2 Intervalbounds:Useofahyperbolictransformation 133 11.2.1 Exampleofthetanhtransformation 134 11.2.2 Aflyintheointment 134 11.3 Settingtheobjectivelargewhenboundsareviolated 135 11.4 Anactivesetapproach 136 11.5 Checkingbounds 138 11.6 Theimportanceofusingboundsintelligently 138 11.6.1 Difficultiesinapplyingboundsconstraints 139 11.7 Post-solutioninformationforboundedproblems 139 Appendix11.AFunctiontransfinite 141 References 142 12 Usingmasks 143 12.1 Anexample 143 12.2 Specifyingtheobjective 143 12.3 Masksfornonlinearleastsquares 147 12.4 Otherapproachestomasks 148 References 148 13 Handlinggeneralconstraints 149 13.1 Equalityconstraints 149 13.1.1 Parameterelimination 151 13.1.2 Whichparametertoeliminate? 153 13.1.3 Scalingandcentering? 154 13.1.4 Nonlinearprogrammingpackages 154 13.1.5 Sequentialapplicationofanincreasingpenalty 156 CONTENTS xi 13.2 Sumscaleproblems 158 13.2.1 Usingaprojection 162 13.3 Inequalityconstraints 163 13.4 Aperspectiveonpenaltyfunctionideas 167 13.5 Assessment 167 References 168 14 Applicationsofmathematicalprogramming 169 14.1 Statisticalapplicationsofmathprogramming 169 14.2 Rpackagesformathprogramming 170 14.3 Exampleproblem:L1regression 171 14.4 Exampleproblem:minimaxregression 177 14.5 Nonlinearquantileregression 179 14.6 Polynomialapproximation 180 References 183 15 Globaloptimizationandstochasticmethods 185 15.1 Panoramaofmethods 185 15.2 Rpackagesforglobalandstochasticoptimization 186 15.3 Anexampleproblem 187 15.3.1 MethodSANNfromoptim() 187 15.3.2 PackageGenSA 188 15.3.3 PackagesDEoptimandRcppDE 189 15.3.4 Packagesmco 191 15.3.5 Packagesoma 192 15.3.6 PackageRmalschains 193 15.3.7 Packagergenoud 193 15.3.8 PackageGA 194 15.3.9 Packagegaoptim 195 15.4 Multiplestartingvalues 196 References 202 16 Scalingandreparameterization 203 16.1 Whyscaleorreparameterize? 203 16.2 Formalitiesofscalingandreparameterization 204 16.3 Hobbs’weedinfestationexample 205 16.4 TheKKTconditionsandscaling 210 16.5 Reparameterizationoftheweedsproblem 214 16.6 Scalechangeacrosstheparameterspace 214 16.7 Robustnessofmethodstostartingpoints 215 16.7.1 Robustnessofoptimizationtechniques 218 16.7.2 Robustnessofnonlinearleastsquaresmethods 220 16.8 Strategiesforscaling 222 References 223 xii CONTENTS 17 Findingtherightsolution 224 17.1 Particularrequirements 224 17.1.1 Afewintegerparameters 225 17.2 Startingvaluesforiterativemethods 225 17.3 KKTconditions 226 17.3.1 Unconstrainedproblems 226 17.3.2 Constrainedproblems 227 17.4 Searchtests 228 References 229 18 Tuningandterminatingmethods 230 18.1 Timingandprofiling 230 18.1.1 rbenchmark 231 18.1.2 microbenchmark 231 18.1.3 Calibratingourtimings 232 18.2 Profiling 234 18.2.1 Tryingpossibleimprovements 235 18.3 MorespeedupsofRcomputations 238 18.3.1 Byte-codecompiledfunctions 238 18.3.2 Avoidingloops 238 18.3.3 Packageupgrades-anexample 239 18.3.4 Specializingcodes 241 18.4 Externallanguagecompiledfunctions 242 18.4.1 BuildinganRfunctionusingFortran 244 18.4.2 SummaryofRayleighquotienttimings 246 18.5 Decidingwhenwearefinished 247 18.5.1 Testsforthingsgonewrong 248 References 249 19 LinkingRtoexternaloptimizationtools 250 19.1 MechanismstolinkRtoexternalsoftware 251 19.1.1 Rfunctionstocallexternal(sub)programs 251 19.1.2 Fileandsystemcallmethods 251 19.1.3 Thinclientmethods 252 19.2 Prepackagedlinkstoexternaloptimizationtools 252 19.2.1 NEOS 252 19.2.2 AutomaticDifferentiationModelBuilder(ADMB) 252 19.2.3 NLopt 253 19.2.4 BUGSandrelatedtools 253 19.3 Strategyforusingexternaltools 253 References 254