Convex Optimization Solutions Manual

《Convex Optimization Solutions Manual》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ConvexOptimizationSolutionsManualStephenBoydLievenVandenbergheJanuary4,2006Chapter2ConvexsetsExercisesExercisesDenitionofconvexityn2.1LetCRbeaconvexset,withx1;:::;xk2C,andlet1;:::;k2Rsatisfyi0,1+


+k=1.Showthat1x1+


+kxk2C.(Thedenitionofconvexityisthatthis

2、holdsfork=2;youmustshowitforarbitraryk.)Hint.Useinductiononk.Solution.Thisisreadilyshownbyinductionfromthedenitionofconvexset.Weillus-tratetheideafork=3,leavingthegeneralcasetothereader.Supposethatx1;x2;x32C,and1+2+3=1with1;2;30.Wewillshowthaty=1x1+2x2+3x32C

3、.Atleastoneoftheiisnotequaltoone;withoutlossofgeneralitywecanassumethat16=1.Thenwecanwritey=1x1+(11)(2x2+3x3)where2=2=(11)and2=3=(11).Notethat2;30and2+3111+2===1:1111SinceCisconvexandx2;x32C,weconcludethat2x2+3x32C.Sincethispointandx1arein

4、C,y2C.2.2Showthatasetisconvexifandonlyifitsintersectionwithanylineisconvex.Showthatasetisaneifandonlyifitsintersectionwithanylineisane.Solution.Weprovetherstpart.Theintersectionoftwoconvexsetsisconvex.There-foreifSisaconvexset,theintersectionofSwithalineisconvex.Con

5、versely,supposetheintersectionofSwithanylineisconvex.Takeanytwodistinctpointsx1andx22S.TheintersectionofSwiththelinethroughx1andx2isconvex.Thereforeconvexcombinationsofx1andx2belongtotheintersection,hencealsotoS.2.3Midpointconvexity.AsetCismidpointconvexifwhenevertwopo

6、intsa;bareinC,theaverageormidpoint(a+b)=2isinC.Obviouslyaconvexsetismidpointconvex.Itcanbeprovedthatundermildconditionsmidpointconvexityimpliesconvexity.Asasimplecase,provethatifCisclosedandmidpointconvex,thenCisconvex.Solution.Wehavetoshowthatx+(1)y2Cforall2[0;1]a

7、ndx;y2C.Let(k)bethebinarynumberoflengthk,i.e.,anumberoftheform(k)12k=c12+c22+


+ck2withci2f0;1g,closestto.Bymidpointconvexity(appliedktimes,recursively),(k)(k)x+(1)y2C.BecauseCisclosed,(k)(k)lim(x+(1)y)=x+(1)y2C:k!12.4ShowthattheconvexhullofasetSisthein

8、tersectionofallconvexsetsthatcontainS.(Thesamemethodcanbeusedtoshowthattheconic,orane,orlinearhullofasetSistheinters