MATH 11158 : Optimization Methods in Finance Assignment 3 2 April 2022 Due: 11 April, 2022, 4pm Question 1 (SOCP, 10 marks ). Let Q be a real symmetric matrix with a single negative eigenvalue and consider a quadratic constraint x⊤Qx + a⊤x + b ≤ 0. Show how this constraint can be formulated as a second-order conic constraint, and clearly state any assumptions you need to make. For the next set of questions, consider the problem with the 8 market indices and the data in the file indices2.csv that you have used in Tutorial 4 and Assignment 2. Batch this data per quarter as done before. We wish to find a portfolio that invests in at least m assets, for m ∈ {1,...,8}. For each of the indices, any investment must be at least 5% of the total portfolio. Investment in the three S&P indices together cannot be more than 30% of the portfolio, for Dow and Nasdaq together it cannot be more than 40% of the portfolio, and for S&P SmallCap and Russell 2000 (which are both for small-cap stocks) it cannot be more than 25% of the portfolio. We must invest in at least one but no more than two of the S&P indices, and we must invest in at least one of Russell, Barron’s or Wilshire. Furthermore, the investment in Dow must be at least as much as that in the greater of Barron’s and Wilshire. Question 2 (Semidefinite relaxation, 35 marks ). Consider the same 10 scenarios as in Assignment 2, for each asset and each quarter. Consider the tracking error w.r.t. the fully-diversified portfolio (equal investment in each asset) and let the net tracking error be the maximum of tracking errors for each quarter. 1. Formulate a SDP relaxation of the problem of finding a feasible portfolio with minimum net tracking error and meeting required target return rate. (8 marks) 2. Solve your SDP for m ∈ {1,...,8} and a range of target returns. (6 marks) 3. Plot and compare the appropriate efficient frontiers in one single figure. Compare the portfolio compositions in one single figure (instead of the area plot we have used so far, you can use bar graphs). Also comment on the highest return rate for which you are able to find a feasible portfolio. (8 marks) 4. Give an algorithm that uses the SDP solution to find a feasible portfolio. If your algorithm solves any optimization problems, then you cannot use any integer variables. (10 marks) 5. Test your algorithm numerically on the dataset and comment on the quality of the portfolios you get. (3 marks) Question 3 (Stochastic gradient method, 20 marks ). Consider the stochastic investment problem as before. However, this time we will not use the same 10 scenario discretization. 1. Formulate the investment problem as stochastic optimization and clearly state your decision variables and recourse function. (5 marks) Page 1 MATH 11158 : Optimization Methods in Finance 2. For each value of m ∈ {1, . . . , 8}, solve the stochastic optimization problem by the stochastic gradient method, using step sizes of 1/k in iteration k and randomly generating N equally likely scenarios at each iteration, where you should test with N ∈ {50,100,200}. Fix the random seed in MATLAB using (10 marks) rng(10,’twister’); As early termination criteria, you can stop your algorithm when either of the following happens: you reach 1000 iterations or the changes in objective value between consecutive iterations is no more than ε = 10−4 for each of the past 10 iterations. 3. Plot the portfolio compositions using bar graphs in a single figure for m = 4 and different values of N. (5 marks) Question 4 (Benders method, 15 marks ). Take the previous question and solve it by the Ben- ders decomposition method, using the same early termination criteria and giving the same plots. Comment and compare the quality of portfolios found by the two algorithms. Page 2