CO 372: Portfolio Optimization Models

Fall 2024

Problem Set 5

S. Vavasis

Handed out: 2024-11-06.

Due: Fri, 2024-11-15, 4pm EST, on Crowdmark. Papers must be handed in on-line using

the labeled dropbox on Crowdmark. The Crowdmark link will be sent out on the same day

this is posted. Each question is handed in as a separate upload. You can either prepare

your solutions electronically using, e.g., LaTeX, or else you can hand-write them and submit

a scan. In the latter case, please take care that the scan is of good quality with a white

background.

Your papers may be handed in up to 24 hours late, in which case there is a 10% late

penalty. Please use the late-paper dropbox on Crowdmark if you are handing in a late paper.

You may hand in some questions on time and others late. In this case, use the on-time

dropbox for the on-time questions and the late dropbox for the late questions. However, you

may not split the parts of a question (i.e., (a), (b), etc.) between the two dropboxes.

Collaboration policy. This problem set is a solo effort. Students are allowed to discuss

question with each other in general terms including helping each other on Piazza. However,

no student should share an entire solution to a question, nor should any student hand in

work that entirely represents someone else’s effort.

1. Consider a variant of SCQP in which, in addition to the simplex constraints, there are

upper bounds on the variables:

min 1xTHx−tr¯Tx

2

s.t. eTx = 1

x ≤ u

x ≥ 0

Here, H is a given n×n symmetric positive semidefinite matrix, g is an n-vector, x is

the n-vector of unknowns, and u ∈ Rn is the vector of upper bounds, assumed to have

all positive entries. As usual, the investor parameter t is assumed to be nonnegative.

(a) Write down the KKT conditions for this problem. Label all four parts.

(b) Using the KKT conditions, show the following result. Suppose x∗ is an optimizer,

and suppose x∗ = u∗. Then x∗ is also an optimizer for the above problem if r¯ is

1 1

replaced by r¯+γe for any γ ≥ 0, where e is the first column of the identity matrix.

1 1

(The financial interpretation of (b) is that if a portfolio is optimal for a particular value

of the return vector and the purchase amount of security 1 in this optimal portfolio is

at its upper bound, then this portfolio continues to be optimal if the return for security

1 increases.)

1

2. Show that the rows of the coefficient matrix A of the problem denoted (EQP) (de-

k k

veloped as part of the active set method for SCQP in lecture) are independent.

Suggested approach: Let the rows be numbered 1,2,...,s +1, where s denotes the

k k

number of ‘0’ entries in x . Suppose there exist coefficients α ,...,α such that

k−1 0 s

k

α eT +α vT +...+α vT = 0T, (∗)

0 1 1 s k s k

where eT is the first row of (EQP) and vT,...,vT are s remaining rows, which are

k 1 s k

k

each distinct rows of the n × n identity matrix. Argue that if α ̸= 0 for some i ∈

i

{1,...,s }, then it must hold that α = −α . Thus, if α ̸= 0 for some i ∈ {1,...,s },

k 0 i i k

then α ̸= 0. But argue that if α ̸= 0, then equation (∗) requires every single row of

0 0

the identity matrix to be among v ,...,v .

1 s

k

3. Recall that the range-space method requires formation of the matrix AH−1AT for

solving EQP, where H ∈ Sn is positive definite and A ∈ Rp×n has independent rows.

Consider the special case of (EQP) . Suppose that H−1 has been precomputed at

k

the start of the SCQP algorithm. Use the special structure of A to find a simple

k

and efficient algorithm for forming the product A H−1AT on iterations k = 1,2,....

k k

How many operations +,−,∗,/ accurate to the leading term are required for your

procedure? (Don’t count the work to form H−1.)

4. Consider the vector x computed on l. 36 of the SCQP code downloaded from the Learn

website. It is claimed that x has the following properties:

(a) x(S) = 0.

(b) x ≥ 0.

(c) x(i) = 0.

Here, S refers to the index set computed in line 14, and i refers to the index computed

on line 35. In your solution, write “xold” for the value of x that exists prior to line 36.

Assume that xold satisfies properties 1–2.

Verify analytically by referring to the formulas encoded in the statements of the m-

file that properties 1–3 hold for x. Note: a correct solution will refer to specific line

numbers in its analysis.

5. Write a Matlab code to plot the efficient frontier of SCQP. Write a function whose

header is

function plot_eff_frontier_scqp(H,rbar,trange)

that takes H and r¯ and a range of t-values. For each t-value, it obtains the optimal x

by invoking scqp_solve (downloaded from Learn).

Then the function makes three plots. The first plot is t on the x-axis versus expected

return, that is, r¯Tx, where x is the optimizer returned by scqp_solve, on the y-axis.

2

√

The second is t on the x-axis versus square-root-risk, that is xTHx, on the y-axis.

The third plot is square-root risk on the x-axis with return on the y-axis. Use line-style

“-*” in all three plots so that the line and individual points are visible. Use Matlab’s

title function to add a title to each plot showing what is on the two axes.

Download ps5 data.m from the Learn website. Invoke your function with H, r¯ from

the data set, and trange set to 0:10:500 (i.e., 0,10,20,...,500).

Hand in: listing of your function and the three plots.

3