課程名稱︰凸函數最佳化 課程性質︰電機所選修 課程教師︰蘇柏青 開課學院：電資學院 開課系所︰電機所 考試日期（年月日）︰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}. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.104.253 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1619566534.A.9BB.html