ellipsoid_method_notes

EllipsoidMethodS.BoydNotesforEE364b,StanfordUniversityMay26,2014ThesenotesweretakenfromthebookLinearControllerDesign:LimitsofPerformance,byBoydandBarratt[BB91],andedited(atvarioustimesovermanyyears)byStephenBoyd,JoelleSkaf,andNicholasMoehle.Contents1Basicellipsoidalgorithm22Deep-cutellipsoidalgorithm63Ellipsoidalgorithmwithconstraints84Numericalexamples95Ellipsoidmethodforotherproblems12ANotesandreferences141rx(k)rx(k+1)rE(k)E(k+1)g(k)Figure1:Theshadedhalfellipsoid,knowntocontainaminimizer,isenclosedbytheellipsoidofsmallestvolume,denotedE(k+1),centeredatx(k+1).1BasicellipsoidalgorithmEllipsoidmethodidea.Weconsidertheproblemofminimizingaconvexfunctionf:Rn→R.Theellipsoidalgorithmgeneratesa“decreasing”sequenceofellipsoidsinRnthatareguaranteedtocontainaminimizingpoint,usingtheideathatgivenasubgradient(orquasigradient)atapoint,wecanfindahalf-spacecontainingthepointthatisguaranteednottocontainanyminimizersoff,i.e.,acutting-plane.SupposethatwehaveanellipsoidE(k)thatisguaranteedtocontainaminimizeroff.Inthebasicellipsoidalgorithm,wecomputeasubgradientg(k)offatthecenter,x(k),ofE(k).WethenknowthatthehalfellipsoidE(k)∩{z|g(k)T(z−x(k))≤0}containsaminimizeroff.WecomputetheellipsoidE(k+1)ofminimumvolumethatcontainstheslicedhalfellipsoid;E(k+1)isthenguaranteedtocontainaminimizeroff,asshowninfigure1.Theprocessisthenrepeated.Wewillseethatthevolumeoftheellipsoiddecreases,geometrically,whichwillallowustoshowthatthemethodconverges,indeedwithacomplexityestimatethatisgood(atleastintheory).Specialcase:BisectiononR.Whenn=1,thisalgorithmisthestandardbisectionmethodonR.Toseethis,wenotethatanellipsoidinRisnothingbutaninterval.Weevaluatethederivative(orasubgradient)offatthemidpoint(whichisthecenter),anddependingonitssign,theslicedhalfellipsoidiseithertheleftorrighthalfoftheinterval.InR,ahalfellipsoidisalsoaninterval,sotheminimumvolume(inthiscase,length)ellipsoidthatcoversthehalfellipsoidisjusttheinterval,whichhasexactlyhalfthelengthofthepreviousellipsoid.2Ellipsoidmethodupdate.Wenowdescribethealgorithmmoreexplicitly.AnellipsoidEcanbedescribedasE={z|(z−x)TP−1(z−x)≤1}.whereP∈Sn++.Thecenteroftheellipsoidisx,andthematrixPgivesthesizeandshapeororientationofE:thesquarerootsoftheeigenvaluesofParethelengthsofthesemi-axesofE.ThevolumeofEisgivenbyvol(E)=βn√detP,whereβn=πn/2/Γ(n/2+1)isthevolumeoftheunitballinRn.Forn1,theminimumvolumeellipsoidthatcontainsthehalfellipsoid{z|(z−x)TP−1(z−x)≤1,gT(z−x)≤0}isgivenbyE+={z|(z−x+)T(P+)−1(z−x+)≤1},wherex+=x−1n+1P˜g,(1)P+=n2n2−1P−2n+1P˜g˜gTP,(2)and˜g=1qgTPggisanormalizedsubgradient.Let’sgivesomeinterpretationsoftheseequations.Thestepgivenin(1)isinthedirectionofthenegativesubgradient,inthecoordinatesgivenbythematrixP.ThestepP˜gisthesteptotheboundaryofE+,so(1)isastepthatisafraction1/(n+1)totheboundary.From(2),wecanthinkofE(k+1)asslightlythinnerthanE(k)inthedirectiong(k),andslightlyenlargedoverall.Basicellipsoidmethod.Thebasicellipsoidalgorithmis:Ellipsoidmethodgivenaninitialellipsoid(P(0),x(0))containingaminimizeroff.k:=0.repeatComputeasubgradient:g(k)∈∂f(x(k)).Normalizethesubgradient:˜g:=1√g(k)TP(k)g(k)g(k).3Updateellipsoidcenter:x(k+1):=x(k)−1n+1P(k)˜g.Updateellipsoidshape:P(k+1):=n2n2−1P(k)−2n+1P(k)˜g˜gTP(k).k:=k+1.Theellipsoidmethodisnotadescentmethod,sowekeeptrackofthebestpointfound.Wedefinef(k)best=minj=0,...,kf(x(j)).Proofofconvergence.Inthissectionweshowthattheellipsoidalgorithmconverges,i.e.,limk→∞f(k)best=f⋆,providedouroriginalellipsoidE(0),whichwetaketobeaball,i.e.,x(0)=0,P(0)=R2I,containsaminimizingpointinitsinterior.EventhoughE(k+1)canbelargerthanE(k)inthesenseofmaximumsemi-axis(λmax(P(k+1))λmax(P(k))ispossible),itturnsoutthatitsvolumeisless:vol(E(k+1))=nn+1(n+1)/2nn−1(n−1)/2vol(E(k))e−1/2nvol(E(k)),byafactorthatonlydependsonthedimensionn.ThefirstlineissimplecalculationfromtheformulaforupdatingthematrixPthatdescribestheellipsoid(2)andbasicdeterminantidentities.Wesupposethatx⋆∈E(0)andthatf(K)best≥f⋆+ǫ,whereǫ0.Thismeansthatfork=1,...,K,f(x(k))f⋆+ǫ.Theneverypointzexcludediniterations0,...,Khasf(z)≥f⋆+ǫ,sinceatiterationkthefunctionvaluesineachexcludedhalf-spaceareatleastf(x(k)).WedefineG=maxg∈∂f(x),x∈E(0)kgk,asthemaximumlengthofthesubgradientsovertheinitialellipsoid.(Infact,GisaLipschitzconstantforfovertheinitialellipsoid.)ThenintheballB={z|kz−x⋆k≤ǫ/G}.wehavef(z)≤f⋆+ǫ.WeassumewithoutlossofgeneralitythatB⊆E(0),andconsequentlynopointofBwasexcludediniterations1,...,K,sowehaveB⊆E(k).Thus,vol(E(k))≥vol(B),soe−K/2nvol(E(0))≥(ǫ/G)nβn.4ForE(0)={z|kzk≤R}wehavevol(E(0))=Rnβn,so,takinglogs,−K2n+nlogR≥nlogǫG,andthereforeK≤2n2logRGǫ.Thustocomputef⋆witherroratmostǫ,ittakesnomorethan2n2logRG/ǫiterationsoftheellipsoidalgorithm;thisnumbergrowsslowlywithbothdimensionnandaccuracyǫ(atleast,fromthepointofviewofcomplexitytheory).Interpretation.Fromtheinitialellipsoid(aballofradiusR)andtheLipschitzboundonf(i.e.,G),weknowthatouroriginalpointisnomorethanRGsuboptimal.AfterKstepswehaveproducedapointthatisǫsuboptimal.ThustheratioRG/ǫisthefractionalreductioninourignoranceaboutthenumberf⋆.Thecomplexityanalysisabovesaysthatt