### Transcription of EE364a Homework 3 solutions - Stanford Engineering …

1 **EE364a** , Winter 2007-08 Prof. S. BoydEE364a **Homework** 3 , .. , fn:R Rbe given continuous functions. Weconsider the problem of approximatingf0as a linear combination off1, .. , fn. Forx Rn, we say thatf=x1f1+ +xnfnapproximatesf0with tolerance >0 overthe interval [0, T] if|f(t) f0(t)| for 0 t T. Now we choose a fixed tolerance >0 and define theapproximation widthas the largestTsuch thatfapproximatesf0over the interval [0, T]:W(x) = sup{T||x1f1(t) + +xnfn(t) f0(t)| for 0 t T}.Show thatWis show thatWis quasiconcave we show that the sets{x|W(x) }areconvex for all . We haveW(x) if and only if x1f1(t) + +xnfn(t) f0(t) for allt [0, ). Therefore the set{x|W(x) }is an intersection of infinitely manyhalfspaces (two for eacht), hence a convex of Gaussian cumulative distribution cumulative distribu-tion function of a Gaussian random variable,f(x) =1 2 Zx e t2/2dt,is log-concave. This follows from the general result that theconvolution of two log-concave functions is log-concave.]

2 In this problem we guide you through a simpleself-contained proof thatfis log-concave. Recall thatfis log-concave if and only iff (x)f(x) f (x)2for allx.(a) Verify thatf (x)f(x) f (x)2forx 0. That leaves us the hard part, which isto show the inequality forx <0.(b) Verify that for anytandxwe havet2/2 x2/2 +xt.(c) Using part (b) show thate t2/2 ex2/2 xt. Conclude thatZx e t2/2dt ex2/2Zx e xtdt.(d) Use part (c) to verify thatf (x)f(x) f (x)2forx derivatives offaref (x) =e x2/2/ 2 ,f (x) = xe x2/2/ 2 .1(a)f (x) 0 forx 0.(b) Sincet2/2 is convex we havet2/2 x2/2 +x(t x) =xt x2 is the general inequalityg(t) g(x) +g (x)(t x),which holds for any differentiable convex function, appliedtog(t) =t2 (easier?) way to establisht2/2 x2/2 +xtis to note thatt2/2 +x2/2 xt= (1/2)(x t)2 just movex2/2 xtto the other side.(c) Take exponentials and integrate.(d) This basic inequality reduces to xe x2/2Zx e t2/2dt e ,Zx e t2/2dt e x2/2 follows from part (c) becauseZx e xtdt=e x2 Show that the functionf(X) =X 1is matrix convex onSn++.

3 Must show that for arbitraryv Rn, the functiong(X) =vTX convex inXonSn++. This follows from example Consider the optimization problemminimizef0(x1, x2)subject to 2x1+x2 1x1+ 3x2 1x1 0, x2 a sketch of the feasible set. For each of the following objective functions, givethe optimal set and the optimal (a)f0(x1, x2) =x1+x2.(b)f0(x1, x2) = x1 x2.(c)f0(x1, x2) =x1.(d)f0(x1, x2) = max{x1, x2}.(e)f0(x1, x2) =x21+ feasible set is shown in the (1,0)(2/5,1/5)(0,1)(a)x = (2/5,1/5).(b) Unbounded below.(c)Xopt={(0, x2)|x2 1}.(d)x = (1/3,1/3).(e)x = (1/2,1/6). This is optimal because it satisfies 2x1+x2= 7/6>1,x1+3x2=1, and f0(x ) = (1,3)is perpendicular to the linex1+ 3x2= [P. Parrilo]Symmetries and convex {Q1, .. , Qk} Rn nisa group, , closed under products and inverse. We say that the functionf:Rn RisG-invariant, orsymmetric with respect toG, iff(Qix) =f(x) holds for allxandi= 1, .. , k. We definex= (1/k)Pki=1 Qix, which is the average ofxover define thefixed subspaceofGasF={x|Qix=x, i= 1.}

