EE364a Homework 5 solutions

1 EE364a , Winter 2007-08 Prof. S. BoydEE364a Homework 5 of Boolean aBoolean linear program, the variablexis constrainedto have components equal to zero or one:minimizecTxsubject toAx bxi {0,1}, i= 1, .. , n.(1)In general, such problems are very difficult to solve, even though the feasible set isfinite (containing at most 2npoints).In a general method calledrelaxation, the constraint thatxibe zero or one is replacedwith the linear inequalities 0 xi 1:minimizecTxsubject toAx b0 xi 1, i= 1, .. , n.(2)We refer to this problem as theLP relaxationof the Boolean LP ( ). The LPrelaxation is far easier to solve than the original Boolean LP.(a) Show that the optimal value of the lp relaxation ( ) isa lower bound on theoptimal value of the Boolean LP ( ). What can you say about the Boolean LPif the lp relaxation is infeasible?(b) It sometimes happens that the lp relaxation has a solution withxi {0,1}.

2 What can you say in this case?Solution.(a) The feasible set of the relaxation includes the feasible set of the Boolean LP. Itfollows that the Boolean LP is infeasible if the relaxation isinfeasible, and thatthe optimal value of the relaxation is less than or equal to theoptimal value ofthe Boolean LP.(b) The optimal solution of the relaxation is also optimal for the Boolean investment consider a portfolio problem withnassets heldoverNperiods. At the beginning of each period, we re-invest our total wealth, redis-tributing it over thenassets using a fixed, constant, allocation strategyx Rn, wherex 0,1Tx= 1. In other words, ifW(t 1) is our wealth at the beginning of periodt, then during periodtwe investxiW(t 1) in asseti. We denote by (t) the total1return during periodt, , (t) =W(t)/W(t 1). At the end of theNperiods ourwealth has been multiplied by the factorQNt=1 (t).

3 We call1 NNXt=1log (t)thegrowth rateof the investment over theNperiods. We are interested in determiningan allocation strategyxthat maximizes growth of our total wealth for use a discrete stochastic model to account for the uncertaintyin the returns. Weassume that during each period there arempossible scenarios, with probabilities j,j= 1, .. , m. In scenarioj, the return for assetiover one period is given , the return (t) of our portfolio during periodtis a random variable, withmpossible valuespT1x, .. , pTmx, and distribution j=prob( (t) =pTjx), j= 1, .. , assume the same scenarios for each period, with (identical) independent distribu-tions. Using the law of large numbers, we havelimN 1 Nlog W(N)W(0)!= limN 1 NNXt=1log (t) =Elog (t) =mXj=1 jlog(pTjx).In other words, with investment strategyx, the long term growth rate is given byRlt=mXj=1 jlog(pTjx).

4 The investment strategyxthat maximizes this quantity is called thelog-optimal in-vestment strategy, and can be found by solving the optimization problemmaximizePmj=1 jlog(pTjx)subject tox 0,1Tx= 1,with variablex that this is a convex optimization , there s not much to do in this problem. The constraints,x 0,1Tx= 1, are clearly convex, so we just need to show that the objectiveis concave(since it is to be maximized). We can do that in just a few steps: First, note that logis concave, so log(pTjx) is concave inx(on the domain, which is the open halfspace{x|pTjx >0}). Since j 0, we conclude that the sum of concave functionsmXj=1 jlog(pTjx)is relaxation of Boolean linear programis an optimizationproblem of the formminimizecTxsubject toAx bxi {0,1}, i= 1, .. , n,and is, in general, very difficult to solve. In exercise we studied the LP relaxationof this problem,minimizecTxsubject toAx b0 xi 1, i= 1.

5 , n,(3)which is far easier to solve, and gives a lower bound on the optimal value of the BooleanLP. In this problem we derive another lower bound for the Boolean LP, and work outthe relation between the two lower bounds.(a)Lagrangian Boolean LP can be reformulated as the problemminimizecTxsubject toAx bxi(1 xi) = 0, i= 1, .. , n,which has quadratic equality constraints. Find the Lagrange dual of this optimal value of the dual problem (which is convex) givesa lower bound onthe optimal value of the Boolean LP. This method of finding a lower bound onthe optimal value is calledLagrangian relaxation .(b) Show that the lower bound obtained via Lagrangian relaxation , and via the LP re-laxation ( ), are the the dual of the lp relaxation ( ).Solution.(a) The Lagrangian isL(x, , ) =cTx+ T(Ax b) Tx+xTdiag( )x=xTdiag( )x+ (c+AT )Tx bT.

6 Minimizing overxgives the dual functiong( , ) =( bT (1/4)Pni=1(ci+aTi i)2/ i 0 otherwisewhereaiis theith column ofA, and we adopt the convention thata2/0 = ifa6= 0, anda2/0 = 0 ifa= resulting dual problem ismaximize bT (1/4)Pni=1(ci+aTi i)2/ isubject to 0, order to simplify this dual, we optimize analytically over , by noting thatsup i 0 (ci+aTi i)2 i!=(4(ci+aTi )ci+aTi 00ci+aTi 0= min{0,4(ci+aTi )}.This allows us to eliminate from the dual problem, and simplify it asmaximize bT +Pni=1min{0, ci+aTi }subject to 0.(b) We follow the hint. The Lagrangian and dual function of the lp relaxation areL(x, u, v, w) =cTx+uT(Ax b) vTx+wT(x 1)= (c+ATu v+w)Tx bTu 1 Twg(u, v, w) =( bTu 1Tw ATu v+w+c= 0 dual problem ismaximize bTu 1 Twsubject toATu v+w+c= 0u 0, v 0, w 0,which is equivalent to the Lagrange relaxation problem derived above.)))

