Midterm 18s Sol

EE 364a: Convex Optimization I R.
Pathak
July 12, 2018
Midterm Quiz Solutions

1. True or false. Write T or F if each statement is true or false. Suppose that f, g : Rn → R
and φ : R → R are given functions.
(a) F If f, g are convex, then h(x, y) = (f (x) + g(y))2 is convex.
(b) T If f, φ are convex, differentiable, and φ0 > 0, then φ(f (x)) is convex.
p
(c) T If f, g are concave and positive, then f (x)g(x) is concave.
Solution.
(a) False. A simple counterexample is g(y) = 0 and f (x) = x log x. Then h(x, y) =
(x log x)2 is not convex, even though f and g are convex. If in addition f and g
were guaranteed to be nonnegative, then h(x, y) would be convex by the composition
rules.
(b) True. Since φ0 > 0, φ is increasing, so φ(f (x)) is convex by the composition rules.
√
(c) True. The function h(x, y) = xy is concave on R2++ and increasing in each
argument. Since f and g are concave and positive, h(f (x), g(x)) is concave by the
composition rules.
2. DCP rules. The function f (x, y) = −1/(xy) with dom f = R2++ is concave. Briefly
explain how√
to represent
√ it, using disciplined convex programming (DCP), limited to the
atoms 1/u, uv, v, u2 , u2 /v, addition, subtraction, and scalar multiplication. Justify
any statement about the curvature, monotonicity, or other properties
√ of the functions
you use. Assume these atoms take their usual domains (e.g., u has domain u ≥ 0),
and that DCP is sign-sensitive (e.g., u2 /v is increasing in u when u ≥ 0).
Solution.
√
Since f (x, y) = −(1/ xy)2 , it can be seen as the
√composition, f (x, y) = −g3 (g2 (g1 (x, y))),
2 2
where g3 (u) = u , g2 (u) = 1/u, and g1 (u, v) = uv. Note that g1 is concave on R++ and
positive, g2 is convex and decreasing on R++ , and g3 is convex and increasing. Thus,
g2 (g1 (x, y)) is DCP convex, and hence g3 (g2 (g1 (x, y))) is also DCP convex, so f is DCP
concave.
3. Curvature of some functions. Determine the curvature of the functions below.

(a) the product f (u, v) = uv, with dom f = R2
convex concave neither
(b) the function f (x, u, v) = log(v−xT x/u), with dom f = {(x, u, v) | uv > xT x, u > 0}
1
(c) the ‘exponential barrier’ of polyhedral constraints
m
X 1
f (x) = exp ,
i=1
bi − aTi x
with dom f = {x | aTi x < bi , i = 1, . . . , m}, and ai ∈ Rn , b ∈ Rm

Solution.
(a) Neither. The Hessian ∇f 2 (u, v) has a positive and negative eigenvalue, thus this
function is neither convex nor concave (though it is quasiconcave).
(b) Concave. The function xT x/u is jointly convex in x and u. Hence, v − xT x/u is
concave, and also positive on the given domain. The result follows as log is concave
and increasing.
(c) Convex. The function 1/u is convex on R++ and on the given domain, bi − aTi x > 0,
so 1/(bi − aTi x) is convex in x. The result follows since exp(1/(bi − aTi x)) is the
composition of a convex increasing function with a convex function and because
sum of convex functions is convex.
4. Convexity of some sets. Determine if each set is necessarily convex.

(a) {P ∈ Rn×n | xT P x ≥ 0 for all x 0}
convex not convex
√ √
(b) {(u, v) ∈ R2 | cos(u + v) ≥ 2/2, u2 + v 2 ≤ π 2 /4} (Hint: cos(π/4) = 2/2)
convex not convex
(c) {x ∈ Rn | xT A−1 x ≥ 0}, where A ≺ 0.
convex not convex
Solution.
(a) Convex. Let X, Y ∈ {P | xT P x ≥ 0, for all x 0}. If 0 ≤ θ ≤ 1 and x 0, then
xT (θP + (1 − θ)Q)x = θxT P x + (1 − θ)xT Qx ≥ 0,
and thus θP + (1 − θ)Q also lies in this set.
√ The second condition implies u, v ∈ [−π/2, π/2]. Using

(b) Convex. the hint, cos(u +
v) ≥ 2/2 if and only if −π/4 ≤ u + v ≤ π/4. As f (u, v) = u + v 2 is convex, the
2
given set can be written as
{(u, v) | −π/4 ≤ u + v ≤ π/4} ∩ {(u, v) | f (u, v) ≤ π 2 /4}.
(The second set is also the ball of radius π/2 centered about the origin in R2 .) The
intersection of a slab with a sublevel set of a convex function is convex.
2
(c) Convex. The function f (x) = xT A−1 x is concave, since its Hessian is 2A−1 which
is negative semidefinite since A ≺ 0. This set is the 0-superlevel set of a concave
function, hence convex. Another valid argument would be that if A ≺ 0, then
A−1 ≺ 0, so xT A−1 x < 0 for all nonzero x ∈ Rn . In particular, this means that the
set is just {0}, which is convex.
5. DCP compliance. Determine if each expression below is (sign-sensitive) DCP compliant,

and check the applicable box.
(a) sqrt(1 + 4 * square(x) + 16 * square(y))
DCP convex DCP concave not compliant
(b) min(x, log(y)) - max(y, z)
(c) log(exp(2 * x + 3) + exp(4 * y + 5))
Solution.
p
(a) Not compliant. Although the function √ 1 + 4x2 + 16y 2 is convex, the given com-
position violates the DCP ruleset, since u is concave (so any precomposition could
only result in a concave function, under the DCP rules). One way to reformulate
this function is norm2(1, 2 * x, 4 * y), which is the composition of an affine
function with the norm, thus DCP convex.
(b) DCP concave. The minimum of two concave functions is concave, and the maximum
of two affine functions is convex, so the given function is concave and also complies
with the DCP rules.
(c) Not compliant. Although the function log(exp(2x + 3) + exp(2y + 5)) is convex,
the given composition violates the DCP ruleset, since log is concave and increasing
(in particular, any precomposition could only result in a concave function, under the
DCP rules). One way to reformulate this function is log_sum_exp(2 * x + 3, 4 * y + 5),
which is the precomposition of the (convex) function log-sum-exp with affine func-
tions.

Midterm 18s Sol

Uploaded by

Copyright:

Available Formats

Midterm 18s Sol

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Midterm 18s Sol

Uploaded by

Copyright:

Available Formats

EE 364a: Convex Optimization I R.

Midterm Quiz Solutions

3. Curvature of some functions. Determine the curvature of the functions below.

with dom f = {x | aTi x < bi , i = 1, . . . , m}, and ai ∈ Rn , b ∈ Rm

4. Convexity of some sets. Determine if each set is necessarily convex.

xT (θP + (1 − θ)Q)x = θxT P x + (1 − θ)xT Qx ≥ 0,

and thus θP + (1 − θ)Q also lies in this set.

√ The second condition implies u, v ∈ [−π/2, π/2]. Using

given set can be written as

{(u, v) | −π/4 ≤ u + v ≤ π/4} ∩ {(u, v) | f (u, v) ≤ π 2 /4}.

5. DCP compliance. Determine if each expression below is (sign-sensitive) DCP compliant,

You might also like