MATH 11158 : Optimization Methods in Finance
Assignment 2
25 February 2021 Due: 10 March, 2021
Part I : Theoretical Exercises
Question 1 (Recourse function, (15 marks)). Consider minx∈X c>x + E
[
Q(x, ω)
]
where the re-
course function is
Q(x, ω) = min
y
f0(y, ω) s.t. fi(y, ω) + gi(x, ω) ≤ hi(ω), i = 1, . . . ,m, y ∈ Y,
where Y is a convex set and where for each i = 0, . . . ,m, fi(·, ω) is a concave function of y for every
ω ∈ Ω and for each i = 1, . . . ,m, gi(·, ω) is a convex function of x for every ω ∈ Ω.
1. Suppose Y is a polytope, which is a convex set with finitely many extreme points1. Let the
extreme points of Y be the vectors {y¯1, . . . , y¯K} for some finite integer K.
Use Lagrange weak duality2 to argue that for every λ ≥ 0 the recourse function can be lower
bounded as (8 marks)
Q(x, ω) ≥ −h(ω)>λ+
m∑
i=1
λigi(x, ω) + min
k=1,...,K
f0(y¯
k, ω) +
m∑
i=1
λifi(y¯
k, ω)
Observe that this lower bound is a convex function of x for every ω. To establish this lower
bound, you will first have to prove the following lemma:
When minimising a concave function over a compact convex set, there exists at
least one extreme point of the set that is an optimal solution. (4 marks)
2. Prove that Q(·, ω) is a convex function of x for every ω ∈ Ω. (5 marks)
Hint: This is using basic definition of convexity and independent of the first part.
3. Explain how the theorem from lectures week 5 about convexity of the recourse function
Q(x, ω) = miny{q(ω)>y : W (ω)y + T (ω)x = h(ω), y ≥ 0} follows as a simple corollary
of above. (2 marks)
Question 2 (Cones of Matrices, (20 marks)). Throughout, let 0 denote either a vector or matrix
of all zeros, as appropriate by context.
Let Sn := {A ∈ Rn×n : A = A>} be the set of all symmetric real n×n matrices. Let S+n := {A ∈
Sn : A ≥ 0} be the set of nonnegative symmetric matrices, meaning that every such matrix has each
entry in it ≥ 0. We defined the cone of symmetric positive semidefinite matrices in lectures and we
denote this by PSDn. Now consider the following sets of matrices,
DNNn := PSDn ∩ S+n (Doubly nonnegative matrices)
COPn := {A ∈ Sn : v>Av ≥ 0, ∀v ≥ 0} (Copositive matrices)
CPn := {A ∈ Sn : A = BB> for some B ≥ 0} (Completely positive matrices)
Note that in the definition of CPn, the matrix B is of dimension n× k for some integer k.
1. What is the difference between a psd matrix and a copositive matrix ? (1 mark)
1An extreme point is a point that cannot be written as a convex combination of two other points.
2This was covered in week 2 in Quadratic.pdf.
Page 1
MATH 11158 : Optimization Methods in Finance
2. Prove that each of DNNn, COPn, CPn is a convex cone. (5 marks)
You can skip showing convexity of CPn since that requires using an alternate definition.
3. Prove the following relationships, (9 marks)
COPn ⊆ PSDn ⊆ DNNn ⊆ PSDn + S+n ⊆ CPn ⊆ COP∗n︸ ︷︷ ︸
(4 marks)
.
Here, C∗ denotes the dual cone of a cone C as defined in lectures, and + between two sets denotes
Minkowski addition, i.e., for two sets X and Y , we have X + Y := {x+ y : x ∈ X, y ∈ Y }.
In fact, CPn is equal to COP∗n, but you are asked only to show the ⊆-inclusion.
4. Consider a portfolio optimization problem that is a quadratically constrained quadratic pro-
gram (QCQP) which maximises the expected return while imposing restrictions on multiple
risk measures Risk1, . . . ,Riskm that are quadratic risk measures (but not necessarily convex)
z∗ = max
x
µ>x s.t. Riski(x) ≤ bi, i = 1, . . . ,m, x ∈ F.
Here, Riski(x) = x
>Qix + f>i x is the i
th quadratic risk measure and F is the set of feasible
portfolios given by some linear constraints, including no short-selling constraint. Define the
following set where • denotes the Frobenius inner product between matrices
F :=
{
(x,X) ∈ Rn × Rn×n : Qi •X + f>i x ≤ bi ∀i, x ∈ F
}
and consider the following problem for some convex cone C.
zC = max
x
µ>x s.t. (x,X) ∈ F ,
(
1 x>
x X
)
∈ C.
Depending on which C we choose, either PSDn+1,DNNn+1, COPn+1, CPn+1, we get the values
zpsd, zdnn, zcop, zcp, respectively. Compare these values to each other and also to z
∗, as in are
any of them =,≤,≥ than another ? (5 marks)
Please highlight your final answer comparing all the values.
Part II : Computational Exercises
Numerical answers to be submitted to the Online Assignment on Gradescope upto a precision of 4
decimal places. Mathematical models and code to be submitted along with Part I.
For this part, we will consider the stochastic portfolio problem. We will solve this problem by
two different algorithms, one from lectures and a new one described here.
Question 3 (Stochastic gradient method).
Question 4 (Benders decomposition).
Page 2




































































































学霸联盟