EE609 Assignment 8 April 10, 2021
1. Show the following results. You may use the result that a function f (x) is convex if and only if f (a+tb)
is convex in t for every possible choice of a and b such that a + tb ∈ dom(f ).
(a) The function f (X) = log det(X) with dom f = Sn++ is concave in X.
(b) The function f (X) = Tr(X−1 ) with dom f = Sn++ is convex in X.
(c) The function f (X) = (det(X))1/n with dom f = Sn++ is concave in X.
(d) The function f (X) = log Tr(X) with dom f = Sn++ is concave in X.
2. Show that the matrix fractional function
f (x, Y) = xT Y−1 x (10)
with dom f = Rn × Sn++ , is convex in (x, Y). You may show this by using the Schur’s complement to
establish that the epigraph of this function is a convex set. Use this result and the composition rule to
show that the function (t − xT Y−1 x)1/2 is concave in (x, Y, t) wherever xT Y−1 x ≤ t.
3. In this question, we will see the intuition behind the Schur’s complement and derive its more general
form. First consider the quadratic function
f (x, y) = xT Ax + 2xT By + yT Cy (13)
where assume that A, C ∈ Sn . Suppose that f is convex in (x, y).
(a) Derive the second order condition for convexity of f .
(b) Recall the result that the function g(x) = miny f (x, y) is also convex whenever f is convex in x
and y. Show that in this case g is quadratic and derive the corresponding second order condition.
4. Here we provide the intuition behind using matrix dual variables.
(a) Using first principles, show that for A ∈ Sn .
(
0 A0
min Tr(AY) = (16)
Y0 −∞ A 0
You may find it useful to write A = ni=1 λi ai aT
P
i .
(b) Next, let us derive the dual of the SDP:
min cT x (18)
x,Y
X
s. t. Y = F(x) := G + Fi x i (19)
i
Y0 (20)
by associating dual variable Z with the equality constraint but keeping the constraint Y 0
implicit. Use the result in part (a) to show that the dual problem is given by
max − Tr(ZG) (21)
Z
s. t. ci = Tr(Fi Z) (22)
Z0 (23)
which is the same form as that obtained when using the matrix dual variable approach.
EE609 Assignment 8, Page 2 of 2 April 10, 2021
5. Consider the complex LMI:
F1 x1 + F2 x2 + . . . + Fn xn + G 0 (29)
where Fi , G are complex Hermitian, i.e., Fi = FH H n
i and G = G , and x ∈ R . Express the complex
LMI as a real LMI. To this end, first establish the equivalence
<(A) −=(A)
A0 ⇔ 0 (30)
=(A) <(A)
where <() and =() denote the real and imaginary parts, respectively. Note also that the condition for a
Hermitial matrix A to be PSD is that uH Au ≥ 0 for all u ∈ Cn .
6. We have seen the following integer programming problem:
min xT Wx (31)
s. t. x2i =1 (32)
and shown that its dual is given by the SDP:
max − 1T ν (33)
ν
s. t. W + diag(ν) 0 (34)
Find the dual of this problem. Since the original problem is non-convex, we will now obtain its relaxed
version.
7. Solve the SDP in closed form:
min Tr(X) (43)
A B
s. t. 0 (44)
BT X
for A ∈ Sn++ .
8. Here we will write the `1.5 -norm minimization problem as an SDP.
(a) First show that the following two problems are equivalent:
X 3/2
min si (50)
s
i
s. t. si ≥ 0 (51)
and
min 1T t (52)
s,t,y
s. t. s2i ≤ ti yi (53)
yi2 ≤ si (54)
from multiple applications of the epigraph trick.
(b) Using the result developed earlier, show that the problem
min kAx + bk1.5 (58)
x
can be written as an SDP.
Page 2
