课程名称︰凸函数最佳化 (Convex Optimization)
课程性质︰电机所、电信所选修
课程教师︰苏柏青
开课学院：电机资讯学院
开课系所︰电信所
考试日期（年月日）︰2018 年 4 月 19 日
考试时限（分钟）：14:20 ~ 17:20 (不延长)
试题 :
Convex Optimization Midterm, Thursday April 19, 2018.
Exam policy: Open book. You can bring any books, handouts, and any kinds of
paper-based notes with you, but electronic devices (including cellphones,
laptops, tablets, etc.) are strictly prohibited.
1. (44%) Determine whether each of the following sets is a convex set, affine
set, subspace, cone. Write your answer as a table of 11 rows and 4 columns,
with each entry being T (yes), F (no), or left blank. The score you get in
this section is s = max {0, n_c - 0.25 * (n_w)^2} where n_c and n_w are the
numbers of correct answers and wrong answers (not including those left blank
).
1. S_1 = { x ∈ R^3 | [3 2 1] x = [1] }
{ | [4 5 6] [2] }.
2. S_2 = { x ∈ R^3 | [3 2 1] x <= [1] }
{ | [4 5 6] [2] }.
3. S_3 = { [1 2] [1] | }
{ [3 4] x + [2] | x ∈ R^2 }.
{ [5 6] [3] | }
4. S_4 = { [1] } ⊆ R^2.
{ [2] }
5. S_5 = { [1] [3] } ⊆ R^2.
{ [2], [4] }
6. S_6 = { x ∈ R^3 | (x_1)^2 + (x_2)^2 <= 1, (x_3) = 0 }.
7. S_7 = -(R^3)+.
8. S_8 = { x ∈ R^2 | (x_1)(x_2) = 0, x_1 >= 0, x_2 >= 0 }.
9. S_9 = { a ∈ R^n | |1 + (a_1)t + (a_2)t^2 + ... + (a_n)t^n| <= 1 for
α <= t <= β} for any given α,β ∈ R.
10. S_10 = { X ∈ S^n | (z^T)Xz >= 1, ∀z ∈ R^n, ||z||_2 = 1 }
11. S_11 = { x ∈ R^n | ||Px+q||_2 <= (c^T)x+r } given any P ∈ R^(m*n),
q ∈ R^m, c ∈ R^n, and r ∈ R.
2. (18%) Determine whether each of the following sets is a convex function,
quasi-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.
The score you get in this section is s = max{0, n_c - 0.25*(n_w)^2} where
nc and nw 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 ∈ (S^3)++.
(b) f_2: R → R, f_2(x) = x * log(x) 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 = [1 2]^T, b = 3, c = [4 5]^T, and d = 2, with dom f_4 =
{ x ∈ R^2 | (c^T)x+d > 0 }.
n
(e) f_5: R^n → R, f_5(x) = Π x_k .
k=1
(f) f_6: R^n → R, f_6(x) = log( 1 + ||x||_2 ).
3. (20%) For the following optimization problems, determine whether each of
them is (1) a convex optimization problem (*); (2) an LP, (3) a QP,
(4) a QCQP, (5) a SOCP. The score you get in this section is
s = max{0, n_c - 0.25 * (n_w)^2} where n_c and n_w are the numbers of
correct answers and wrong answers (not including those left blank).
(*) Note: for an equality constraint h_1(x) = h_2(x), we assume the
equality constraint function to be h(x) = h_1(x) - h_2(x); for an
inequality constriant f_1(x) <= f_2(x), we assume the corresponding
inequality constraint function to be f(x) = f_1(x) - f_2(x).
(a) minimize (c^T)x
subject to (x_1)^2 + (x_2)^2 + ... + (x_n)^2 = 1
where c ∈ R^n.
(b) minimize 3 * x_1 + 2 * x_2 + x_3
_______________________________
subject to V(x_1)^2 + 4*(x_2)^2 + 9*(x_3)^2 <= 2 (x_1 + x_2 + x_3)
(c) minimize (x_1)^2 + (x_2)^2 + (x_3)^2
subject to x_1 + x_2 = 1
x_1 - x_2 + x_3 <= 0
(d) minimize -3 * x_1 - 4 * x_2 - 5 * x_3
subject to (x_1)^2 + (x_2)^2 + (x_3)^2 <= 1
4. (16%) We consider a robust variation of the linear program:
minimize (c^T)x
subject to Ax <= b.
We assume that only the vector c ∈ R^n is subject to errors, and the other
parameters (A ∈ R^(m*n), b ∈ R^m) are exactly known. The robust program is
defined as
minimize sup { (c^T)x }
c∈ε
subject to Ax <= b.
where ε is the set of possible vectors c. For each of the following sets
ε, express the robust LP as a tractable convex problem (i.e., any of an LP,
QP, QCQP, or SOCP problem)
(a) (8%) A finite set of vectors: ε={c_1, c_2, ..., c_K}, where c_i ∈ R^n,
i = 1, ..., K.
(b) (8%) A set specified by a nominal value c_0 ∈ R^n plus a bound on the
deviation c - c_0:
ε = { c ∈ R^n | ||c-c_0||_2 <= γ}
where γ∈ R+ and c_0 ∈ R^n.
Hint. Think about epigraph and the technique of introducing slack variables.