信息论基础与编码 (10).pdf

《信息论基础与编码 (10).pdf》由会员分享，可在线阅读，更多相关《信息论基础与编码 (10).pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、SDP Relaxation for Nonconvex QPWhy?SupposeWi=Pwiwiis optimal.Goal:find a rank-1Wi,such thatTr(Wihjhj)=Tr(Wihjhj)andTr(Wi)=Tr(Wi).?Recall a()=(1,ej,.,ej(K1).WriteTr(Wihjhj)=P|a(j)wi|2?The real-valued complex trig polynomialfi():=X|a()wi|2 0,.fi()=|a()wi|2for some wi.(Riesz-Fejer;spectral factorizatio

2、n)?Integrating outin|a()wi|2=P|a()wi|2yieldsTr(wi(wi)=k wik2=Xkwik2=XTr(wi(wi).?Moreover,Tr(Wihjhj)=P|a(j)wi|2=f(j)=Tr(wi(wi)hjhj)Thus,Wi=wi(wi)ni=1is feasible and has the same objective value asWini=1.The SDP relaxation has a rank-1 solution.24SDP Relaxation for Nonconvex QPWorst-case SDP Approxima

3、tion PerformanceIn general,SDP relaxation for separable homogeneous QCQP is not tight.Example:For anyM 0,considerqp:=minx2+y2s.t.y2 1,x2 Mxy 1,x2+Mxy 1.Notice that the last two constraints of QCQP implyx2 M|x|y|+1,x2 1,which,inlight of the constraintsy2 1,further implyx2 M+1.qp M+2.However,for the S

4、DP relaxationsdp:=minX(11)+X(22)s.t.X(22)1,X(11)MX(12)1,X(22)+MX(12)1,X?0.X=I is clearly a feasible solution,implyingsdp 2.the performance ratioqp/sdpis at least(M+2)/2,which can be arbitrarily large.25SDP Relaxation for Nonconvex QPSpecial Case:Single Group MulticastingWhenn=1(single group),the tra

5、nsmit beamforming problem becomesqp:=minwHnkwk2s.t.wHiw:=XIi|hw|2 1,i=1,.,m,h6=0 Hn(H=CorR),I1 Im=1,.,M z=x+iy(x,y Rn),z=xT iyT|Ii|:number of antennas at receiveri.w=the least norm vector in the exteriorsof ellipsoids.Formulation is“dual”to the max norm over ellipsoids problem considered by NRT99.26

6、SDP Relaxation for Nonconvex QPSDP RelaxationLetZ=zzH(Z?0,rankZ 1)LetHi=PIihh.The SDP relaxation isqp=minTr(Z)s.t.Tr(HiZ)=XIiTr(hhHZ)1,i=1,.,m,Z?0,rankZ 1.sdp:=minTr(W)s.t.Tr(HiW)1,i=1,.,m,W?0.Then0 sdp qp?Csdp(C 1)27SDP Relaxation for Nonconvex QPApproximation Upper&Lower BoundsTheorem 1:qp Csdpwhe

7、re122m2C27m2ifH=R12(3.6)2m C 8mifH=C28SDP Relaxation for Nonconvex QPNumerical experienceSimulation with randomly generatedh(m=8,n=4)shows that both the mean and themaximum of the upper boundqpsdpare lower in theH=Ccase than theH=Rcase.29SDP Relaxation for Nonconvex QPLower Bound:H=RExample:Taken=2,

8、|Ii|=1,hi=?cos(2mi)sin(2mi)?,i=1,.,mandconsidermin kwk2,s.t.|hiw|2 1,i=1,2,.,m.hiuniformly partitions the unit circle.For any QP feas.solnw,isuch thatw hiapproximately,i.e.,their angular spreadiis about2mThis implies1|hiw|cosikwkkhik mkwk kwk2m22 qpm22 W=I is a feas.soln of SDP,sosdp Tr(I)=2Thusqp12

9、2m2sdp30SDP Relaxation for Nonconvex QPUpper Bound:H=RLetWbe an optimal SDP soln,with rankr 2m(suchWexists).Goal:randomly generate a feasible solution wfor QCQP.WriteW=rXk=1wkwk(wk H).Let:=rXk=1wkk,ki.i.d.N(0,1).Then E(Hi)=Tr(HiW)1 i satisfies SDP constraints in expectation.E(kk2)=Tr(W)kkequalssdp=T

10、r(W)in expectation.Question:such thatHi for alliandkk Tr(W)?Facts:P(Hi 0,i?P(|k|2 Tr(W)1 0(Markov ineq.)31SDP Relaxation for Nonconvex QPUnion bound:P?Hi ,i=1,.,m&kk2 Tr(W)?1 mXi=1P?Hi Tr(W)?1 m 10if =3,=9m2so RnsuchHi 9m2,i=1,.,mkk2 3Tr(W)=3sdp.Then w:=miniHiis a feas.soln of QCQP,k wk2=kk2miniHi3s

11、dp/(9m2).Thusqp k wk227m2sdp.32SDP Relaxation for Nonconvex QPComplex Case:H=CProof of upper bound is similar to the real case,but withki.i.d.Nc(0,1)(densitye|k|2)ThenP(Hi 0,isoP?Hi ,i=1,.,m&kk2 Tr(Z)?1 mXi=1P?Hi Tr(W)?1 m43 10if =2,=14m33SDP Relaxation for Nonconvex QPLower Bounds:H=CExample:LetK=d

12、me(soK 2),and leth=?cos2jK,sin2jKei2kK,0,.,0?Twith=jK K+k,j,k=1,.,K.There areK2 mcomplex rank-1 constraints.Letw=(w1,.,wn)T Cnbe an optimal solution of QCQP.WLOG,assume thatw1isreal and write(w1,w2)=(cos,sinej),for some,0,2).Since2k/K,k=1,.,Kand2j/K,j=1,.,Kare uniformly spaced in0,2),jandksuch that?

13、2kK?Kand?2jK2?K.34SDP Relaxation for Nonconvex QPCan show|Re(hw)|=O(1/m),|Im(hw)|=O(1/m),implyingqp=kwk=O(m).However,W=diag1,1,0,.,0is a feasible SDP soln,implyingsdp Tr(W)=2.qp/sdp O(m).35SDP Relaxation for Nonconvex QPExtensionsOne Indefinite Constraint:(m2)and(m)still holds when one of the constr

14、aint matrixHiis indefinite.Quadratic Fractional Objective:The same(m2)and(m)bounds hold formaximizemini=1,.,mwHHiwwHGiw+2subject tokwk2 Pwhich has application to max-min fair downlink beamforming.Low Rank Approximate Solution:Consider the following linear systemTr(AiX)=bi,i=1,2,.,m,X?0.A rank-dappro

15、ximate solution:(m,n,d)bi Tr(AiX)(m,n,d)bi,i=1,2,.,m,X?0.Result:(m,n,d)=1+O(lnm/d),(m,n,d)=O(m2/d).36SDP Relaxation for Nonconvex QPKey Step for the Indefinite CaseLemma 1.For any real numbersi,and i.i.d.exponential random variablesiwith unitvariance,i=1,.,n,there holdsProb(nXi=1i(i 1)0)120,Prob(nXi

16、=1i(i 1)0)120.This settled an open question of Nemirovskii who established a lower bound ofO(1/n).37SDP Relaxation for Nonconvex QPGeometric InterpretationConsider the joint exponentialdistribution onRn+with densityePni=1xi.The mean vector,orthe center of gravity ofRn+isxc:=(1,1,.,1)T.The setH+=(1,2

17、,.,n)T?nXi=1i(i 1)0)represents a half space passingthroughxc.Inequality(3)can be interpreted asfollows:Prob(Rn+H+)e1,for any hyperplaneHpassingthroughxc.38SDP Relaxation for Nonconvex QPConnection with Grunbaums InequalityConsider the uniform distributionover a bounded convex bodyC Rn,then the mean

18、vectorxc=1Vol(C)ZCxdx;then Gr unbaum inequalityVol(C H+)e1Vol(C)mProb(C H+)e139SDP Relaxation for Nonconvex QPEquivalent Probability EstimateThe above probability expression is equivalent to120nXi=1e1iQj6=i?1 ji?1920for any distinctive real valuesi,i=1,.,n.Conjecture(no more):1enXi=1e1iQj6=i?1 ji?e

19、1e,(3)hold for any real valuesi,i=1,.,n.Inequality(3)can be shown to hold forn=2,3.40SDP Relaxation for Nonconvex QPImproved Approximation Bound:bounded phase spreadTheorem 2:H=C.Ifh=pXi=1igi,=1,.,M,for somep 1,i C,gi Cnwithkgik=1and gHigj=0for alli 6=j;i=|i|ejisatisfies,for some0 2,|i j|i,j,thenqp1

20、cos()sdp.41SDP Relaxation for Nonconvex QPMaximization QP with convex constraintsqp:=maxwHkwk2s.t.XIi|hw|2 1,i=1,.,m,sdp:=maxTr(W)s.t.Tr(HiW)1,i=1,.,m,W?0.Thensdp qp?Csdp(0 C 1)42SDP Relaxation for Nonconvex QPApproximation Upper&Lower BoundsTheorem 3:qp CsdpwhereO?1ln(m)?C14ln(m)+2ln(2)ifH=RnO?1ln(

21、m)?C16ln(m)+4ln(100)ifH=Cn43SDP Relaxation for Nonconvex QPSummary(Transmit Beamforming)Motivated by a transmit beamforming application,we have considered separable homogeneousQCQP.We have identified various cases when the SDP relaxation is tight?Individual broadcasting case,m=n?Vandermonde case,ULA

22、,LoS,far-fieldFor single group multicasting(n=1,Hi?0),we have establishedqp Csdp,where122m2C27m2ifH=R12(3.6)2m C 8mifH=CFor bounded phase spread case,C=O(1).IfHi6?0,Ccan be unbounded.Theoretical bounds corroborated by simulations;led to significant performance improvement inmulticasting for practical VDSL channels.44SDP Relaxation for Nonconvex QPSummary(Optimization)Assume Ai,Ai?0,i=0,1,2,.,mBj6?0 indefinite,j=0,1,2,.,dR,d=0R,d=1orC,d=0,1RorC,d 2minwHA0ws.t.wHAiw 1,wHBjw 1(m2)(m)maxwHB0ws.t.wHAiw 1,wHBjw 1(log1m)(log1m)maxmin1imwHAiwwHAiw+2s.t.kwk2 P(m2)(m)N.A.45