Convex Optimization 教材习题答案

ConvexOptimizationSolutionsManualStephenBoydLievenVandenbergheJanuary4,2006Chapter2ConvexsetsExercisesExercisesDenitionofconvexity2.1LetCRnbeaconvexset,withx1;:::;xk2C,andlet1;:::;k2Rsatisfyi0,1+


+k=1.Showthat1x1+


+kxk2C.(Thedenitionofconvexityisthatthisholdsfork=2;youmustshowitforarbitraryk.)Hint.Useinductiononk.Solution.Thisisreadilyshownbyinductionfromthedenitionofconvexset.Weillus-tratetheideafork=3,leavingthegeneralcasetothereader.Supposethatx1;x2;x32C,and1+2+3=1with1;2;30.Wewillshowthaty=1x1+2x2+3x32C.Atleastoneoftheiisnotequaltoone;withoutlossofgeneralitywecanassumethat16=1.Thenwecanwritey=1x1+(11)(2x2+3x3)where2=2=(11)and2=3=(11).Notethat2;30and1+2=2+311=1111=1:SinceCisconvexandx2;x32C,weconcludethat2x2+3x32C.Sincethispointandx1areinC,y2C.2.2Showthatasetisconvexifandonlyifitsintersectionwithanylineisconvex.Showthatasetisaneifandonlyifitsintersectionwithanylineisane.Solution.Weprovetherstpart.Theintersectionoftwoconvexsetsisconvex.There-foreifSisaconvexset,theintersectionofSwithalineisconvex.Conversely,supposetheintersectionofSwithanylineisconvex.Takeanytwodistinctpointsx1andx22S.TheintersectionofSwiththelinethroughx1andx2isconvex.Thereforeconvexcombinationsofx1andx2belongtotheintersection,hencealsotoS.2.3Midpointconvexity.AsetCismidpointconvexifwhenevertwopointsa;bareinC,theaverageormidpoint(a+b)=2isinC.Obviouslyaconvexsetismidpointconvex.Itcanbeprovedthatundermildconditionsmidpointconvexityimpliesconvexity.Asasimplecase,provethatifCisclosedandmidpointconvex,thenCisconvex.Solution.Wehavetoshowthatx+(1)y2Cforall2[0;1]andx;y2C.Let(k)bethebinarynumberoflengthk,i.e.,anumberoftheform(k)=c121+c222+


+ck2kwithci2f0;1g,closestto.Bymidpointconvexity(appliedktimes,recursively),(k)x+(1(k))y2C.BecauseCisclosed,limk!1((k)x+(1(k))y)=x+(1)y2C:2.4ShowthattheconvexhullofasetSistheintersectionofallconvexsetsthatcontainS.(Thesamemethodcanbeusedtoshowthattheconic,orane,orlinearhullofasetSistheintersectionofallconicsets,oranesets,orsubspacesthatcontainS.)Solution.LetHbetheconvexhullofSandletDbetheintersectionofallconvexsetsthatcontainS,i.e.,D=\fDjDconvex;DSg:WewillshowthatH=DbyshowingthatHDandDH.FirstweshowthatHD.Supposex2H,i.e.,xisaconvexcombinationofsomepointsx1;:::;xn2S.NowletDbeanyconvexsetsuchthatDS.Evidently,wehavex1;:::;xn2D.SinceDisconvex,andxisaconvexcombinationofx1;:::;xn,itfollowsthatx2D.WehaveshownthatforanyconvexsetDthatcontainsS,wehavex2D.ThismeansthatxisintheintersectionofallconvexsetsthatcontainS,i.e.,x2D.NowletusshowthatDH.SinceHisconvex(bydenition)andcontainsS,wemusthaveH=DforsomeDintheconstructionofD,provingtheclaim.2ConvexsetsExamples2.5Whatisthedistancebetweentwoparallelhyperplanesfx2RnjaTx=b1gandfx2RnjaTx=b2g?Solution.Thedistancebetweenthetwohyperplanesisjb1b2j=kak2.Toseethis,considertheconstructioninthegurebelow.PSfragreplacementsax1=(b1=kak2)ax2=(b2=kak2)aaTx=b2aTx=b1Thedistancebetweenthetwohyperplanesisalsothedistancebetweenthetwopointsx1andx2wherethehyperplaneintersectsthelinethroughtheoriginandparalleltothenormalvectora.Thesepointsaregivenbyx1=(b1=kak22)a;x2=(b2=kak22)a;andthedistanceiskx1x2k2=jb1b2j=kak2:2.6Whendoesonehalfspacecontainanother?GiveconditionsunderwhichfxjaTxbgfxj~aTx~bg(wherea6=0,~a6=0).Alsondtheconditionsunderwhichthetwohalfspacesareequal.Solution.LetH=fxjaTxbgand~H=fxj~aTx~bg.Theconditionsare:H~Hifandonlyifthereexistsa0suchthat~a=aand~bb.H=~Hifandonlyifthereexistsa0suchthat~a=aand~b=b.Letusprovetherstcondition.Theconditionisclearlysucient:if~a=aand~bbforsome0,thenaTxb=)aTxb=)~aTx~b;i.e.,H~H.Toprovenecessity,wedistinguishthreecases.Firstsupposeaand~aarenotparallel.Thismeanswecanndavwith~aTv=0andaTv6=0.Let^xbeanypointintheintersectionofHand~H,i.e.,aT^xband~aTx~b.WehaveaT(^x+tv)=aT^xbforallt2R.However~aT(^x+tv)=~aT^x+t~aTv,andsince~aTv6=0,wewillhave~aT(^x+tv)~bforsucientlylarget0orsucientlysmallt0.Inotherwords,ifaand~aarenotparallel,wecanndapoint^x+tv2Hthatisnotin~H,i.e.,H6~H.Nextsupposeaand~aareparallel,butpointinoppositedirections,i.e.,~a=aforsome0.Let^xbeanypointinH.Then^xta2Hforallt0.Howeverfortlargeenoughwewillhave~aT(^xta)=~aT^x+tkak22~b,so^xta62~H.Again,thisshowsH6~H.ExercisesFinally,weassume~a=aforsome0but~bb.Consideranypoint^xthatsatisesaT^x=b.Then~aT^x=aT^x=b~b,so^x62~H.Theproofforthesecondpartoftheproblemissimilar.2.7Voronoidescriptionofhalfspace.LetaandbbedistinctpointsinRn.Showthatthesetofallpointsthatarecloser(inEuclideannorm)toathanb,i.e.,fxjkxak2kxbk2g,isahalfspace.DescribeitexplicitlyasaninequalityoftheformcTxd.Drawapicture.Solution.Sinceanormisalwaysnonnegative,wehavekxak2kxbk2ifandonlyifkxak22kxbk22,sokxak22kxbk22()(xa)T(xa)(xb)T(xb)()xTx2aTx+aTaxTx2bTx+bTb()2(ba)TxbTbaTa:Therefore,thesetisindeedahalfspace.Wecantakec=2(ba)andd=bTbaTa.Thismakesgoodgeometricsense:thepointsthatareequidistanttoaandbaregivenbyahyperplanewhosenormalisinthedirectionba.2.8WhichofthefollowingsetsSarepolyhedra?