7 We con-clude that the two relaxations give the same 1-, 2-, and -norm approximation by a constant is the solution of thenorm approximation problem with one scalar variablex R,minimizekx1 bk,for the 1-, 2-, and -norms?Solution.(a) 2-norm: the average1Tb/m.(b) 1-norm: the (or a) median of the coefficients ofb.(c) -norm: the midrange point (maxbi minbi) to additional a matrixX=XT Rn npartitioned asX="A BBTC#,whereA Rk k. If detA6= 0, the matrixS=C BTA 1 Bis called theSchurcomplementofAinX. Schur complements arise in many situations and appear inmany important formulas and theorems. For example, we have detX= detAdetS.(You don t have to prove this.)(a) The Schur complement arises when you minimize a quadraticform over some ofthe variables. Letf(u, v) = [uTvT]X[uTvT]T, whereu Rk. Letg(v) be theminimum value offoveru, ,g(v) = infuf(u, v).

8 Of courseg(v) can be .Show that ifA 0, we haveg(v) =vTSv.(b) The Schur complement arises in several characterizationsof positive definitenessor semidefiniteness of a block matrix. As examples we have the following threetheorems: X 0 if and only ifA 0 andS 0. IfA 0, thenX 0 if and only ifS 0. X 0 if and only ifA 0,BT(I AA ) = 0 andC BTA B 0, whereA is the pseudo-inverse ofA. (C BTA Bserves as a generalization of theSchur complement in the case whereAis positive semidefinite but singular.)Proveoneof these theorems. (You can choose which one.)(c) Recognizing Schur complements often helps to represent nonlinear convex con-straints as linear matrix inequalities (LMIs). Consider the functionf(x) = (Ax+b)T(P0+x1P1+ +xnPn) 1(Ax+b)whereA Rm n,b Rm, andPi=PTi Rm m, with domaindomf={x Rn|P0+x1P1+ +xnPn 0}.This is the composition of the matrix fractional function andan affine mapping,and so is convex.

9 Give an LMI representation ofepif. That is, find a symmetricmatrixF(x, t), affine in (x, t), for whichx domf, f(x) t F(x, t) (a)IfA 0, theng(v) = havef(u, v) =uTAu+2vTBu+vTCv. IfA 0, we can minimizefoverubysetting the gradient with respect touequal to zero. We obtainu (v) = A 1Bv,andg(v) =f(u (v), v) =vT(C BTA 1B)v=vTSv.(b)Positive definite and semidefinite block matrices. X 0if and only ifA 0andS 0. Thenf(u, v)>0 for all non-zero (u, v), and in particular,f(u,0) =uTAu >0 for all non-zerou(hence,A 0), andf( A 1Bv, v) =vT(C BTA 1B)v >0 (hence,S=C BTA 1B 0). This proves the onlyif prove the if part, we have to show that ifA 0 andS 0, thenf(u, v)>0 for all nonzero (u, v) (that is, for allu,vthat are not both zero).Ifv6= 0, then it follows from (a) thatf(u, v) infuf(u, v) =vTSv > 0 andu6= 0,f(u,0) =uTAu >0. IfA 0, thenX 0if and only ifS part (a) we know that ifA 0, then infuf(u, v) =vTSv.

10 IfS 0,thenf(u, v) infuf(u, v) =vTSv 0for allu,v, and henceX 0. This proves the if prove the only if -part we note thatf(u, v) 0 for all (u, v) implies thatinfuf(u, v) 0 for allv, ,S 0. X 0if and only ifA 0,BT(I AA ) = 0,C BTA B Rk kwithrank(A) =r. Then there exist matricesQ1 Rk r,Q2 Rk (k r)and an invertible diagonal matrix Rr rsuch thatA=hQ1Q2i" 00 0#hQ1Q2iT,and [Q1Q2]T[Q1Q2] =I. The matrix"Q1Q200 0I# Rn nis nonsingular, and therefore"A BBTC# 0 "Q1Q200 0I#T"A BBTC#"Q1Q200 0I# 06 0QT1B00QT2 BBTQ1 BTQ2C 0 QT2B= 0," QT1 BBTQ1C# have 0 if and only ifA 0. It can be verified thatA =Q1 1QT1, I AA = 0 Q2QT2B= (I A A)B= , since is invertible," QT1 BBTQ1C# 0 0, C BTQ1 1QT1B=C BTA B 0.(c) The epigraph offis the set of points (x, t) that satisfyP0+x1P1+ +xnPn 0and(Ax+b)T(P0+x1P1+ +xnPn) 1(Ax+b) the second result of part (b), we can write the second inequality as"t(Ax+b)T(Ax+b)P0+x1P1+ +xnPn# a linear matrix inequality in the variablesx,t, , a convex Formulate the following optimization problems as semidefinite programs.