� � � � � 6.079/6.975, Fall 2009-10 S. Boyd & P. Parrilo Homework 9 1. Efficient numerical method for a regularized least-squares problem. We consider a reg-ularized least squares problem with smoothing, �k n−1 nminimize (a Ti x − bi)2 + δ (xi − xi+1)2 + η x 2 i , i=1 i=1 i=1 where x ∈ Rn is the variable, and δ, η > 0 are parameters. (a) Express the optimality conditions for this problem as a set of linear equations involving x. (These are called the normal equations.) (b) Now assume that k n. Describe an efficient method to solve the normal equations found in (1a). Give an approximate flop count for a general method that does not exploit structure, and also for your efficient method. (c) A numerical instance. In this part you will try out your efficient method. We’ll choose k = 100 and n = 2000, and δ = η = 1. First, randomly generate A and b with these dimensions. Form the normal equations as in (1a), and solve them using a generic method. Next, write (short) code implementing your efficient method, and run it on your problem instance. Verify that the solutions found by the two methods are nearly the same, and also that your efficient method is much faster than the generic one. Note: You’ll need to know some things about Matlab to be sure you get the speedup from the efficient method. Your method should involve solving linear equations with tridiagonal coefficient matrix. In this case, both the factorization and the back sub-stitution can be carried out very efficiently. The Matlab documentation says that banded matrices are recognized and exploited, when solving equations, but we found this wasn’t always the case. To be sure Matlab knows your matrix is tridiagonal, you can declare the matrix as sparse, using spdiags, which can be used to create a tridi-agonal matrix. You could also create the tridiagonal matrix conventionally, and then convert the resulting matrix to a sparse one using sparse. One other thing you need to know. Suppose you need to solve a group of linear equations with the same coefficient matrix, i.e., you need to compute F −1a1, ..., F −1am, where F is invertible and ai are column vectors. By concatenating columns, this can be expressed as a single matrix F −1 a1 F −1 am = F −1 [a1 am] .· · · · · · To compute this matrix using Matlab, you should collect the righthand sides into one matrix (as above) and use Matlab’s backslash operator: F\A. This will do the right thing: factor the matrix F once, and carry out multiple back substitutions for the righthand sides. 1� 2. Bounding portfolio risk with incomplete covariance information. Consider the following instance of the problem described in §4.6, on p171–173 of Convex Optimization. We suppose that Σii, which are the squares of the price volatilities of the assets, are known. For the off-diagonal entries of Σ, all we know is the sign (or, in some cases, nothing at all). For example, we might be given that Σ12 ≥ 0, Σ23 ≤ 0, etc. This means that we do not know the correlation between p1 and p2, but we do know that they are nonnegatively correlated (i.e., the prices of assets 1 and 2 tend to rise or fall together). Compute σwc, the worst-case variance of the portfolio return, for the specific case ⎤⎡⎤⎡ 0.10.2 + + ± x = ⎢⎢⎢⎣ 0.2 −0.05 0.1 ⎥⎥⎥⎦, Σ = ⎢⎢⎢⎣ ⎥⎥⎥⎦, + 0.1 − − + 0.3 +− ± − + 0.1 where a “+” entry means that the element is nonnegative, a “−” means the entry is nonpositive, and “±” means we don’t know anything about the entry. (The negative value in x represents a short position: you sold stocks that you didn’t have, but must produce at the end of the investment period.) In addition to σwc, give the covariance matrix Σwc associated with the maximum risk. Compare the worst-case risk with the risk obtained when Σ is diagonal. 3. Equilibrium position of a system of springs. We consider a collection of n small masses in R2, with locations (x1, y1), . . . , (xn, yn), and masses m1, . . . , mn. (In other words, the vector x ∈ Rn gives the x-coordinates, and y ∈ Rn gives the y-coordinates, of the points.) The masses mi are, of course, positive. For i = 1, . . . , n−1, mass i is connected to mass i+1 by a spring. The potential energy in the ith spring is a function of the (Euclidean) distance di = �(xi, yi) − (xi+1, yi+1)�2 between the ith and (i + 1)st masses, given by 0 di < liEi = (ki/2)(di − li)2 di ≥ li where li ≥ 0 is the rest length, and ki > 0 is the stiffness, of the ith spring. The gravitational potential energy of the ith mass is gmiyi, where g is a positive constant. The total potential energy of the system is therefore 1−n� E = Ei + gm T y. i=1 The locations of the first and last mass are fixed. The equilibrium location of the other masses is the one that minimizes E. (a) Show how to find the equilibrium positions of the masses 2, . . . , n−1 using convex optimization. Be sure to justify convexity of any functions that arise in your formulation (if it is not obvious). Justify any new variables or constraints that you introduce. The problem data are mi, ki, li, g, x1, y1, xn, and yn. 2(b) Carry out your method to find the equilibrium positions for a problem with n = 10, mi = 1, ki = 10, li = 1, x1 = y1 = 0, xn = 10, yn = 10, with g varying from g = 0 (no gravity) to g = 10 (say). Verify that the results look reasonable. Plot the equilibrium configuration for several values of g. 4. Estimating a vector with unknown measurement nonlinearity. (A specific instance of exercise 7.9 in Convex Optimization.) We want to estimate a vector x ∈ Rn, given some measurements yi = φ(aiT x + vi), i = 1, . . . , m. Here ai ∈ Rn are known, vi are IID N (0, σ2) random noises, and φ : R → R is an unknown monotonic increasing function, known to satisfy α ≤ φ�(u) ≤ β, for all u. (Here α and β are known positive constants, with α < β.) We want to find a maximum likelihood estimate of x and φ, given yi. (We also know ai, σ, α, and β.) This sounds like an infinite-dimensional problem, since one of the parameters we are estimating is a function. In fact, we only need to know the m numbers zi = φ−1(yi), i = 1, . . . , m. So by estimating φ we really