EE 127 / EE 227AT Homework Assignment #4 A Due date: 3/15/16 11AM. Please L TEX or scan your homework solution and submit the pdf on bCourses. Exercise 1 (A Boolean problem of maximal margin) We have to decide which items to sell among of a collection of n items, with given selling prices si > 0, i = 1, . . . , n. Selling implies a transaction cost ci > 0 for each item i; the total transaction cost is the sum of these costs, plus a xed amount d > 0 (say, d = 1). We are interested in the following decision problem: which items need to be sold, in order to maximize the margin (revenue-to-cost ratio). 1. Show that the problem can be formalized as . . p = max n f (x), f (x) = x{0,1} s x . 1+c x 2. Show that the problem admits a convex formulation: p = min t : t 1 (s tc)+ . t0 Here z+ , for a vector z Rn , denotes the vector with components max(0, zi ), i = 1, . . . , n. Hint: for given t 0, express the condition f (x) t for every x {0, 1}n in simple terms. 3. How can you recover an optimal solution x , from an optimal value t for the above problem? Exercise 2 (Dual of a QP and dierentiability) Consider a quadratic program of the form 1 p = max c x x Qx : Ax b, x 2 m,n m n n where A R , b R , c R , and Q S++ . We assume that the problem is feasible. 1. Form the dual of the QP. Show that strong duality holds. 2. Show that p , considered as a function of c (resp. b), is convex (resp. concave). 3. Explain how to form a subgradient of p (considered as a function of c). 1 4. Is p dierentiable with respect to c? Exercise 3 (Bounds on a linear-fractional function) Consider the function f : Rn . R, with values on its domain X = {x : x 2 1} given by f (x) = b x . 1a x Here, a, b Rn are given, with a, b = 0 and a 2 < 1. In this exercise, we consider the problem . fmax = max f (x). xX 1. Show that indeed f is well-dened everywhere on X . 2. Is the above problem convex, as stated? Proof or counter-example. 3. Show that the problem can be expressed as an SOCP in one variable, namely fmax = min t : at + b t 2 t. Hint: for given t 0, express the condition f (x) t for every x X in simple terms. 4. Show that fmax = t , where t is the (unique) positive solution to the equation t = at + b 2 . Express the optimal value fmax in closed-form. 5. Show that x = a + (1/t )b is an optimal point for the original problem. 6. What about a lower bound on f ? Derive an explicit expression for two scalars f , > 0 , f + ] for every x X . such that f (x) [f Exercise 4 (Superquantile Risk) In this problem, we want to replicate the S&P 100 index I using other stocks Sj , j = 1, . . . , n, over time t = 1, . . . , T (scenarios or days). In our problem, we have T =600, n=30. We'd like to minimize the mean absolute penalty over the days, where each daily penalty is the relative deviation from S&P 100: f (x, pt ) := n j=1 It ptj xj It (see the table below for what each symbol means, and note that the prices of I are normalized to 1). We'd also like to choose a strategy that bounds the -superquantile. When = 0.999, the -superquantile is the expected loss in the worst 0.1% of cases. It turns out that the -superquantile is upper bounded by w if and only if 1 s.t. + T (1 ) T It n j=1 It t=1 2 ptj xj w + This motivates the problem 1 min x, T T It t=1 n j=1 ptj xj It n s.t. p T j xj = v (1) j=1 x0 + 1 T (1 ) T It n j=1 ptj xj It t=1 w + Data is provided in the le data.mat. More information can be found at the following links: http://aorda.com/aod/PSG_CS_HTML/index.html?portfolio_replication.htm http://www.math.washington.edu/~rtr/papers/rtr187-CVaR2.pdf Variable It ptj v := v/IT xj w Interpretation price of I at time t price of Sj at time t Desired amount of money at time T number of units of I at time T number of units of Sj in proposed replicating portfolio Desired upper bound on -superquantile Level of superquantile Value 1600 H1 (from data.mat) 10000 1e-3 0.999 1. Show the problem is convex. 2. Solve the problem using CVX. 3. Formulate the problem as a linear program (LP). Hint: you may need to introduce slack variables. Use CVX to solve the LP you found. Compare running times and the solution with part 2. 4. Make a histogram of the penalty over the 600 days. 5. Solve the problem with the extra constraint of equal allocation, that is, xi = xj i, j. Make a histogram of the loss over the 600 days and compare with part 4. 3