課程名稱︰凸函數最佳化
課程性質︰電機所選修
課程教師︰蘇柏青
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰110.04.22
考試時限（分鐘）：120
試題 :
（註：以下部分數學式以latex語法表示）
1. (32%) For each of the following functions, prove or disprove if it is a con-
vex function.
(a) (8%) f : R^n -> R with f(x) = - \Pi_{i=1}^{n} x_{i}^{αi}
and dom f = R_{++}^n where 1^{T}α = 1.
(b) (8%) f : R^n -> R with f(y) = sup_{x \in C} a^{T}x
where a \in R^n is a constant vector and C = {x \in R^n | ||x||_2 = 1}
(c) (8%) f : R^n -> R with f(y) = inf_{x \in D} ||y-x||_p
where a \in R^n is a constant vector and D = {x \in R^n | ||x||_2 ≦1}
(d) (8%) f : R^n -> R with f(x) = ||Ax-b||_{2}^{2} / (1-x^{T}x)
and dom f = {x \in R^n | ||x||≦1} for any A \in R^{m*n} and b \in R^m
2. (19%) Consider the complex least l_p-norm problem
minimize ||x||_p
subject to Ax = b
where A \in C^{m*n}, b \in C^m and the variable is x \in C^n. Here ||‧|| deno-
tes the l_p norm on C^n, define as
||x||_p = (\sum_{i=1}^{n} |x_i|_^p)^{1/p}
for p≧1 and ||x||_{infty} = max_{i=1,...,n} |x_i|. We assume A is full rank,
and m < n.
(a) (9%) Reformulate the complex least l_2-norm problem as a least l_2-norm pr-
oblem with real problem data and variable.
Hint: Use z = (Re(x), Im(x)) \in R^{2n} as the variable.
(b) (9%) Reformulate the complex least l_{\infty}-norm problem as an SOCP.
3. (20%) Consider a linear program
minimize c^{T}x
subject to Ax \preceq b
where c \in R^n is uncertain and lies in an ellipsoid
ε = {\bar{c} + Pu | ||u||≦1} with P \in R^{n*n}. We intend to study the robu-
st linear program and minimize the largest possible value of c^{T}x among all
c \in ε, that is,
minimize sup_{c \in ε} c^{T}x
subject to Ax \preceq b (1)
(a) (10%) Determine if Problem (1) is a convex problem. Why?
(b0 (10%) Try to rewrite Problem (1) as an equivalent problem in the form of e-
ither a QCQP or an SOCP. Explain why the new problem you write is a QCQP (or an
SOCP). IF you find that it is not possible, please also explain why it is so.
4. (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 QCQP, (5) a
SOCP, (6) a quasi-convex optimization problem. Write your answer as a table of
5 rows and 6 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 - 2n_w} where n_c and n_w are
the numbers of correct answers and wrong answers (not including those left bla-
nk).
(a) minimize (c^{T}x)^2
subject to x^{T}Px≦1
where P \in S_{++}^n.
(b) minimize 2x_1 + 3x_2
subject to \sqrt{x_{1}^2 + 4x_{2}^2 + 9x_{3}^3}
≧ 4x_1 + 3x_2
(c) minimize x_{1}^2 + x_{2}^2
subject to x_1 + x_2 = 1
x_1 - x_2 ≦ 0
(d) minimize x_{1}^2 + 2x_{2}^4 + 3x_{3}^6
subject to x_1 + x_2 - x_3 ≦ 1
(e) maximize log(\sum_{k=1}^{n} x_k)
subject to c^{T}x ≧ 1
where c \in R^n.