R Solution. R

1 EE364a, Winter 2007-08 Prof. S. BoydEE364a Homework 4 involving 1- and -norms. Formulate the following problems as LPs. Ex-plain in detail the relation between the optimal solution of each problem and thesolution of its equivalent LP.(a) MinimizekAx bk ( -norm approximation).(b) MinimizekAx bk1( 1-norm approximation).(c) MinimizekAx bk1subject tokxk 1.(d) Minimizekxk1subject tokAx bk 1.(e) MinimizekAx bk1+kxk .In each problem,A Rm nandb Rmare given. (See for more problemsinvolving approximation and constrained approximation.)Solution.(a) Equivalent to the LPminimizetsubject toAx b t1Ax b the variablesx Rn,t R. To see the equivalence, assumexis fixed in thisproblem, and we optimize only overt. The constraints say that t aTkx bk tfor eachk, ,t |aTkx bk|, ,t maxk|aTkx bk|=kAx bk .Clearly, ifxis fixed, the optimal value of the LP isp (x) =kAx bk . Thereforeoptimizing overtandxsimultaneously is equivalent to the original problem.

2 (b) Equivalent to the LPminimize1 Tssubject toAx b sAx b swith variablesx Rnands Rm. Assumexis fixed in this problem, and weoptimize only overs. The constraints say that sk aTkx bk sk1for eachk, ,sk |aTkx bk|. The objective function of the LP is separable, sowe achieve the optimum oversby choosingsk=|aTkx bk|,and obtain the optimal valuep (x) =kAx bk1. Therefore optimizing overxandssimultaneously is equivalent to the original problem.(c) Equivalent to the LPminimize1 Tysubject to y Ax b y 1 x 1,with variablesx Rnandy Rm.(d) Equivalent to the LPminimize1 Tysubject to y x y 1 Ax b 1with variablesx Rnandy reformulation is to writexas the difference of two nonnegative vectorsx=x+ x , and to express the problem asminimize1Tx++1Tx subject to 1 Ax+ Ax b 1x+ 0, x 0,with variablesx+ Rnandx Rn.(e) Equivalent tominimize1Ty+tsubject to y Ax b y t1 x t1,with variablesx Rn,y Rm, andt fuel optimal consider a linear dynamical system with statex(t) Rn,t= 0.

3 , N, and actuator or input signalu(t) R, fort= 0, .. , N dynamics of the system is given by the linear recurrencex(t+ 1) =Ax(t) +bu(t), t= 0, .. , N 1,whereA Rn nandb Rnare given. We assume that the initial state is zero, ,x(0) = fuel optimal control problemis to choose the inputsu(0), .. , u(N 1)so as to minimize the total fuel consumed, which is given byF=N 1Xt=0f(u(t)),subject to the constraint thatx(N) =xdes, whereNis the (given) time horizon, andxdes Rnis the (given) desired final or target state. The functionf:R Ris thefuel use mapfor the actuator, and gives the amount of fuel used as a function of theactuator signal amplitude. In this problem we usef(a) =(|a| |a| 12|a| 1|a|> means that fuel use is proportional to the absolute value of the actuator signal,for actuator signals between 1 and 1; for larger actuator signals the marginal fuelefficiency is the minimum fuel optimal control problem as an minimum fuel optimal control problem is equivalent to the LPminimize1 Ttsubject toHu=xdes y u yt yt 2y 1,with variablesu RN,y RN, andt R, whereH=hAN 1b AN 2b Ab are several other possible LP formulations.)

4 For example, we can keep the statetrajectoryx(0), .. , x(N) as optimization variables, and replace the equality constraintabove,Hu=xdes, with the equality constraintsx(t+ 1) =Ax(t) +bu(t), t= 0, .. , N 1,x(0) = 0,x(N) = this formulation, the variables areu RN,x(0), .. , x(N) Rn, as well asy RNandt another variation is to not use the intermediate variableyintroduced above, andexpress the problem just in terms of the variablet(andu): t u t,2u 1 t, 2u 1 t,with variablesu RNandt probability of satisfying a linear a random variable inRn, normally distributed with mean cand covariance matrixR. Consider the problemmaximizeprob(cTx )subject toF x g, Ax= the conditions under which this is equivalent to a convex or quasiconvex optimiza-tion problem. When these conditions hold, formulate the problem as a QP, QCQP, orSOCP (if the problem is convex), or explain how you can solve itby solving a sequenceof QP, QCQP, or SOCP feasibility problems (if the problem is quasiconvex).

5 , a scalar random variable, normally distributed with meanEu= cTxand varianceE(u Eu)2=xTRx. The random variableu cTx xTRxhas a normal distribution with mean zero and unit variance, soprob(u ) =prob u cTx xTRx cTx xTRx!= 1 cTx xTRx!,where (z) =1 2 Rz e t2/2dtis the standard normal maximizeprob(u ), we can minimize ( cTx)/ xTRx(since is increasing), , solve the problemmaximize ( cTx )/ xTRxsubject toF x gAx=b.(1)This is not a convex optimization problem, since the objective is not problem can, however, be solved by quasiconvex optimization provided a condtionholds. (We ll derive the condition below.) The objective exceeds a valuetif and onlyif cTx t xTRxholds. This last inequality is convex, in fact a second-order cone constraint, providedt 0. So now we can state the condition: There exists a feasiblexfor which cTx .(This condition is easily checked as an LP feasibility problem.)

