凸优化作业答案5

EE364a,Winter2007-08Prof.S.BoydEE364aHomework5solutions4.15RelaxationofBooleanLP.InaBooleanlinearprogram,thevariablexisconstrainedtohavecomponentsequaltozeroorone:minimizecTxsubjecttoAxbxi∈{0,1},i=1,...,n.(1)Ingeneral,suchproblemsareverydifficulttosolve,eventhoughthefeasiblesetisfinite(containingatmost2npoints).Inageneralmethodcalledrelaxation,theconstraintthatxibezerooroneisreplacedwiththelinearinequalities0≤xi≤1:minimizecTxsubjecttoAxb0≤xi≤1,i=1,...,n.(2)WerefertothisproblemastheLPrelaxationoftheBooleanLP(4.67).TheLPrelaxationisfareasiertosolvethantheoriginalBooleanLP.(a)ShowthattheoptimalvalueoftheLPrelaxation(4.68)isalowerboundontheoptimalvalueoftheBooleanLP(4.67).WhatcanyousayabouttheBooleanLPiftheLPrelaxationisinfeasible?(b)ItsometimeshappensthattheLPrelaxationhasasolutionwithxi∈{0,1}.Whatcanyousayinthiscase?Solution.(a)ThefeasiblesetoftherelaxationincludesthefeasiblesetoftheBooleanLP.ItfollowsthattheBooleanLPisinfeasibleiftherelaxationisinfeasible,andthattheoptimalvalueoftherelaxationislessthanorequaltotheoptimalvalueoftheBooleanLP.(b)TheoptimalsolutionoftherelaxationisalsooptimalfortheBooleanLP.4.60Log-optimalinvestmentstrategy.WeconsideraportfolioproblemwithnassetsheldoverNperiods.Atthebeginningofeachperiod,were-investourtotalwealth,redis-tributingitoverthenassetsusingafixed,constant,allocationstrategyx∈Rn,wherex0,1Tx=1.Inotherwords,ifW(t−1)isourwealthatthebeginningofperiodt,thenduringperiodtweinvestxiW(t−1)inasseti.Wedenotebyλ(t)thetotal1returnduringperiodt,i.e.,λ(t)=W(t)/W(t−1).AttheendoftheNperiodsourwealthhasbeenmultipliedbythefactorQNt=1λ(t).Wecall1NNXt=1logλ(t)thegrowthrateoftheinvestmentovertheNperiods.WeareinterestedindetermininganallocationstrategyxthatmaximizesgrowthofourtotalwealthforlargeN.Weuseadiscretestochasticmodeltoaccountfortheuncertaintyinthereturns.Weassumethatduringeachperiodtherearempossiblescenarios,withprobabilitiesπj,j=1,...,m.Inscenarioj,thereturnforassetioveroneperiodisgivenbypij.Therefore,thereturnλ(t)ofourportfolioduringperiodtisarandomvariable,withmpossiblevaluespT1x,...,pTmx,anddistributionπj=prob(λ(t)=pTjx),j=1,...,m.Weassumethesamescenariosforeachperiod,with(identical)independentdistribu-tions.Usingthelawoflargenumbers,wehavelimN→∞1NlogW(N)W(0)!=limN→∞1NNXt=1logλ(t)=Elogλ(t)=mXj=1πjlog(pTjx).Inotherwords,withinvestmentstrategyx,thelongtermgrowthrateisgivenbyRlt=mXj=1πjlog(pTjx).Theinvestmentstrategyxthatmaximizesthisquantityiscalledthelog-optimalin-vestmentstrategy,andcanbefoundbysolvingtheoptimizationproblemmaximizePmj=1πjlog(pTjx)subjecttox0,1Tx=1,withvariablex∈Rn.Showthatthisisaconvexoptimizationproblem.Solution.Actually,there’snotmuchtodointhisproblem.Theconstraints,x0,1Tx=1,areclearlyconvex,sowejustneedtoshowthattheobjectiveisconcave(sinceitistobemaximized).Wecandothatinjustafewsteps:First,notethatlogisconcave,solog(pTjx)isconcaveinx(onthedomain,whichistheopenhalfspace{x|pTjx0}).Sinceπj≥0,weconcludethatthesumofconcavefunctionsmXj=1πjlog(pTjx)isconcave.25.13LagrangianrelaxationofBooleanLP.ABooleanlinearprogramisanoptimizationproblemoftheformminimizecTxsubjecttoAxbxi∈{0,1},i=1,...,n,andis,ingeneral,verydifficulttosolve.Inexercise4.15westudiedtheLPrelaxationofthisproblem,minimizecTxsubjecttoAxb0≤xi≤1,i=1,...,n,(3)whichisfareasiertosolve,andgivesalowerboundontheoptimalvalueoftheBooleanLP.InthisproblemwederiveanotherlowerboundfortheBooleanLP,andworkouttherelationbetweenthetwolowerbounds.(a)Lagrangianrelaxation.TheBooleanLPcanbereformulatedastheproblemminimizecTxsubjecttoAxbxi(1−xi)=0,i=1,...,n,whichhasquadraticequalityconstraints.FindtheLagrangedualofthisproblem.Theoptimalvalueofthedualproblem(whichisconvex)givesalowerboundontheoptimalvalueoftheBooleanLP.ThismethodoffindingalowerboundontheoptimalvalueiscalledLagrangianrelaxation.(b)ShowthatthelowerboundobtainedviaLagrangianrelaxation,andviatheLPre-laxation(5.107),arethesame.Hint.DerivethedualoftheLPrelaxation(5.107).Solution.(a)TheLagrangianisL(x,μ,ν)=cTx+μT(Ax−b)−νTx+xTdiag(ν)x=xTdiag(ν)x+(c+ATμ−ν)Tx−bTμ.Minimizingoverxgivesthedualfunctiong(μ,ν)=(−bTμ−(1/4)Pni=1(ci+aTiμ−νi)2/νiν0−∞otherwisewhereaiistheithcolumnofA,andweadopttheconventionthata2/0=∞ifa6=0,anda2/0=0ifa=0.3Theresultingdualproblemismaximize−bTμ−(1/4)Pni=1(ci+aTiμ−νi)2/νisubjecttoν0,μ0.Inordertosimplifythisdual,weoptimizeanalyticallyoverν,bynotingthatsupνi≥0−(ci+aTiμ−νi)2νi!=(4(ci+aTiμ)ci+aTiμ≤00ci+aTiμ≥0=min{0,4(ci+aTiμ)}.Thisallowsustoeliminateνfromthedualproblem,andsimplifyitasmaximize−bTμ+Pni=1min{0,ci+aTiμ}subjecttoμ0.(b)Wefollowthehint.TheLagrangiananddualfunctionoftheLPrelaxationareL(x,u,v,w)=cTx+uT(Ax−b)−vTx+wT(x−1)=(c+ATu−v+w)Tx−bTu−1Twg(u,v,w)=(−bTu−1TwATu−v+w+c=0−∞otherwise.Thedualproblemismaximize−bTu−1TwsubjecttoATu−v+w+c=0u0,v0,w0,whichisequivalenttotheLagrangerelaxationproblemderivedabove.Wecon-cludethatthetworelaxationsgivethesamevalue.6.2ℓ1-,ℓ2-,andℓ∞-normapproximationbyaconstantvector.Whatisthesolutionofthenormapproximationproblemwithonescalarvariablex∈R,minimizekx1−bk,fortheℓ1-,ℓ2-,andℓ∞-norms?Solution.(a)ℓ2-norm:theaverage1Tb