文稿文案凸優(yōu)化2 convex optimization ii hw4

Prof.S. Projectionontotheprobabilitysimplex.InthisproblemyouwillworkoutasimplemethodforfindingtheEuclideanprojectionyofx∈RnontotheprobabilitysimplexP={z|z0,1Tz=1}.Hints.Considertheproblemofminimizing(1/2)ky?xk22subjecttoy0,1Ty=1.FormthepartialLagrangian2L(y,ν)=(1/2)ky?xk2+ν(1Ty?2leavingtheconstraint 0implicit.Showthaty=(x?ν1)+minimizesL(y,ν) Minimizingexpected umviolation.Weconsidertheproblemofminimizingthe thevariable, subjecttokxk∞≤wherethedataA∈Rm×nandb∈RmareWeconsideraspecificprobleminstancewithm=3andn=3.TheentriesofA 0EA10,Eb1. Solutionviastochasticsubgradient.Useastochasticsubgradientmethodwithstepsize1/ktocomputeasolutionxstoch,startingfromx=0,withM=1theobjectivevalueobtainedbyxstochusingMonteCarlo,withM=1000samples.Plotthedistributionofmax(b?Axstoch)fromthesesamples.(Inthisplot,pointstotheleftof0correspondtonoviolationoftheinequalities.) ummarginheuristic.Theheuristicxmmisobtainedby izingthemarginintheinequalities,withthecoefficientssettotheirexpectedvalues: subjecttokxk∞≤1.UseMonteCarlowithM=1000samplestoestimatetheobjectivevalue(fortheoriginalproblem)obtainedbyxmm,andplotthedistributionofmax(b?Axmm).Directsolutionofsampledproblem.GenerateM=100samplesofAandb,andsolvetheproblemminimize(1/M)subjecttokxk∞≤

max(bi?Thesolutionwillbedenotedxds.UseMonteCarlowithM=1000samplestoestimatetheobjectivevalue(fortheoriginalproblem)obtainedbyxds,andplotthedistributionofmax(b?Axds). =max(min(x,1),-1)toprojectontothe?∞normUsethecvxfunctionpos()togetthepositivepartfunctionTheclearestcodeforcarryingoutMonteCarlo ysisusesaforloop.Inforloopscanbeveryslow,s etheyareinterpreted.Ourfor-loopimplementationofthesolutiontothisproblemisn’ttooslow,butifyoufindMonteCarlorunsslowonyourmachine,youcanusethe methodbelow,tofindtheempiricaldistributionofmax(b?%loop-MonteCarlowith1000samplesofdataAandbM=1000;noise=0.1;Amtx=repmat(Abar,M,1)+2*noise*rand(M*m,n)-noise;bmtx=repmat(bbar,M,1)+2*noise*rand(M*m,1)-%evaluatemax(b-Ax)for1000fvals_stoch=max(reshape(bmtx-Amtx*x_sto,M)SubgradientmethodforinequalityformSDP.DescribehowtoimplementasubgradientmethodtosolvetheinequalityformSDP cTsubject x1A1+···+ Rn, Rn,Sm,Sm.Generateasmallinstanceoftheproblem(say,withn=4andm=10)andsolveitusingyoursubgradientmethod.CheckyoursolutionusingCVX.Kelley’scutting-nealgorithm.Weconsidertheproblemofminimizingaconvexfunctionf:Rn→RoversomeconvexsetC,assumingwecanevaluatef(x)andfindasubgradientg∈?f(x)foranyx.Supposewehaveevaluatedthefunctionandasubgradientatx(1),...,x(k).Wecanformthepiecewise-linearapproximationf?(k)(x)=

f(x(i))+g(i)T(x?x(i))whichsatisfiesf?(k)(x)≤f(x)forallx.ItfollowsL(k)=inff?(k)(x)≤wherep?=infx∈Cf(x).Sef?(k+1)(x)≥f?(k)(x)forallx,wehaveL(k+1)≥InKelley’scutting-nealgorithm,wesetx(k+1)tobeanypointthatminimizesf?(k)overx∈C.ThealgorithmcanbeterminatedwhenU(k)?L(k)≤?,whereU(k)=mini=1,...,kf(x(i)).maxi=1,...,m(aTix+bi)thatwehaveusedforothernumericalexamples,withCtheunitcube,i.e.,C={x|kxk∞≤1}.Thedatathatdefinestheparticularfunctioncanfoundinthedirectoryofthesubgradientnotesonthecoursewebsite.Youcanstartwithx(1)=0andrunthealgorithmfor40itions.Plotf(x(k)),U(k),L(k)andtheconstantp?(onthesameplot)versusk.Repeatforf(x)=kx?ck2,wherecischosenfromauniformdistributionovertheunitcubeC.(Thesolutiontothisproblemis,ofcourse,x?=c.)Minimumvolumeellipsoidcoveringahalf-ellipsoid.Inthisproblemwederivetheupdateformulasusedintheellipsoidmethod,i.e.,wewilldetermheminimumvolumeellipsoidthatcontainstheintersectionoftheellipsoidE={x∈Rn|(x?xc)P?1(x?xc)≤andtheH={x|gT(x?xc)≤We’llassumethatn>1, eforn=1theproblemisWefirstconsideraspecialcase:Eisaballcenteredattheorigin(P=I,xc=0),andg=?e1(e1thefirstunitvector),soE∩H={x|xTx≤1,x1≥0}.?c??1?caboutthelhroughfirstunitvectore1,itisclear(andnottoohardtoshow)thatE?willhavethesamesymmetry.ThismeansthatthematrixP?isdiagonal,oftheformP?=diag(α,β,β,...,β),andthatxc=γe1.Sonowwehaveonlythreevariablestodetermine:α,β,andγ.ExpresstheThensolvetheoptimizationproblemdirectly,toshow α=(n+1)2 β=n2?1 γ=n+toreducethegeneralcasetothespecialcasesolvedinpart(a).Hint.Findanaffransformationthatmapstheoriginalellipsoidtotheunitball,andgto?e1.Exinwhyminimizingthevolumeinthesetransformedcoordinatesalsominimizesthevolumeintheoriginalcoordinates.EE364bS.BoydEE364bxRnP{z|的得投影yz0,1Tz=1}提示?？紤]最小化(1/2)y的問題。x22服從y0,1Ty=1。形成偏日L(y,ν)=(1/2)y。x22+ν(1Ty.1),y0y=(xν1y0L(y,ν最小化Emax(b滿足x1A?Rm×nb?Rmm3n3Ab（且獨立0.11009/10EA11/20Eb1.10111291/kxx0，每次迭代M=1個次梯度樣本。運行算法5000次迭代。使用估計xstoch獲得M1000max(bAxstoch)（在此圖中，0左側(cè)的點對應(yīng)于不違反不等式。）最小化最大值(EbEx11使用M=1000個樣本的來估計xmm獲得的目標值（針對原始問題），并繪制max(bAxmm)AbM100M1/M)i=1max(bi.Aix)+且x1≤1。該解決方案將表示為xds。使用M=1000個樣本的來估計xds獲得的目標值（針對原始問題），并繪制max(b.Axds)的分布。xmax(min(x,110.1使用cvx函數(shù)pos()得到正部分函數(shù)()+。執(zhí)行分析的最清晰的代碼使用for循環(huán)。在中，for循環(huán)可能非常慢，因為它們是被解釋的。我們解決這個問題的for循環(huán)實現(xiàn)并不太慢，但是如果您發(fā)現(xiàn)在您的計算機上運行緩慢，您可以使用下面所示的無循環(huán)方法來查找max(b.斧頭）。無循環(huán)，具有1000個數(shù)據(jù)A和b樣本M=1000；噪聲=0.1；Amtx=repmat(Abar,M,1)2*噪聲*rand(M*m,n)bmtxrepmat(bbar,M,12**rand(M*m,1)1000max(bAxfvals_stochmax(-Amtx*x_sto,M)SDPSDPcTxx1A1·xnAnB的不等式，x?Rnc?RnA1,...,An?SmB?Sm生成問題的一個小實例（例如，n4m10）CVXCfRnR評估f(x)并找到任何x的次梯度g∈.f(x)。假設(shè)我們已經(jīng)評估了函數(shù)并且1)x,xf.(k