Levenberg-Marquardt algorithms Trust Region algorithms

1 levenberg -MarquardtalgorithmsvsTrustRegi onalgorithmsFrankVandenBerghenIRIDIA,Uni versit e 12, 2004 For anin-depthexplanationandmorereferencesab outthissubject,seemy thesis, ,availableat: fvandenb/ 'sassumethatwe want to ndx , theminimumof theobjective functionF(x) :<n!<.Letus writetheTaylordevelopment limitedto thedegree2 ofFaroundxk:F(xk+ ) Qk( ) =F(xk) +gtk +12 tBk withQk( ), thequadraticalapproximationofF(x) ,thegradient ofF(x) ,anapproximationof therealhessianmatrixHkofF(x) ,therealhessianmatrixofF(x) themoment, we willassumethatBk:= kofQ( ) is:rQ( k) =gk+Bk k=0()Bk k= gk(1)Equation1 is calledtheequationof theNewtonStep ,theNewton'smethod to ndtheminimumx ofF(x) is:1. Setk= 0. Setx0= solveBk k= gk(goto theminimumof thecurrent quadraticalapproximationofF).3. setxk+1=xk+ k4. Incrementk. Stopifgk 0 otherwise,go to 'smethod is VERY fast:whenxkis closetox (whenwe areneartheoptimum)thismethod hasquadraticalconvergencespeed:kxk+1 x k< kxk x k2with <1.

2 Unfortunately, it does NOTalways convergeto theminimumx ofF(x). To haveconvergence,we needto be surethatBkis always positive de nite, (x) is always :Bkmustbe positive de niteto have want thesearch direction kto be a descent direction=) Tg <0(2)Takingthevalueofgfrom(1)andputtingit in (2),we have: TB <0, TB >0(3)TheEquation(3)says thatBkmustalways be positive de ,we mustalways constructtheBkmatrixso thatit is a positive de niteapproximationofHk, therealHessianmatrixofF(x). TheNewton'sAlgorithmcannotusenegative curvature(whenHknegative de nite)insideF(x). See gure1 : positive/negative curvatureof a functionf(x) :<!<Onepossibility to solve thisproblemis to takeBk=I(I=identity matrix),which is a verybadapproximationof theHessianHbutwhich is always positive de willsimplyhave k= gk. We willsimplyfollow theslope. Thisalgorithmis calledthe\steepestdescent al-gorithm".

3 It is haslinearspeedof convergence:kxk+1 x k< kxk x kwith3 <1 (problemis when = 0:99).Anotherpossibility, if we don'thaveHkpositive de nite,is to useinsteadBnew;k=Hk+ Iwith beinga verybignumber,such thatBnew;kis positive de solve, as usual,theNewtonStepequation(seeequation( 1)):Bnew;k k= gk,(Hk+ I) k= gk(4)Choosinga highvaluefor has2 e (insideequationBnew;k=Hk+ I) willbecomenegligibleandwe will nd,as searchdirection,\thesteepestdescent step".2. Thestepsizek kkis , onlytheabove secondpoint is canbe proventhat,if we imposeaproper limitationonthestepsizek kk< k, we maintainglobalconvergenceevenifBkis aninde ( kis calledthetrustregionradius).In trustregionalgorithmthesteps kare: kis thesolutionofQ( k) = min Q( ) subjecttok k< k(5)TheoldLevenberg-Marquardtalgorithmus esa techniquewhich adaptsthevalueof theiterationwas successful(F(xk+ k)<F( k)),we decrease to exploitmorethecurvatureinformationcontai nedinsideHk.

4 If thepreviousiterationwas unsuccessful(F(xk+ k)>F( k)),thequadraticmodeldon't t mustthenonlyusethe\basic"gradient willincrease in ordertofollow closelythegradient (\steepestdescent algorithm").Thisoldalgorithmis thebasefortheexplanationoftheupdateof thetrustregionradius kin intermediatevalueof , we willthus follow a directionwhich is a mixtureof the\steepestdescent step"andthe\NewtonStep".Thisdirectionis basedona perturbatedHessianmatrixBnew;kandcansome timebe disastrous(Thereis nogeometricalmeaningof theperturbation IonHk).Whena negative curvatureis encountered(Hknegative de nite): Newton'sMethod fail. levenberg -Marquardtalgorithmsarefollowin ga perturbatedandapproximative directionof research kbasedonanarbitraryperturbationofHk( kis thesolutionof equation(4):(Hk+ I) k= gk). Trustregionalgorithmswillperforma longstep(k kk= k) and\move"quicklyto amoreinterestingarea(seeequation(5))Trus tRegionalgorithmwillthus exhibitbetterperformanceseach timea negative curvatureisencounteredandhave thus , thecomputationof kforTrustRegionalgorithminvolves a constrainedmini-mizationof a quadraticsubjectto onenon-linearconstraint (seeequation(5)).

5 Thisis notatrivialproblemto solve at of Trustregionalgorithmsis equation(5)canbe computedverye cientlyusingthefastalgorithmfromMor onelastpoint which muststillbe taken into account: How canwe obtainHk? Usually,we don'thave be usuallyconstructediterativelybasedoninfo rmationgatheredfromoldevaluationsF(xj) forj= 1; : : : ; k. Iterative constructionofHkcanbe basedon: Thewell-knownBFGS formulae:Each updateis fastto computebutwe getpoor approximationofHk. Multivariatepolynomialinterpolation:Each updateis getverypreciseHk. Finitedi erenceapproximation:Verypoor quality: numericalinstability summarize: levenberg -MarquardtalgorithmsandTrustreg ionalgorithmsarebothNewtonStep-basedmeth ods(theyarecalled\RestrictedNewtonStepme thods").Thustheybothexhibitsquadraticals peedof convergencenearx . Whenwe arefarfromthesolution(xkfarfromx ), we canencountera negative curvature(Hknegative de nite).

6 If thishappens, levenberg -Marquardtalgorithm swillslow downdramatically. In opposition,TrustRegionMethods willperforma verylongstep kand\move" quicklyto a good valuefor hasbeenfound(Thisis becauseonoldcomputerstheupdateofHkis verytimeconsuming,so we want to avoidit).ModernLevenberg-Marquardtalgori thmsareupdat-ingiterativelyHkat everyiterationskbuttheyarestillenableto follow a negative curvatureinsidethefunctionF(x). Thesteps kremainsthus of poor quality comparedto summarizeagain:TrustRegionMethods areanevolutionof areableto follow thenegative curvatureof theobjective doso andarethus slower.