4 , k}.(a) Show that for anyx Rn, we havex F.(b) Show that iff:Rn Ris convex andG-invariant, thenf(x) f(x).3(c) We say the optimization problemminimizef0(x)subject tofi(x) 0, i= 1, .. , misG-invariant if the objectivef0isG-invariant, and the feasible set isG-invariant,which meansf1(x) 0, .. , fm(x) 0 = f1(Qix) 0, .. , fm(Qix) 0,fori= 1, .. , k. Show that if the problem is convex andG-invariant, and thereexists an optimal point, then there exists an optimal point inF. In other words,we can adjoin the equality constraintsx Fto the problem, without loss ofgenerality.(d) As an example, supposefis convex and symmetric, ,f(P x) =f(x) for everypermutationP. Show that iffhas a minimizer, then it has a minimizer of theform 1. (This means to minimizefoverx Rn, we can just as well minimizef(t1) overt R.)Solution.(a) We first observe that when you multiply eachQiby some fixedQj, you get apermutation of theQi s:QjQi=Q (i), i= 1, .. , k,where is a permutation. This is a basic result in group theory, but it s easyenough for us to show it.

5 First we note that by closedness, eachQjQiis equalto someQs. Now suppose thatQjQi=QkQi=Qs. Multiplying byQ 1ion theright, we see thatQj=Qk. Thus the mapping from the indexito the indexsisone-to-one, , a we haveQjx= (1/k)kXi=1 QjQix= (1/k)kXi=1Q (i)x= (1/k)kXi=1 Qix= holds forj, so we havex F.(b) Using convexity and invariance off,f(x) (1/k)kXi=1f(Qix) = (1/k)kXi=1f(x) =f(x).4(c) Supposex is an optimal solution. Thenx is feasible, withf0(x ) =f0((1/k)kXi=1 Qix) (1/k)kXi=1f0(Qix)=f0(x ).Thereforex is also optimal.(d) Supposex is a minimizer off. Letx= (1/n!)PPP x , where the sum is overall permutations. Sincexis invariant under any permutation, we conclude thatx= 1for some R. By Jensen s inequality we havef(x) (1/n!)XPf(P x ) =f(x ),which shows thatxis also a simple an explicit solution of each of the following LPs.(a)Minimizing a linear function over an affine toAx= distinguish three possibilities. The problem is infeasible (b6 R(A)). The optimal value is.

6 The problem is feasible, andcis orthogonal to the nullspace ofA. We candecomposecasc=AT + c,A c= 0.( cis the component in the nullspace ofA;AT is orthogonal to the nullspace.)If c= 0, then on the feasible set the objective function reduces to aconstant:cTx= TAx+ cTx= optimal value is Tb. All feasible **solutions** are optimal. The problem is feasible, andcis not in the range ofAT( c6= 0). The problemis unbounded (p = ). To verify this, note thatx=x0 t cis feasible forallt; astgoes to infinity, the objective value decreases summary,p = + b6 R(A) Tb c=AT for some (b)Minimizing a linear function over a toaTx b,wherea6= problem is always feasible. The vectorccan be decomposed intoa component parallel toaand a component orthogonal toa:c=a + c,withaT c= 0. If >0, the problem is unbounded below. Choosex= ta, and lettgo toinfinity:cTx= tcTa= t aTa andaTx b= taTa b 0for larget, soxis feasible for larget. Intuitively, by going very far in thedirection a, we find feasible points with arbitrarily negative objectivevalues.

