[SOLVED] Si251 – convex optimization homework 1

1. Please prove that the following sets are convex:
1) S = {x ∈ Rm | | p(t) |≤ 1 for |t| ≤ π/3}, where p(t) = x1 cost + x2 cos 2t + · · · +
xm cos mt. (5 pts)2) (Ellipsoids)
n
x|
p
(x − xc)
T P(x − xc) ≤ r
o
(xc ∈ R
n, r ∈ R, P ⪰ 0). (5 pts)3) (Symmetric positive semidefinite matrices) S
n×n
+ =
n
P ∈ S
n×n|P ⪰ 0
o
. (5
pts)
4) The set of points closer to a given point than a given set, i.e.,
n
x | ∥x − x0∥2 ≤ ∥x − y∥2 for all y ∈ S
o
,
where S ∈ Rn. (5 pts)2. (15 pts) For a given norm ∥ · ∥ on Rn, the dual norm, denoted ∥ · ∥∗, is defined as
∥y∥∗ = sup
x∈Rn
{y
T x | ∥x∥ ≤ 1}.Show that the dual of Euclidean norm is the Euclidean mom, i.e., supx∈Rn {z
T x | ∥x∥2 ≤
1} = ||z||2.3. (15 pts) Define a norm cone as
C ≡ 
(x, t) : x ∈ R
d
, t ≥ 0, ∥x∥ ≤ t⊆ R
d+1
Show that the norm cone is convex by using the definition of convex sets.4. (18 pts) Let C ⊂ R
n be convex and f : C → R⋆
. Show that the following statements are
equivalent:
(a) epi(f) is convex.
(b) For all points xi ∈ C and {λi
|λi ≥ 0,
Pn
i=1 λi = 1, i = 1, 2, · · · , n}, we have
f
Xn
i=1
λixi

≤
Xn
i=1
λif(xi).(c) For ∀x, y ∈ C and λ ∈ [0, 1],
f

(1 − λ)x + λy
≤ (1 − λ)f(x) + λf(y).5. (14 pts) Monotone Mappings. A function ψ : Rn → Rn is called monotone if for all
x, y ∈ domψ,
(ψ(x) − ψ(y))T
(x − y) >= 0. (1)Suppose f : Rn → Rn is a differentiable convex function. Show that its gradient ∇f is
monotone. Is the convex true, i.e., is every monotone mapping the gradient of a convex
function?6. (18 pts) Please determine whether the following functions are convex, concave or none of
those, and give a detailed explanation for your choice.
1)
f1(x1, x2, · · · , xn) = (
−(x1x2 · · · xn)
1
n , if x1, · · · , xn > 0
∞ otherwise;
2) f2(x1, x2) = x
α
1 x
1−α
2
, where 0 ≤ α ≤ 1, on R
2
++;
3) f3(x, u, v) = − log(uv − x
T x) on domf = {(x, u, v)|uv > xT x, u, v > 0}.