CO 372: Portfolio Optimization Models

Fall 2024

Problem Set 6

S. Vavasis

Handed out: 2024-11-20.

Due: Fri, 2024-11-29, 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 finding the portfolio to minimize 0.9-CVaR as measured from historical data

subject to a wealth constraint, a return constraint, and a no-short-sale constraint:

min F (x,α)

x,α 0.9

s.t. eTx = 1,

r¯Tx ≥ r ,

p

x ≥ 0.

Recall from lecture:

M

1 1 (cid:88)(cid:2) (cid:3)

F (x,α) = α+ · eTx−rTx−α .

β 1−β M j +

j=1

Here, r ,...,r denote M historical returns, each assumed to be equally likely. Also,

1 M

r as usual denotes the investor’s required return. Finally, recall from lecture that [s]

p +

stands for max(s,0).

Introduce variables t ,...,t so that the jth term in the summation can be upper-

1 M

bounded by t . Then rewrite the problem with these new variables and with a dif-

j

ferentiable objective function and constraints. Explain why the rewritten program is

actually linear programming.

1

2. Suppose the return r of a security follows a discrete probability distribution: r takes

on values r < r < ··· < r with probabilities p ,...,p . Here, p + ··· + p = 1

1 2 N 1 N 1 N

and each p > 0. Select a particular k ∈ {2,...,N}. Consider subtracting a small

i

number θ > 0 from p while simultaneously adding θ from p (so that the p ’s are still

k 1 i

positive and still add to 1). Recall the definition of β-VaR of this distribution: it is

1−r , where k is such that

(cid:80)N

p ≥ β while

(cid:80)N

p < β. Recall the definition of

k i=k i i=k+1 i

β-CVaR of this distribution: for the same k as in the previous sentence, define,

(cid:32) (cid:32)(cid:32) (cid:33) (cid:33) (cid:33)

N

1 (cid:88)

r := p r +···+p r + p −β r .

tail 1 1 k−1 k−1 i k

1−β

i=k

and the β-CVaR is 1−r .

tail

(a)Writedownanexampleofthisset-upwithN = 3andk = 3sothattheperturbation

θ described above causes a discontinuous jump in the β-VaR for an arbitrarily small

θ > 0 (because k changes).

(b) Show that for your small example in (a), the β-CVaR varies continuously with θ

(for small θ > 0).

For both (b) and (c), the value of r is a function of θ (including the unperturbed

tail

problem with θ = 0). For ease of marking, please use the notation r(θ) to denote the

tail

value of r for a particular choice of θ.

tail

(c) Show that the result in (b) is true in general. That is, show that if p +···+p = β

k N

(so that k jumps under perturbations p → p −θ, p → p +θ for θ > 0), then the

k k 1 1

β-CVaR is nonetheless continuous with respect to θ ≥ 0.

Note: since part (c) generalizes part (b), you will get full credit for this question if (a)

and (c) are correctly answered and (b) is skipped. On the other hand, if you are more

confident in your solution to (b) than to (c), then it is safer to submit (b) as well.

3. Suppose τ and x are two scalar variables in a portfolio optimization problem, where τ

stands for a transaction cost and x stands for an invested amount. Suppose that one

has the constraint τ ≥ ϕ(x), where



−0.1x, x ≤ 0,



ϕ(x) = 0.04x, x ∈ [0,1000],

 0.02x+20, x ≥ 1000.

(a) Make a sketch of ϕ. You can either draw it by hand or use graphing software (like

Matlab) or a graphing website. You will note from your sketch that ϕ is piecewise

linear, continuous, and nonconvex. (This function ϕ is a model of transaction costs

where there is a large per-unit expense for short selling, a smaller per-unit expense for

ordinary purchasing, and a volume discount.)

2

(b) Provide a formula of the form ϕ(x) = max(·,min(·,·)) that is equivalent to the

above formula; each ‘·’ symbol stands for one of the three expressions appearing in the

definition of ϕ.

(c) Using the min and max techniques described in lecture, introducing more variables

as needed, rewrite the constraint τ ≥ ϕ(x) as an equivalent sequence of differentiable

constraints, and explain how you arrived at your formula.

4. Consider the problem of minimizing xTHx/2 − tr¯Tx + tτ, where τ is a transaction

cost for security 1 and t > 0 is the usual Pr3 parameter. Assume there is a wealth

constraint, eTx = γ, where γ > 0 is the total budget; a no-short-sell constraint

x ≥ 0; and a nonconvex piecewise linear transaction cost as written in lecture: τ ≥

0.02α x +α (0.01x +1000), α +α = 1, α ≥ 0, α ≥ 0.

1 1 2 1 1 2 1 2

