凸優(yōu)化作業(yè)答案

EE364a, Winter 2007-08Prof. S. Boyd EE364a Homework 5 solutions 4.15 Relaxation of Boolean LP. In a Boolean linear program, the variable x is constrained to have components equal to zero or one: minimizecTx subject toAx ? b xi 0,1,i = 1,.,n. (1) In general, such problems are very diffi cult to solve, even though the feasible set is fi nite (containing at most 2npoints). In a general method called relaxation, the constraint that xibe zero or one is replaced with the linear inequalities 0 xi 1: minimizecTx subject toAx ? b 0 xi 1,i = 1,.,n. (2) We refer to this problem as the LP relaxation of the Boolean LP (4.67).The LP relaxation is far easier to solve than the original Boolean LP. (a) Show that the optimal value of the LP relaxation (4.68) is a lower bound on the optimal value of the Boolean LP (4.67). What can you say about the Boolean LP if the LP relaxation is infeasible? (b) It sometimes happens that the LP relaxation has a solution with xi 0,1. What can you say in this case? Solution. (a) The feasible set of the relaxation includes the feasible set of the Boolean LP. It follows that the Boolean LP is infeasible if the relaxation is infeasible, and that the optimal value of the relaxation is less than or equal to the optimal value of the Boolean LP. (b) The optimal solution of the relaxation is also optimal for the Boolean LP. 4.60 Log-optimal investment strategy. We consider a portfolio problem with n assets held over N periods. At the beginning of each period, we re-invest our total wealth, redis- tributing it over the n assets using a fi xed, constant, allocation strategy x Rn, where x ? 0, 1Tx = 1. In other words, if W(t 1) is our wealth at the beginning of period t, then during period t we invest xiW(t 1) in asset i. We denote by (t) the total 1 return during period t, i.e., (t) = W(t)/W(t 1). At the end of the N periods our wealth has been multiplied by the factor QN t=1(t). We call 1 N N X t=1 log(t) the growth rate of the investment over the N periods. We are interested in determining an allocation strategy x that maximizes growth of our total wealth for large N. We use a discrete stochastic model to account for the uncertainty in the returns. We assume that during each period there are m possible scenarios, with probabilities j, j = 1,.,m. In scenario j, the return for asset i over one period is given by pij. Therefore, the return (t) of our portfolio during period t is a random variable, with m possible values pT 1x,.,p T mx, and distribution j= prob(t) = pT jx), j = 1,.,m. We assume the same scenarios for each period, with (identical) independent distribu- tions. Using the law of large numbers, we have lim N 1 N log W(N) W(0) ! = lim N 1 N N X t=1 log(t) = Elog(t) = m X j=1 jlog(pT jx). In other words, with investment strategy x, the long term growth rate is given by Rlt= m X j=1 jlog(pT jx). The investment strategy x that maximizes this quantity is called the log-optimal in- vestment strategy, and can be found by solving the optimization problem maximize Pm j=1jlog(p T jx) subject tox ? 0,1Tx = 1, with variable x Rn. Show that this is a convex optimization problem. Solution. Actually, theres not much to do in this problem. The constraints, x ? 0, 1Tx = 1, are clearly convex, so we just need to show that the objective is concave (since it is to be maximized). We can do that in just a few steps: First, note that log is concave, so log(pT jx) is concave in x (on the domain, which is the open halfspace x | pT jx 0). Since j 0, we conclude that the sum of concave functions m X j=1 jlog(pT jx) is concave. 2 5.13 Lagrangian relaxation of Boolean LP. A Boolean linear program is an optimization problem of the form minimizecTx subject toAx ? b xi 0,1,i = 1,.,n, and is, in general, very diffi cult to solve. In exercise 4.15 we studied the LP relaxation of this problem, minimizecTx subject toAx ? b 0 xi 1,i = 1,.,n, (3) which is far easier to solve, and gives a lower bound on the optimal value of the Boolean LP. In this problem we derive another lower bound for the Boolean LP, and work out the relation between the two lower bounds. (a) Lagrangian relaxation. The Boolean LP can be reformulated as the problem minimizecTx subject toAx ? b xi(1 xi) = 0,i = 1,.,n, which has quadratic equality constraints. Find the Lagrange dual of this problem. The optimal value of the dual problem (which is convex) gives a lower bound on the optimal value of the Boolean LP. This method of fi nding a lower bound on the optimal value is called Lagrangian relaxation. (b) Show that the lower bound obtained via Lagrangian relaxation, and via the LP re- laxation (5.107), are the same. Hint. Derive the dual of the LP relaxation (5.107). Solution. (a) The Lagrangian is L(x,)=cTx + T(Ax b) Tx + xTdiag()x =xTdiag()x + (c + AT )Tx bT. Minimizing over x gives the dual function g(,) = ( bT (1/4) Pn i=1(ci+ a T i i)2/i ? 0 otherwise where aiis the ith column of A, and we adopt the convention that a2/0 = if a 6= 0, and a2/0 = 0 if a = 0. 3 The resulting dual problem is maximizebT (1/4) Pn i=1(ci+ a T i i)2/i subject to ? 0, ? 0. In order to simplify this dual, we optimize analytically over , by noting that sup i0 (ci + aT i i)2 i ! = ( 4(ci+ aT i )ci+ aT i 0 0ci+ aT i 0 =min0,4(ci+ aT i ). This allows us to eliminate from the dual problem, and simplify it as maximizebT + Pn i=1min0,ci+ a T i subject to ? 0. (b) We follow the hint. The Lagrangian and dual function of the LP relaxation are L(x,u,v,w)=cTx + uT(Ax b) vTx + wT(x 1) =(c + ATu v + w)Tx bTu 1Tw g(u,v,w)= ( bTu 1TwATu v + w + c = 0 otherwise. The dual problem is maximizebTu 1Tw subject toATu v + w + c = 0 u ? 0,v ? 0,w ? 0, which is equivalent to the Lagrange relaxation problem derived above. We con- clude that the two relaxations give the same value. 6.2 1-, 2-, and -norm approximation by a constant vector. What is the solution of the norm approximation problem with one scalar variable x R, minimizekx1 bk, for the 1-, 2-, and -norms? Solution. (a) 2-norm: the average 1Tb/m. (b) 1 -norm: the (or a) median of the coeffi cients of b. (c) -norm: the midrange point (maxbi minbi)/2. 4 Solutions to additional exercises 1. Schur complements. Consider a matrix X = XT Rnnpartitioned as X = AB BTC # , where A Rkk. If detA 6= 0, the matrix S = C BTA1B is called the Schur complement of A in X. Schur complements arise in many situations and appear in many important formulas and theorems. For example, we have detX = detAdetS. (You dont have to prove this.) (a) The Schur complement arises when you minimize a quadratic form over some of the variables. Let f(u,v) = uTvTXuTvTT, where u Rk. Let g(v) be the minimum value of f over u, i.e., g(v) = infuf(u,v). Of course g(v) can be . Show that if A 0, we have g(v) = vTSv. (b) The Schur complement arises in several characterizations of positive defi niteness or semidefi niteness of a block matrix. As examples we have the following three theorems: X 0 if and only if A 0 and S 0. If A 0, then X ? 0 if and only if S ? 0. X ? 0 if and only if A ? 0, BT(I AA) = 0 and C BTAB ? 0, where Ais the pseudo-inverse of A. (C BTAB serves as a generalization of the Schur complement in the case where A is positive semidefi nite but singular.) Prove one of 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 function f(x) = (Ax + b)T(P0+ x1P1+ + xnPn)1(Ax + b) where A Rmn, b Rm, and Pi= PT i Rmm, with domain domf = x Rn| P0+ x1P1+ + xnPn 0. This is the composition of the matrix fractional function and an affi ne mapping, and so is convex. Give an LMI representation of epif. That is, fi nd a symmetric matrix F(x,t), affi ne in (x,t), for which x domf,f(x) t F(x,t) ? 0. Solution 5 (a) If A 0, then g(v) = vTSv. We have f(u,v) = uTAu+2vTBu+vTCv. If A 0, we can minimize f over u by setting the gradient with respect to u equal to zero. We obtain u(v) = A1Bv, and g(v) = f(u(v),v) = vT(C BTA1B)v = vTSv. (b) Positive defi nite and semidefi nite block matrices. X 0 if and only if A 0 and S 0. Suppose X 0. Then f(u,v) 0 for all non-zero (u,v), and in particular, f(u,0) = uTAu 0 for all non-zero u (hence, A 0), and f(A1Bv,v) = vT(CBTA1B)v 0 (hence, S = CBTA1B 0). This proves the only if part. To prove the “if” part, we have to show that if A 0 and S 0, then f(u,v) 0 for all nonzero (u,v) (that is, for all u, v that are not both zero). If v 6= 0, then it follows from (a) that f(u,v) inf u f(u,v) = vTSv 0. If v = 0 and u 6= 0, f(u,0) = uTAu 0. If A 0, then X ? 0 if and only if S ? 0. From part (a) we know that if A 0, then infuf(u,v) = vTSv. If S ? 0, then f(u,v) inf u f(u,v) = vTSv 0 for all u, v, and hence X ? 0. This proves the if-part. To prove the only if-part we note that f(u,v) 0 for all (u,v) implies that infuf(u,v) 0 for all v, i.e., S ? 0. X ? 0 if and only if A ? 0, BT(I AA) = 0, C BTAB ? 0. Suppose A Rkkwith rank(A) = r. Then there exist matrices Q1 Rkr, Q2 Rk(kr)and an invertible diagonal matrix Rrrsuch that A = h Q1Q2 i 0 00 # h Q1Q2 iT , and Q1Q2TQ1Q2 = I. The matrix Q1Q20 00I # Rnn is nonsingular, and therefore AB BTC # ? 0 Q1Q20 00I #T AB BTC # Q1Q20 00I # ? 0 6 0QT 1B 00QT 2B BTQ1BTQ2C ? 0 QT 2B = 0, QT 1B BTQ1C # ? 0. We have 0 if and only if A ? 0. It can be verifi ed that A= Q11QT 1, I AA = Q2QT 2. Therefore QT 2B = 0 Q2Q T 2B = (I A A)B = 0. Moreover, since is invertible, QT 1B BTQ1C # ? 0 0, C BTQ11QT 1B = C B TAB ? 0. (c) The epigraph of f is the set of points (x,t) that satisfy P0+x1P1+xnPn 0 and (Ax + b)T(P0+ x1P1+ + xnPn)1(Ax + b) t. Using the second result of part (b), we can write the second inequality as t(Ax + b)T (Ax + b)P0+ x1P1+ + xnPn # ? 0. This a linear matrix inequality in the variables x, t, i.e., a convex constraint. 2. Formulate the following optimization problems as semidefi nite programs. The variable is x Rn ; F(x) is defi ned as F(x) = F0+ x1F1+ x2F2+ + xnFn with Fi Sm. The domain of f in each subproblem is domf = x Rn| F(x) 0. (a) Minimize f(x) = cTF(x)1c where c Rm. (b) Minimize f(x) = maxi=1,.,KcT i F(x)1ciwhere ci Rm, i = 1,.,K. (c) Minimize f(x) = sup kck21 cTF(x)1c. (d) Minimize f(x) = E(cTF(x)1c) where c is a random vector with mean Ec = c and covariance E(c c)(c c)T= S. Solution. 7 (a) minimizet subject to F(x)c cTt # ? 0. (b) minimizet subject to F(x)ci cT i t # ? 0,i = 1,.,K. (c) f(x) = max(F(x)1), so f(x) t if and only if F(x)1? tI. Using a Schur complement we get minimizet subject to F(x)I ItI # ? 0. (d) f(x) = cTF(x)1 c + tr(F(x)1S). If we factor S as S = Pm k=1ckc T k the problem is equivalent to minimize cTF(x)1 c + Pm k=1c T kF(x) 1ck, which we can write as an SDP minimizet0+ P ktk subject to F(x) c cTt0 # ? 0 F(x)ck cT k tk # ? 0,k = 1,.,m. 3. Optimality conditions and dual for log-optimal investment problem. (a) Show that the optimality conditions for the log-optimal investment problem de- scribed in exercise 4.60 can be expressed as: 1Tx = 1, x ? 0, and for each i, xi 0 m X j=1 j pij pT jx = 1,xi= 0 m X j=1 j pij pT jx 1. We can interpret this as follows. pij/pT jx is a random variable, which gives the ratio of the investment gain with asset i only, to the investment gain with our mixed portfolio x. The optimality condition is that, for each asset we invest in, the expected value of this ratio is one, and for each asset we do not invest in, the expected value cannot exceed one. Very roughly speaking, this means our portfolio does as well as any of the assets that we choose to invest in, and cannot do worse than any assets that we do not invest in. Hint. You can start from the simple criterion given in 4.2.3, or the KKT condi- tions, or additional exercise 1 from homework 4. 8 (b) In this part we will derive the dual of the log-optimal investment problem. We start by writing the problem as, minimize Pm j=1jlogyj subject toy = PTx,x ? 0,1Tx = 1. Here, P has columns p1,.,pm, and we have the introduced new variables y1,.,ym, with the implicit constraint y 0. We will associate dual variables , and 0 with the constraints y = PTx, x ? 0, and 1Tx = 1, respectively. Defi ning j= j/0for j = 1,.,m, show that the dual problem can be written as maximize Pm j=1jlog( j/j) subject toP ? 1, with variable . The objective here is the (negative) Kullback-Leibler divergence between the given distribution and the dual variable . Solution. (a) The problem is the same as minimizing f(x) = Pm j=1jlog(p T jx) over the prob- ability simplex. If x is feasible the optimality condition is that f(x)T(zx) 0 for all z with z ? 0, 1Tz = 1. This holds if and only if for each k, xk 0 f xk = min i=1,.,n f xi = f(x)Tx. From f(x) = Pm j=1jlog(p T jx), we get f(x)i= m X j=1 j(1/pT jx)pij, so f(x)Tx = m X j=1 j(1/pT jx)p T jx = 1. The optimality conditions are, 1Tx = 1, x ? 0, and for each i, xi 0 m X j=1 j pij pT jx = 1,xi= 0 m X j=1 j pij pT jx 1. (b) The Lagrangian is L(x,0) = m X j=1 jlogyj+ T(y P Tx) Tx + 0(1Tx 1). 9 This is unbounded below unless TPT T+ 01T= 0. Since L is separable in y we can minimize it over y by minimizing over yj . We fi nd the minimum is obtained for yj= j/j, so we have g(,0) = 1 0+ m X j=1 jlog(j/j), provided P ? 01. Thus we can write the dual problem as maximize1 0+ Pm j=1jlog(j/j) subject toP ? 01 with variables Rm, 0 R. This has implicit constraint 0. We can further simplify this, by analytically optimizing over 0. From the con- straint inequality we see that 0 0. Defi ning = /0, we get the problem in variables , 0 maximize1 0+ Pm j=1jlog( j0/j) subject to0P ? 01. Cancelling 0from the constraint we get maximize1 0+ log0+ Pm j=1jlog( j/j) subject toP ? 1. The optimal value of 0is evidently 0= 1, so we end up with the dual problem maximize Pm j=1jlog( j/j) subject toP ? 1. 4. Log-optimal investment strategy. In this problem you will solve a specifi c instance of the log-optimal investment problem described in exercise 4.60, with n = 5 assets and m = 10 possible outcomes in each period. The problem data are defi ned in log_opt_invest.m, with the rows of the matrix P giving the asset return vectors pT j. The outcomes are equiprobable, i.e., we have j= 1/m. Each column of the matrix P gives the return of the associated asset in the diff erent posible outcomes. You can examine the columns to get an idea of the types of assets. For example, the last asset gives a fi xed and certain return of 1%; the fi rst asset is a very risky one, with occasional large return, and (more often) substantial loss. Find the log-optimal investment strategy x, and its associated long term growth rate R lt. Compare this to the long term growth rate obtained with a uniform allocation strategy, i.e., x = (1/n)1, and also with a pure investment in each asset. For the optimal investment strategy, and also the uniform investment strategy, plot 10 sample trajectories of the accumulated wealth, i.e., W(T) = W(0) QT t=1(t), for T = 0,.,200, with initial wealth W(0) = 1. 10 To save you the trouble of fi guring out how to simulate the wealth trajectories or plot them nicely, weve included the simulation and plotting code in log_opt_invest.m; you just have to add the code needed to fi nd x. Hint:The current version of cvx doesnt handle the logarithm, but you can use geomean() to solve the problem. Solution. (a) The following code was used to solve this problem: P = 3.50001.11001.11001.04001.0100; 0.50000.97000.98001.05001.0100; 0.50000.99000.99000.99001.0100; 0.50001.05001.06000.99001.0100; 0.50001.16000.99001.07001.0100; 0.50000.99000.99001.06001.0100; 0.50000.92001.08000.99001.0100; 0.50001.13001.10000.99001.0100; 0.50000.93000.95001.04001.0100; 3.50000.99000.97000.98001.0100; m,n = size(P); % Find log-optimal investment policy cvx_begin variable x_opt(n) maximize(geomean(P*x_opt) sum(x_opt) = 1 x_opt = 0 cvx_end x_opt x_unif = ones(n,1)/n; R_opt = sum(log(P*x_opt)/m R_unif = sum(log(P*x_unif)/m It was found that the log-optimal investment strategy is: xopt= (0.0580, 0.4000, 0.2923, 0.2497, 0.0000). This strategy achieves a long term growth rate R lt = 0.0231. In contrast, the uniform allocation strategy achieves a growth rate of Runif= 0.0114. Clearly asset 1 is a high-risk asset. The amount that we invest in this asset will grow by a factor of 3.50 with probability 20% and will be halved with probability 11 80%. On the other hand, asset 5 is an asset with a certain return of 1% per time period. Finally, assets 2, 3 and 4 are low-risk assets. It turns out that the log-optimal policy in this case is to invest very little wealth in the high-risk asset and no wealth on the sure asset and to invest most of the wealth in asset 2. (b) The following code was used to generate the random event sequences and the trajectory plots: % Generate random event sequences rand(state,0); N = 10; T = 200; w_opt = ; w_unif = ; for i = 1:N events = ceil(rand(1,T)*m); P_event = P(events,:); w_opt = w_opt 1; cumprod(P_event*x_opt); w_unif = w_unif 1; cumprod(P_event*x_unif); end % Plot wealth versus time figure semilogy(w_opt,g) hold on semilogy(w_unif,r-) grid axis tight xlabel(time) ylabel(wealth) This generates the following plot: 12 20406080100120140160180200 10 1 10 0 10 1 10 2 10 3 t W The log-optimal investment policy consistently increases