Optimization and Algorithms
November 25, 2021
Exam
1. Nonconvex function. (3 points) One of the following functions f : R → R is not convex:
(A) f(x) = (x
2 − x)+ − x
(B) f(x) = − ((x+))2 + x
2 + x
(C) f(x) = (x − x+)
2 − x
(D) f(x) = ((x+))2 − x
2 + x
(E) f(x) = x+ + x
2 − x
(F) f(x) = (x + x+)
2 − (x+)
2
Which one?
Write your answer (A, B, C, D, E, or F) here:
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 matrices A and B, and the vector c are given. The scalar ρ is also given and is positive: ρ > 0.
One of the optimization problems above is not a least-squares problem.
Which one?
Write your answer (A, B, C, D, E, or F) here:
3. Optimal value of a constrained problem. (3 points) Consider the constrained problem
where the variable to optimize is (x1, . . . , xN ), with xn ∈ Rd
for 1 ≤ n ≤ N. The matrices Rn ∈ Rd×d are given for 1 ≤ n ≤ N. Assume that each Rn is a symmetric, positive-definite matrix. The vector s ∈ Rd
is also given.
One of the following expressions is the minimum value that f attains over the feasible set, that is, one of the following expressions is the number min{f(x1, . . . , xN ): x1 + · · · + xN = s}:
Which one?
Write your answer (A, B, C, D, E, or F) here:
4. Sparse linear regression with asymmetric loss. (4 points) Consider the optimization problem
where the variable to optimize is (s, r) ∈ Rn × R. The vectors xk ∈ Rn and the scalars yk ∈ R are given for 1 ≤ k ≤ K. The scalars α, β, and ρ are given and denote positive constants: α > 0, β > 0, and ρ > 0. The functions (·)− and (·)+ are defined as (z)− = max{−z, 0} and (z)+ = max{z, 0} for z ∈ R.
Show that the function f is convex.
5. A simple control problem. (4 points) Consider the optimization problem
where the variables to optimize are xt ∈ Rn
for 1 ≤ t ≤ T and ut ∈ Rp
for 1 ≤ t ≤ T − 1. The vector xinitial ∈ Rn and the matrices Dt ∈ Rn×p are given for 1 ≤ t ≤ T − 1. The scalar ρ is also given and denotes a positive constant: ρ > 0.
Give a closed-form. solution for the optimal {ut
: 1 ≤ t ≤ T − 1}.
6. Moureau envelope. (4 points) Let f : R → R be a convex function. For λ > 0, we define a function eλ[f]: R → R as follows: for x ∈ R, the image of x under the function eλ[f] is the number min{f(u) + 2λ/1 (u − x)
2
: u ∈ R}.
That is, the function eλ[f] maps each number x to the number eλ[f](x), where eλ[f](x) is the minimum value attained by f(u) + 2λ/1 (u − x)
2 as u varies in R.
Let λ1 > 0 and λ2 > 0. Show that
eλ1
[eλ2
[f]](x) = eλ1+λ2
[f](x),
for each x ∈ R.