Homework 7
1. Consider the optimization problem
Σm
minimize i=1 h( Aix + bi 2) − cT x
with variable x ∈ Rn, where c ∈ Rn, Ai ∈ R3×n, bi ∈ R3, and
(u − 1)2/2, u ≥ 1
h(u) =
0, otherwise.
Derive the Lagrange dual of the equivalent problem
Σ
minimize mi=1 h( yi 2) − cT x
subject to Aix + bi − yi = 0, i = 1, . . . , m,
with variables x ∈ Rn and yi ∈ R3.
Solution. The Lagrangian is
m m
Σ Σ
L(x, y, z) = (h( yi 2) − zT y
i i) − cT x + zTi (Aix + bi).
i=1 i=1
Σm
Minimizing over x gives condition i=1 ATi zi = c. Minimizing over yi gives
inf(h( yi 2) − zT yi) = inf(h( yi 2) − zi 2 yi 2)
yi i yi
= inf (h(u) — zi 2u)
u≥0
2
= −1/2 zi 2 − zi 2.
The dual problem is
Σ
maximize Σmi=1 2
m (b zi − zi 2 /2 − zi 2)
iT
subject to i=1 AT z = c. i
i
2. Fix S ∈ S+
n and λ > 0. Consider the following optimization problem:
Σ
maximize log det X − Tr(SX) − λ i,j tij
subject to |Xij| ≤ tij,
where the domain of log det is Sn++ . Show that if the optimal solution is a block diagonal
matrix, then |Sij| ≤ λ whenever the (i, i) entry and the (j, j) entry are in two different
blocks.
(Note that you should solve this without using subgradients (which we have not covered in
our course). This is a very useful result in learning Gaussian graphical models in statistics,
used as a “screening test”.)
1
, Solution. Rewrite the problem as:
Σ
maximize log det X − Tr(SX) − λ i,j ti,j
subject to −ti,j ≤ Xi,j ≤ ti,j
The Lagrangian L : Sn++ × Rn×n × Rn×n '→ R is:
Σ Σ
L(X, η, γ) = log det X − Tr(SX) + ti,j(−λ + ηi,j + γi,j) + Xi,j(−ηi,j + γi,j)
i,j i,j
Since the problem is strictly feasible, by KKT, if X is an optimal solution, there exists (η, γ)
such that:
X −1 + S + η − γ = 0
T
−λ11 + η + γ = 0
−ti,j ≤ Xi,j ≤ ti,j
ηi,j ≥ 0, γi,j ≥ 0
ηi,j(Xi,j − ti,j) = 0, γi,j(Xi,j + ti,j) = 0
Since ηi,j ≥ 0, γi,j ≥ 0 and ηi,j + γi,j = λ, we have |ηi,j − γi,j| ≤ λ. If i and j belong to
different blocks then Xi,j = Xi,j−1 = 0. That implies |Si,j| = |γi,j − ηi,j| ≤ λ.
3. Minimum norm positive semidefinite matrix completion. Given some entries of a matrix, we
want to find a “completion” for it such that the completed matrix is positive semidefinite,
and has the smallest possible matrix norm (maximum singular value).
(a) Express this problem as an SDP. (b) Using CVX find the smallest norm PSD completion
for the following matrix:
50 6 ? 4 ?
6 ? ? ? −15
A= ? ? 46 ? 17
4 ? ? ? −13
? −15 17 −13 70
Solution.
(a) Note that for a matrix X ∈ Sn+, the spectral norm of X is equal to the largest eigenvalue
of X, X = λmax(X). To complete the X with the smallest spectral norm, we
formulate the following problem,
minimize X
subject to X ⪰ 0
Xij = Aij, ij ∈ Ω
2