Optimization and Algorithms
February 22, 2022
Exam
1. Simple convex function. (3 points) One of the following six functions R → R is convex:
(A) (1 − (x − 1)+)+
(B) |(x − 1)+ − 1|
(C) -(1 − (x − 1)+)+
(D) ((x − 1)+ − 1)+
(E) -((x − 1)+ − 1)+
(F) -|(x − 1)+ − 1|
Which one?
Write your answer (A, B, C, D, E, or F) in the box at the top of page 1
2. Least-squares. (2 points) Consider the following six optimization problems:
In each of the six problems above, the variable to optimize is x ∈ Rn
. The matrix A and the vector b are given. The scalar ρ > 0 is also given.
One of the optimization problems above is a least-squares problem.
Which one?
Write your answer (A, B, C, D, E, or F) in the box at the top of page 1
3. Convex function. (3 points) Let f : Rn → R be a convex function. One of the following functions is guaranteed to be convex:
(A) |f(x)|
(B) f(x) + (f(x))2
(C) (f(x))2
(D) f(x)(f(x))2
(E) |f(x)| + (f(x))2
(F) f(x) + |f(x)|
Which one?
Write your answer (A, B, C, D, E, or F) in the box at the top of page 1
4. Robust portfolio selection. (4 points) A problem that often occurs in finance has the following form.
where the variable to optimize is x ∈ Rn
.
The matrices V1 ∈ Rp×n
, V2 ∈ Rp×n
, and D ∈ Rp×p are given, the matrix D being diagonal with positive entries in the diagonal:
with di > 0 for i = 1, . . . , p.
The vectors µ1 ∈ Rn
, µ2 ∈ Rn and the scalar α ∈ R are given. Finally, recall that the symbol 1 stands for the vector of dimension n with all components equal to one:
Show that the optimization problem (1) is convex.
5. Mahalanobis projection. (4 points) Consider the optimization problem
where the variable to optimize is x ∈ Rn
. The vector µ ∈ Rn and the matrix Σ ∈ Rn×n are given, with Σ being symmetric and positive definite.
Show that the optimal value of problem (2) is
6. Strictly convex functions. (4 points) Suppose that the functions f1 : Rn → R and f2 : Rn → R are both convex, and let f : Rn → R be defined as f(x) = max{f1(x), f2(x)} for each x ∈ Rn
. Is the function f strictly convex? If you think the answer is ‘yes’, then prove it; if you think the answer is ‘no’, then give a counter-example.