Reference no: EM133296092

Question 1: Portfolio optimization

We study the problem of portfolio optimization and the risk-return tradeoff. Consider a pool of 5 assets, where pi denotes the relative price change in asset i over a fixed period of time. Portfolio optimization seeks to allocate the amount of asset i held over that period of time with the goal of maximizing returns. Let x_i denote the amount of asset i held throughout the time period. The return on the portfolio is r = p^Tx where r is measured in dollars.

Of course the vector p∈R⁵ is not exactly known. We model our belief of p as a random variable with mean and covariance

 

1a) The linear program

r* = minimize -p¯^Tx
subject to x ≥ 0, 1^Tx = 1

will find return a portfolio based purely on the mean price-change of the assets. The elements of xú denote the allocation of asset i as a percentage. Here we rule out the possibility of shorting-selling. Modify the above LP so that the decision vector x returns the cash amount of each asset when the portfolio has a budget of $10, 000. Solve the resulting problem using CVX and note r* and x*.

1b) Generate 5, 000 samples of the random variable p and use the optimal allocation xi from 1a) to plot a histogram of returns. Calculate the average return based on the 5,000 samples. You can use the following pseudo-code to generate a sample of p: >> p = p_mean + sqrtm(Sigma)*randn(5,1).

Note: You must use sqrtm, if you use sqrt this will just apply the square root function element-wise and your solution will be incorrect.

1c) Add the quadratic regularizer γx^TΣx to your LP to account for variance in the model of p. For 200 values of γ spaced logarithmically between 10^-4 and 10⁴ plot the optimal values of p¯^T x (in dollars) on the y-axis against the standard deviation x^TΣx on the x-axis.

1d) From 1c) select a level of risk (i.e., pick ") that you are comfortable with and take the associated optimal allocation xú, repeat the simulation from part 1b) and plot the resulting histogram. Comment on how the results compare to those in 1b).

1e) It is often possible to achieve better returns on investment by allowing short-selling (i.e., allowing xi < 0). However we will limit ourselves to only being allowed to short- sell to the value of $2, 000. Modify the QP from 1c) to incorporate the short-selling constraints. Produce a maximum of two plots that demonstrate the affect of short-selling stock.

Question 2: Positive semidefinite polynomials

A polynomial is defined as a weighted sum of monomials where a monomial takes the form x^-1 x^-2 ,. .., x^-n where -i is a non-negative integer. The degree of a monomial is given by Σ_iα_i. For example,

f (x) = 3.6x₁²x₂ - 4x₁⁷x₃⁵ + x₂⁴ - 2

is a polynomial in 3 variables that contains 4 monomials with degrees 3, 12, 4, and 0 respectively (from left to right). The weights 3.6, 4, 1, and 2 are the coefficients. In many applications it is necessary to determine if a polynomial p(x) is positive semidefinite (psd), i.e., verify that p(x) 0 for all x Rn. Unfortunately the task of verifying this property is in general intractable. However, a sufficient condition for p to be psd is to show that it can be decomposed as

         m
p(x)= ∑h_i(x)²,   (1)
         k=1
where the functions hi are themselves polynomials.

All polynomials, regardless of whether or not they are psd, can be expressed as a quadratic expression subject to linear constraints on the coefficients, i.e., any polynomial p can be expressed as

p(x)= Z(x)^T QZ(x), (2)

where Z(x) is a vector containing monomials, and Q is a square matrix that relates coefficients to monomials. When all monomials in p have the same degree, say l, Z(x) only needs to include monomials that are of degree 1/2, else, Z(x) must contain all monomials up to degree 1/2.

2a) Express the polynomial p(x)= 2x₁⁴ + 2x₁³x₂ - x₁²x₂² + 5x₂⁴ in the quadratic form (2)

and state all necessary linear constraints on the entries of Q.

2b) When the matrix Q can be chosen to be positive semidefinite, then it follows that p(x) 0 for all x, i.e. we have verified that p is psd. Formulate the convex feasibility problem and use CVX to determine if such a Q exists for:

i) p(x) from part 2a)

ii) p₂(x)= x₁⁴x₂² + x1²x₂⁴ + x3⁶ - 3₁x²x₂²x₃²

Hint: Take advantage of the fact that all monomials have have the same degree.

2c) When a positive semidefinite Q does exist, we can conclude that p(x) can be decomposed as in (1). Suggest a method for constructing the polynomials h_i(x) from Q and Z(x).

2d) Assume that f is a given polynomial. Minimizing over f directly is not possible as most polynomials are not convex. Use the fact that

minimize f (x) and maximize t

                        subject to f (x) ≥ t

are equivalent problems, and use the constrained quadratic representation of a polynomial to to propose a convex optimization problem that provides a lower-bound to the unconstrained problem of minimizing f. Implement this problem in CVX to obtain a lower bound on the non-convex problem

minimize 4x₁² - 21/10 x₁⁴ + 1/3x₁⁶ + x₁x₂ - 4x₂² + 4x₂⁴.

Question 3: Interior point methods

3a) Consider a convex optimization problem in standard form. Express the calculation of the Newton step in the barrier method in matrix form, i.e., derive the matrices A and b such that:

 

where A and b are functions of the objective, and barrier functions.

3b) Implement the barrier method described on slide 12-11 of the lecture notes to solve the inequality constrained problem:

 

Your solver should return pi, xi, and vector ‹ú of dual variables. Provide all parameters you set (e.g. α, β for back tracking, tolerance ε, etc.) Provide a plot of the duality gap m/t against the number of Newton iterations c.f. slide 12-13.

Question 4: Combinatorial problems

In many settings one is interested in solving an optimization problem where the decision vector is constrained to be either +1 or 1. Unfortunately, such problems are non-convex. Consider the problem

maximize x^TQx

subject to xi ∈ {-1, 1}

where Q is a symmetric (you can assume that it is positive semidefinite).

4a) Use the fact that

x_i² - 1 = 0 <=> xi ∈ {≠1, 1}

to derive the dual program for (3), make implicit constraints explicit to ensure the solution is bounded.

4b) Introduce a new variable X = xx^T and show that (3) can be expressed as a semidefinite program with an additional (non-convex) rank constraint.

4c) A graph is a collection of vertices V = {v₁,. .., v_n} and edges

ε = {(v_i, v_j) | if v_i is connected to v_j and v_i, v_j ∈ V}.

 

Figure 1 shows a simple example of a graph with 8 vertices. We consider undirected graphs, so if (vi, vj) and (vj, vi) correspond to the same edge.

For any subset S ⊂ V, the capacity of S is the number of edges connecting vertices in S to vertices not in S. A graph can be represented via an adjacency matrix:

A_ij1  =    if (vi, vj) ∈ ε
            0 otherwise .

Indicating whether a vertex belongs to S or not can be done by creating a vector x such that

x_i = 1 if x_i ∈ S
     -1 otherwise .

4c-i) Formulate the problem of finding a set with maximum capacity as (non-convex) optimization problem.

Hint: Think about what value 1 - x_ix_j returns depending on whether v_i and/or v_j are in S?

4c-ii) Use CVX to obtain a bound for the maximum capacity problem for the graph shown in Figure 1.

4c-iii) How do you extract the set S from the convex formulation?