Convex Optimization
Problem set 3
Due Monday November 11th
1. Consider the Quadratically Constrained Quadratic Program (QCQP):
minimizes.t.

1 0x Hx + c0 x
2x0 Qi x + p0i x + di ≤ 0A0 x = bi = 1..m

(1)

where the minimization is w.r.t. x ∈ Rn , and H, Qi ∈ S n , c, pi ∈ Rn , di ∈ R, A ∈ Rn×p ,b ∈ Rp are given.
(a) What constraints must H and each Qi satisfy for the problem to be convex?
(b) Derive the dual of the problem.
(c) When Qi = 0 for all i, the problem is known simply as a “Quadratic Problem” (QP).
By substituting Q = 0 in the general dual, verify the dual of a quadratic program isalso a quadratic program.
(d) Write down the QCQP as a semi-definite program (SDP), that is using only linear
matrix inequality constraints and a linear objective.
2. In this problem we will expand the derivation of the dual to the logistic regression problem
we did in class. Recall the logistic loss function is given by:g(z) = log(1 + e−z )(2)You might want to plot g(z) and see how g(z) is close to zero when z >> 0 and increases
roughly linearly when z < 0. It can thus be used to penalize values that we would like to bepositive, and preferably away from zero.
(a) In class we saw the expression of the Fenchel conjugate of g(z). What is the value ofg ∗ (0) and g ∗ (−1)? What is the value of g ∗ (p) for p > 0 or p < −1?
In a logistic regression model we would like to explain binary labels (responses) y1 , . . . , ym
using a linear function of input points (feature vectors, covariate vectors) x1 , . . . , xm ∈ Rn .
In particular, we would like to find w ∈ Rn such that the sign of w0 xi matches the label yi ,1and we quantify this by minimizing g(yi w0 xi ). Fitting a logistic regression model therefore
corresponds to optimizing the following unconstrained convex optimization problem:mX

minimizew∈Rng(yi w0 xi )

(3)

i=1

In order to be able to derive a meaningful dual, e.g. in order to be able to obtain certificatesof suboptimality, we instead rewrote (3) as:mX

minimizew∈Rn ,z∈Rmg(zi )

(4)

i=1
0s.t. zi = yi w xi

i = 1..m.

(b) Use the dual of (4), seen in class, to write down the KKT conditions for a pair ofprimal and dual optimal solutions of (4). Explain how to use the KKT conditions toeasily obtain a primal optimal solution if you are given a dual optimal solution.
(c) Consider adding a regulaization term, as is commonly done, to (3):mXminimizew∈Rng(yi w0 xi ) +i=1

λkwk2
2(5)Modify (4) accordingly by adding a similar regularization term to its objective, andderive the dual of the resulting problem (Hint: first derive the Fenchel conjugate of thesquared norm, possibly as a special case of the Fenchel conjugate of a quadratic).
(d) [Optional] An alternative loss function to the logistic loss is the hinge-loss (or SupportVector Machine loss) given by:r(z) = [1 − z]+(6)Derive the Fenchel conjugate of r(z), then replace the logistic loss g(yi w0 xi ) with thehinge-loss r(yi w0 xi ) in the regularized probelm (5), rewrite it using equality constraints
and derive its dual.
An alternative way to obtain a dual is to represent the piecewise-linear hinge-loss ξi =r(yi w0 xi ) using the two linear inequality constraints ξi ≥ 0 and ξi ≥ 1 − yi w0 xi ,resulting in:minimizew∈Rn ,ξ∈RmmX

ξi +i=1s.t. ξi ≥ 0,

λkwk2
2(7)
0, ξi ≥ 1 − yi w xi

Derive the dual of (7) and compare it to the dual obtained above.

2i = 1..m.

3. In this problem we will consider a different variant of the binary rating reconstruction problem we studied in class. Consider n “users” and m “movies”, and a sparse set of ratingsyij ∈ ±1 for (i, j) ∈ S, where S is a (small) subset of all user-movie pairs. We will again
want to find small-norm vectors ui ∈ Rk and vj ∈ Rk (k > n + m), associated with eachuser i and each user j, that explain the ratings in the sense that:yij hui , vj i ≥ 1for each (i, j) ∈ S. However, this time we would like to minimize the maximum norm, i.e.
optimize:minimize max(max kui k , max kvj k)ij(8)s.t. yij hui , vj i ≥ 1 ∀(i, j) ∈ S
The problem (8) can be reformulated as a semi-definite program:
minimize ts.t. ( XA0 XB)  0diag(A) ≤ tdiag(B) ≤ tyij Xij ≥ 1 ∀(i, j) ∈ S(9)(a) Derive the dual of this semi-definite program.
(b) Write down, and simplify as much as you can, the KKT conditions for the problems.
Suggested review questions (please do not turn these in): 4.43 (try also deriving the dual ofeach one), 5.13, 5.22, 5.41.

3