Homework 5
Convex Optimization
1. Consider the following non-smooth function on the real line:
f(x) = max!
Describe the subdifferential ∂f(x) at every point x ∈R.
2. Prove or disprove: the subdifferential ∂f(x) of a convex function is a convex set at every x ∈R.
3. Recall the subdifferential for the nuclear norm for an n1 × n2 matrix X.
∂$X$" = #UV T + W : UW = 0,WV = 0,$W$ ≤ 1$
In the expression above, X has rank r and its SVD is X = UΣV T, where U is n1 × r, Σ is r × r and V is n2 × r. Recall that
x+ = proxt!cdot!!(X) = argmin
Z
if and only if
X−X+ ∈ t∂’’X+’’"
Show that we can compute the prox operator above by singular value thresholding:
X max(σit,0).
1
