課程名稱︰凸函數最佳化
課程性質︰電機所選修
課程教師︰蘇柏青
開課學院：電資學院
開課系所︰電機所
考試日期（年月日）︰108.04.25
考試時限（分鐘）：120
試題 :
（註：以下部分數學式以latex語法書寫）
1. (30%) For the following optimization problems, determine whether each of th-
em is (1) a convex optimization problem, (2) an LP, (3) a QP, (4) a QCOP, (5) a
SOCP. Write your answer as atable of 4 rows and 5 columns, with each entry bei-
ng T (yes), F (no), or left blank. The score you get in this section is
s = max{0, 1.5n_c - 3n_w} where n_c and n_w are the numbers of correct answers
and wrong answers (not including those left blank).
(a) minimize c^{T}x
subject to x_{1}^2 + x_{2}^2 + ... + x_{n}^2 ≦ 1
where c \in R^n.
(b) minimize 3x_1 + 2x_2 + x_3
subject to \sqrt{x_{1}^2 + 4x_{2}^2 + 9x_{3}^2}
≦ 2x_1 + x_2
(c) minimize (x_{1}^3 + x_{2}^3 + x_{3}^3)^{1/3}
subject to x_1 - x_2 = 1
x_1 - x_2 + x_3 ≦ 0
(d) minimize x_{1}^2 + x_{2}^2 + x_{3}^2
subject to -3x_1 - 4x_2 - 5x_3 ≦ 1
2. (30%) For each of the following sets, prove or disprove if it is convex. If
it is, write down your proof (i.e. showing that for any x and y in the set and
for any θ \in [0,1], θx + (1-θ)xy is also in the set). If it is not convex,
please find x, y, and θ that violate the convex property described above.
(a) C_1 = {a \in R^k | p(0) = 1, |p(t)|≦1 for -3≦t≦5} where
p(t) = a_1 + a_{2}t + ... + a_{k}t^{k-1}.
(b) C_2 = C_1 - 2C_2 where C_1 \subseteq R^k and C_2 \subseteq R^k are both co-
nvex sets.
(c) C_3 = {x \in R^k | (|x_1|^{1/2} + |x_2|^{1/2} + ... + |x_k|^{1/2})^2≦1}.
(d) C_4 = {x \in R_{++}^k | \Pi_{i=1}^{k} x_i≦1}.
(e) C_5 = {x \in S^n | z^{T}Xz≧1, \forall z \in R^n, ||z||_2 = 1}.
3. (22%) True and False. The score you get in this section is
s = max{0, 2n_c - 4n_w} where n_c and n_w are the numbers of correct answers
and wrong answers (not including those left blank).
(a) If C \subseteq R^n is an affine set. Then 0 \in C.
(b) A halfspace can be expressed as the intersection of two hyperplanes.
(c) A polyhedron is the intersection of a finite number of hyperplanes and hal-
fspaces, and therefore is always a convex set.
(d) An ellipsoid, defined as {x | (x - x_c)^{T}P^{-1}(x - x_c)≦1} for any giv-
en x_c \in R^n and P \in S_{++}^n is a convex set whose affine dimension is n.
(e) If a function f : R^n -> R is convex and concave at the same time, then it
is also an affine function.
(f) Every norm on R^n is convex.
(g) The epigraph of a function f : R^n -> R, defined as epi f = {(x,t) | x \in
dom f, f(x)≦t}, is a convex set if and only if f is a convex function.
(h) Let x_1, x_2 \in R^n. Then the set {x_1, x_2} is a convex set if and only
if x_1 = x_2.
(i) Suppose f : R^n -> R is twice differentiable. Then, f is strictly convex if
and only if its Hessian is always positive define (i.e., ▽^2f(x) \succ 0,
\forall x \in R^n).
(j) The α-sublevel set of a function f : R^n -> R, defined as C_α = {x \in
dom f | f(x)≦α}, is a convex set if and only if f is a convex function.
(k) A function f : R^n -> R is convex if and only if \forall x \in dom f, v \in
R^n, the function g(t) = f(x + tv) is convex on dom g = {t | x + tv \in dom f}.
4. (18%) Determine whether each of the following sets is a convex function, qu-
asi-convex function, concave function. Write your answer as a table of 6 rows
and 3 columns, with each entry being T (yes), F (no), or left blank. You don't
have to write down the proofs. The score you get in this section is
s = max{0, n_c - 2n_w} where n_c and n_w are the numbers of correct answers and
wrong answers (not including those left blank).
(a) f_1 : R^3 -> R, f_1(x) = x^{T}Px + q^{T}x + r where P \in S_{++}^3.
(b) f_2 : R -> R, f_2(x) = logx with dom f_2 = R_{++}.
(c) f_3 : S_{++}^3, f_3(x) = log(det(I + X)).
(d) f_4 : R^2 -> R, f_4(x) = (a^{T}x + b) / (c^{T}x + d) where a = [6 5]^T,
b = 4, c = [3 2]^T, and d = 1, with dom f_4 = {x \in R^2 | c^{T}x + d > 0}.