(a) Eliminate the variable τ from the problem by inserting the expression on the RHS

of the τ constraint into the objective function in place of τ. The problem variables are

now x,α ,α .

1 2

(b) Show that the two new terms in the objective function introduced in part (a) can

be written as a quadratic in standard form:

 T    

x x x

1 1 1 1

 α 1  G α 1 +hT  α 1 +d.

2

α α α

2 2 2

Here, G is a 3 × 3 symmetric matrix, h is a 3-vector, and d is a scalar; you should

provide formulas for G, h, and d as part of your solution. Note: t > 0 is a constant.

(c) Argue that the matrix G derived in part (b) is not positive semidefinite. Suggested

approach. The matrix G you found should have 0’s on the diagonal and nonzero entries

in the nondiagonal entries of the first row. Use this structure to find a particular vector

x ∈ R3 whose first two entries are nonzero such that xTGx < 0.

5. Consider the following portfolio optimization problem in a universe with two securities:

min −r¯Tx+τ(x )

1

s.t. x +x = b,

1 2

x ≥ 0, x ≥ 0.

1 2

Take r¯ = [1.10;1.05]. This question does not model risk, so it is assumed that both

securities have very low risk.

Function τ is the transaction cost for x :

1

(cid:26)

0.07x , x ∈ [0,1000],

τ(x ) = 1 1

1 0.03x +40, x ≥ 1000.

1 1

This cost is nonconvex because it models a volume discount. Security 2 has no trans-

action cost.

3

(a) Consider the two investment strategies: (i) entire portfolio in security 1, and (ii)

¯ ¯

entire portfolio in security 2. There is a particular value of b, say b, such that for b > b,

¯ ¯

strategy (i) is preferred, while for b < b, stategy (ii) is preferred. Work out b, and show

the steps of your derivation.

(b) Rewrite the transaction cost as a min of two quantities. Then introduce two

variables α ,α as in lecture to model the transaction cost without explicitly taking a

1 2

min. Thus, the problem will now have four variables, x ,x ,α ,α . Write down this

1 2 1 2

newmodel. Ifyouwroteitcorrectly, theconstraintswillconsistoftwolinearequalities,

four sign constraints, and an objective function with a mixture of linear and quadratic

terms in the four variables.

(c) Implement in Matlab a script that invokes fmincon to solve the nonlinear con-

strained optimization problem written down in (b) for values of b in the range 1000 :

200 : 3000 (i.e., 1000, 1200, 1400,..., 3000).

Someremarksonusingfminconforthisproblem: Inyourcode, denotetheoptimization

variable p, a 4-vector, for consistency of marking. The first two entries of p stand for

x and the third and fourth entry for α and α . You need to write a function handle

1 2

(one-line function) for the objective function derived in (b). This function handle takes

p as a variable and then computes the objective value in terms of p(1),...,p(4). This

problem has no nonlinear constraints, so take nonlcon in the fmincon documentation

to be []. There are two linear equality constraints, written using Aeq and beq in the

documentation. There are lower bounds (denoted lb) but no upper bounds (denoted

ub). Following the nonlcon argument in the argument list, include one more argument

as follows:

[p,fval,exitflag] = fmincon(..., optimoptions(’fmincon’, ’Display’, ’off’))

This argument prevents fmincon from making a long printout as it solves the problem.

The first return argument from fmincon is p, the solution for the four unknowns. The

second return argument fval is unneeded. The third return variable exitflag should

be checked on every iteration; if it is not equal to 1, then your program should emit

an error message.

Set the x0 parameter for fmincon as follows. Use b/2 as the initial guess for both x(i)’s

(first two entries of p), and 0.5 as the initial guess for the α ’s (last two entries of p).

i

For each value of b in the given range, solve the optimization problem to obtain p.

Then display a line in the command window like this:

b = xxx x(1) = xxx x(2) = xxx

The Matlab statement to display a line like this is:

fprintf(’b = %f x(1) = %f x(2) = %f\n’, b, p(1), p(2))

4

Now repeat the whole procedure with an initial guess of p (i.e., x0) as follows: x(1) = b,

x(2) = 0, α = α = 0.5.

1 2

Did the optimizer found by fmincon correspond to the hand calculation in (a) as b

varies? When I carried out this experiment, I found that the choice of starting guess

made a big difference. This is expected since general-purpose nonlinear optimizers are

sensitive to the choice of starting guess and may not return the true (global) minimizer

for some starting guesses.

Hand in: a listing of your code, a copy of the output in the command window for the

two cases (two starting guesses), and an answer to the question in the last paragraph.

Each printout should have 11 lines of the form

b = xxx x(1) = xxx x(2) = xxx

5