Convex Optimization 教材习题答案.pdf

《Convex Optimization 教材习题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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


+k=1.Showthat1x1+


+kxk2C.(Thedenitionofconvexityisthatthisholdsfork=2;youmusts

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

3、tlossofgeneralitywecanassumethat16=1.Thenwecanwritey=1x1+(11)(2x2+3x3)where2=2=(11)and2=3=(11).Notethat2;30and2+3111+2===1:1111SinceCisconvexandx2;x32C,weconcludethat2x2+3x32C.Sincethispointandx1areinC,y2C.2.2Showthatasetisconvexifandonlyifitsintersectionwitha

4、nylineisconvex.Showthatasetisaneifandonlyifitsintersectionwithanylineisane.Solution.Weprovetherstpart.Theintersectionoftwoconvexsetsisconvex.There-foreifSisaconvexset,theintersectionofSwithalineisconvex.Conversely,supposetheintersectionofSwithanylineisconvex.Takeanytwodistinctpointsx1a

5、ndx22S.TheintersectionofSwiththelinethroughx1andx2isconvex.Thereforeconvexcombinationsofx1andx2belongtotheintersection,hencealsotoS.2.3Midpointconvexity.AsetCismidpointconvexifwhenevertwopointsa;bareinC,theaverageormidpoint(a+b)=2isinC.Obviouslyaconvexsetismidpointconvex.Itcanbeprovedthat

6、undermildconditionsmidpointconvexityimpliesconvexity.Asasimplecase,provethatifCisclosedandmidpointconvex,thenCisconvex.Solution.Wehavetoshowthatx+(1)y2Cforall2[0;1]andx;y2C.Let(k)bethebinarynumberoflengthk,i.e.,anumberoftheform(k)12k=c12+c22+


+ck2withci2f0;1g,closestto.Bymidpo

7、intconvexity(appliedktimes,recursively),(k)(k)x+(1)y2C.BecauseCisclosed,(k)(k)lim(x+(1)y)=x+(1)y2C:k!12.4ShowthattheconvexhullofasetSistheintersectionofallconvexsetsthatcontainS.(Thesamemethodcanbeusedtoshowthattheconic,orane,orlinearhullofasetSistheinters