6 This condition, by theway, can also be stated as: There exists a feasiblexfor whichprob(u ) 1 that this condition holds. This means that the optimal value of our originalproblem is at least , and the optimal value of the problem (1) is at least 0. Thismeans that we can state our problem asmaximizetsubject toF x g,Ax=b cTx t xTRx,4where we can assume thatt 0. This can be solved by bisection ont, by solving anSOCP feasibility problem at each step. In other words: the function ( cTx )/ xTRxis quasiconcave, provided it is fact, provided the condition above holds ( , there exists a feasiblexwith cTx )we can solve the problem (1) via convex optimization. We make the change of variablesy=x cTx ,s=1 cTx ,sox=y/s. This yields the problemminimizeqyTRysubject toF y gsAy=bs cTy s= 1s A heated fluid at temperatureT(degrees above ambient temperature) flows in a pipewith fixed length and circular cross section with radiusr.

7 A layer of insulation, withthicknessw r, surrounds the pipe to reduce heat loss through the pipe walls. Thedesign variables in this problem areT,r, heat loss is (approximately) proportional toT r/w, so over a fixed lifetime, theenergy cost due to heat loss is given by 1T r/w. The cost of the pipe, which hasa fixed wall thickness, is approximately proportional to the total material, , it isgiven by 2r. The cost of the insulation is also approximately proportionalto the totalinsulation material, , 3rw(usingw r). The total cost is the sum of these heat flow down the pipe is entirely due to the flow of the fluid, which has a fixedvelocity, , it is given by 4T r2. The constants iare all positive, as are the variablesT,r, the problem: maximize the total heat flow down the pipe, subject to an upperlimitCmaxon total cost, and the constraintsTmin T Tmax,rmin r rmax,wmin w wmax, w this problem as a geometric problem ismaximize 4T r2subject to 1T w 1+ 2r+ 3rw CmaxTmin T Tmaxrmin r rmaxwmin w wmaxw is equivalent to the GPminimize (1/ 4)T 1r 2subject to ( 1/Cmax)T w 1+ ( 2/Cmax)r+ ( 3/Cmax)rw 1(1/Tmax)T 1, TminT 1 1(1/rmax)r 1, rminr 1 1(1/wmax)w 1, wminw 1 110wr 1 1(with variablesT,r,w).

8 Simple the optimization problemminimizex2+ 1subject to (x 2)(x 4) 0,with variablex R.(a)Analysis of primal the feasible set, the optimal value, and theoptimal solution.(b)Lagrangian and dual the objectivex2+ 1 versusx. On the sameplot, show the feasible set, optimal point and value, and plot the LagrangianL(x, ) versusxfor a few positive values of . Verify the lower bound property(p infxL(x, ) for 0). Derive and sketch the Lagrange dual functiong.(c)Lagrange dual the dual problem, and verify that it is a concavemaximization problem. Find the dual optimal value and dual optimal solution . Does strong duality hold?(d)Sensitivity (u) denote the optimal value of the problemminimizex2+ 1subject to (x 2)(x 4) u,as a function of the parameteru. Plotp (u). Verify thatdp (0)/du= .Solution.(a) The feasible set is the interval [2,4]. The (unique) optimal point isx = 2, andthe optimal value isp = plot 1012345 5051015202530xf0f1(b) The Lagrangian isL(x, ) = (1 + )x2 6 x+ (1 + 8 ).

9 The plot shows the LagrangianL(x, ) =f0+ f1as a function ofxfor differentvalues of 0. Note that the minimum value ofL(x, ) overx( ,g( )) isalways less thanp . It increases as varies from 0 toward 2, reaches its maximumat = 2, and then decreases again as increases above 2. We have equalityp =g( ) for = 2. 1012345 5051015202530x@@If0 f0+ f0+ f0+ > 1, the Lagrangian reaches its minimum at x= 3 /(1 + ). For 1it is unbounded below. Thusg( ) =( 9 2/(1 + ) + 1 + 8 > 1 1which is plotted 2 101234 10 8 6 4 20246 g( )We can verify that the dual function is concave, that its value is equal top = 5for = 2, and less thanp for other values of .(c) The Lagrange dual problem ismaximize 9 2/(1 + ) + 1 + 8 subject to dual optimum occurs at = 2, withd = 5. So for this example we candirectly observe that strong duality holds (as it must Slater s constraint qual-ification is satisfied).(d) The perturbed problem is infeasible foru < 1, since infx(x2 6x+ 8) = 1, the feasible set is the interval[3 1 +u,3 + 1 +u],given by the two roots ofx2 6x+ 8 =u.)

10 For 1 u 8 the optimum isx (u) = 3 1 +u. Foru 8, the optimum is the unconstrained minimum off0, ,x (u) = 0. In summary,p (u) = u < 111 +u 6 1 +u 1 u 81u figure shows the optimal value functionp (u) and its 20246810 20246810up (u)epip p (0) uFinally, we note thatp (u) is a differentiable function ofu, and thatdp (0)du= 2 = .9 Solutions to additional a function over the probability simple necessary and suffi-cient conditions forx Rnto minimize a differentiable convex functionfover theprobability simplex,{x|1Tx= 1, x 0}. simple basic optimality condition is thatxis feasible, ,x 0,1Tx= 1, and that f(x)T(y x) 0 for all feasibley. We ll first show this isequivalent tomini=1,..,n f(x)i f(x) see this, suppose that f(x)T(y x) 0 for all feasibley. Then in particular, fory=ei, we have f(x)i f(x)Tx, which is what we have above. To show the otherway, suppose that f(x)i f(x)Txholds, fori= 1, .. , n.