7 If c6= 0, the problem is unbounded below. Choosex=ba t cand lettgoto infinity. Ifc=a for some 0, the optimal value iscTab= summary, the optimal value isp =( bc=a for some 0 otherwise.(c)Minimizing a linear function over a tol x u,wherelandusatisfyl objective and the constraints are separable: The objective is asum of termscixi, each dependent on one variable only; each constraint dependson only one variable. We can therefore solve the problem by minimizing overeach component ofxindependently. The optimalx iminimizescixisubject to theconstraintli xi ui. Ifci>0, thenx i=li; ifci<0, thenx i=ui; ifci= 0,then anyxiin the interval [li, ui] is optimal. Therefore, the optimal value of theproblem isp =lTc++uTc ,wherec+i= max{ci,0}andc i= max{ ci,0}.6(d)Minimizing a linear function over the probability to1Tx= 1, x happens if the equality constraint is replaced by an inequality1Tx 1?We can interpret this LP as a simple portfolio optimization problem. The vectorxrepresents the allocation of our total budget over different assets, withxithefraction invested in asseti.)

8 The return of each investment is fixed and given by ci, so our total return (which we want to maximize) is cTx. If we replace thebudget constraint1Tx= 1 with an inequality1Tx 1, we have the option of notinvesting a portion of the total the components ofcare sorted in increasing order withc1=c2= =ck< ck+1 havecTx c1(1Tx) =cminfor all feasiblex, with equality if and only ifx1+ +xk= 1,x1 0, .. , xk 0,xk+1= =xn= conclude that the optimal value isp =c1=cmin. In the investment interpre-tation this choice is quite obvious. If the returns are fixed and known, we investour total budget in the investment with the highest we replace the equality with an inequality, the optimal value is equal top = min{0, cmin}.(Ifcmin 0, we make the same choice forxas above. Otherwise, we choosex= 0.)(e)Minimizing a linear function over a unit box with a total budget to1Tx= ,0 x 1,where is an integer between 0 andn. What happens if is not an integer (butsatisfies 0 n)? What if we change the equality to an inequality1Tx ?

9 First consider the case of integer . Supposec1 ci 1< ci= =c = =ck< ck+1 optimal value isc1+c2+ +c , the sum of the smallest elements optimal if and only ifx1= =xi 1= 1,xi+ +xk= i+ 1,xk+1= =xn= is not an integer, the optimal value isp =c1+c2+ +c +c1+ ( ).In the case of an inequality constraint1Tx , with an integer between 0 andn, the optimal value is the sum of the smallest nonpositive coefficients activity consider the selection ofnnonnegative activity levels,denotedx1, .. , xn. These activities consumemresources, which are limited. ActivityjconsumesAijxjof resourcei, whereAijare given. The total resource consumptionis additive, so the total of resourceiconsumed isci=Pnj=1 Aijxj. (Ordinarily wehaveAij 0, , activityjconsumes resourcei. But we allow the possibility thatAij<0, which means that activityjactuallygeneratesresourceias a by-product.)Each resource consumption is limited: we must haveci cmaxi, wherecmaxiare activity generates revenue, which is a piecewise-linear concave function of theactivity level:rj(xj) =(pjxj0 xj qjpjqj+pdiscj(xj qj)xj >0 is the basic price,qj>0 is the quantity discount level, andpdiscjis thequantity discount price, for (the product of) activityj.)

10 (We have 0< pdiscj< pj.) Thetotal revenue is the sum of the revenues associated with each activity, ,Pnj=1rj(xj).The goal is to choose activity levels that maximize the total revenue while respectingthe resource limits. Show how to formulate this problem as an basic problem can be expressed asmaximizePnj=1rj(xj)subject tox 0Ax is a convex optimization problem since the objective is concave and the constraintsare a set of linear inequalities. To transform it to an equivalent LP, we first expressthe revenue functions asrj(xj) = min{pjxj, pjqj+pdiscj(xj qj)},which holds sincerjis concave. It follows thatrj(xj) ujif and only ifpjxj uj,pjqj+pdiscj(xj qj) can form an LP asmaximize1 Tusubject tox 0Ax cmaxpjxj uj, pjqj+pdiscj(xj qj) uj, j= 1, .. , n,with show that this LP is equivalent to the original problem, letus fixx. The last set ofconstraints in the LP ensure thatui ri(x), so we conclude that for every feasiblex,uin the LP, the LP objective is less than or equal to the total revenue.