6.079/6.975 S. Boyd & P. Parrilo October 29–30, 2009. Midterm exam This is a 24 hour take-home midterm exam. Please turn it in to Professor Pablo Parrilo, (Stata Center), on Friday October 30, at 5PM (or before). You may use any books, notes, or computer programs (e.g., Matlab, CVX), but you may not discuss the exam with anyone until October 31, aft er everyone has taken the exam. The only exception is that you can ask us for clarification, via email. Please address your emails to both professors and the TA. Please make a copy of your exam b efo re handing it in. When a problem involves computation you must give all of the following: a clear discussion and justification of exactly what you did, the Matlab source code that produces the result, and the final numerical results or plots. Matlab files containing problem data are ava ilable on Stellar. All problems have equal weight. Some are easier than they might appear at first glance. Be sure to check your email and the course web site on Stellar often during the exam, just in case we need to send out an importa nt announcement. And one technical comment. For problems that require you to work out a numerical solution, you are welcome to use a solution method that involves solving more t han just a single convex optimization problem. (Of course, only when this is necessary.) 11. 2D filter design. A symmetric convolution kernel with support {−(N − 1), . . . , N −1}2 is characterized by N2 coefficients hkl, k, l = 1, . . . , N. These coefficients will be our variables. The corresponding 2D frequency response (Fourier transform) H : R2 → R is given by H(ω1, ω2) = � hkl cos((k − 1)ω1) cos((l − 1)ω2), k,l=1,...,N where ω1 and ω2 are the fr equency variables. Evidently we only need to specify H over the r egion [0, π]2, although it is often plotted over the region [−π, π]2 . (It won’t matter in this problem, but we should mention that the coefficients hkl above are not exactly the same as the impulse response coefficients of the filter.) We will design a 2D filter (i. e ., find the coefficients hkl) to satisfy H(0 , 0) = 1 and to minimize the maximum response R in the rejection region Ωrej ⊂ [0, π]2 , R = sup |H(ω1, ω2)|. (ω1,ω2)∈Ωrej (a) Explain why this 2D filter design problem is convex. (b) F ind the optimal filter for the specific case with N = 5 and Ωrej = {(ω1, ω2) ∈ [0, π]2 | ω12 + ω22 ≥ W2}, with W = π/4. You can approximate R by sampling on a grid of frequency values. Define ω(p) = π(p − 1)/M, p = 1, . . . , M. (You can use M = 25.) We then replace t he exact expression for R above with Rˆ= max{|H(ω(p), ω(q))| | p, q = 1, . . . , M, (ω(p), ω(q)) ∈ Ωrej}. Give the optimal value of Rˆ. Plot the optimal frequency response using plot_2D_filt(h), available on the course web site, where h is the matrix containing the coefficients hkl. 2� � 2. Gini coefficient of in equality. Let x1, . . . , xn be a set of nonnegative numbers with positive sum, which typically represent the wealth or income of n individuals in some group. The Lorentz curve is a plot of the fraction fi of total wealth held by the i poorest individuals, i fi = (1/1T x) x(j), i = 0, . . . , n, j=1 versus i/n, where x(j) denotes the jth smallest of the numbers {x1, . . . , xn}, and we take f0 = 0. The Lorentz curve starts at (0, 0) and ends at (1, 1). Interpreted as a continuous curve (as, say, n → ∞) the Lorentz curve is convex and increasing, and lies on or below the straight line joining the endpoints. The curve coincides with this straight line, i.e., fi = (i/n), if and only if the wealth is distributed equally, i.e., the xi are all equal. The Gini coefficien t is defined as twice the area between the straight line corresponding to uniform wealth distribution and the Lorentz curve: n G(x) = (2/n) ((i/n) − fi). i=1 The Gini coefficient is used as a measure of wealth or income inequality: It ranges between 0 (for equal distribution of wealth) and 1 − 1/n (when one individual holds all wealth). (a) Show that G is a quasiconvex function on x ∈ Rn \ {0} .+ (b) Gini coefficient and marriage. Suppose that individuals i and j get married (i 6 j) and therefore pool wealth. This means that xi and xj are both replaced = with (xi + xj )/2. What can you say about the change in Gini coefficient caused by this marriage? 3� ��� � 3. Optimal trans-shipment of a commodity. We consider a single commodity, that can be bought or sold in n different locations or markets, at a (given) price pi at location i. Let ui denote the amount sold at location i, where we interpret ui < 0 as meaning that we buy an amount |ui| at locatio n i. The gross revenue from buying and selling the commodity is pT u. At each location i there is a (given) maximum commodity availa bility ai (which limits how much we can buy there), and a maximum demand for the commodity di (which limits how much we can sell there). Thus, we must have −ai ≤ ui ≤ di. You can assume that ai and di are nonnegative. (They can be zero, however: di = 0 means that at location i, we can only buy the commodity; we cannot sell it.) We can ship the commodity between the locations, at a cost. Let Sij ≥ 0 denote the amount of commodity t hat we ship from location j to location i. (We can assume that Sii = 0.) The total shipping charge is n CijSij = Tr(CT S), i,j=1 where Cij are (given) nonnegative shipping rates. Our net profit, including shipping charges, is pT u − Tr(CT S). At location i the total amount shipped out to ot her locations is n j=1 Sji, and the amount received from other locations is n j=1 Sij, so we must have n n ui = Sij − Sji. j=1 j=1 (In words: the amount of commo dity sold at each location is the total amount shipp ed in to that lo catio n, minus the total amount