xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

matlab代写-MATH 11158-Assignment 2

时间：2021-02-25

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

学霸联盟

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

学霸联盟