EE364a Homework 3 solutions

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.

2 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. In this problem we guide you through a simpleself-contained proof thatfis log-concave.]

3 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?)

4 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++. 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.

5 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.

6 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, .. , 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.

7 , 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.)

8 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. 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.

9 (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.

10 (a)Minimizing a linear function over an affine toAx= distinguish three possibilities. The problem is infeasible (b6 R(A)). The optimal value is . 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).