課程名稱︰凸函數最佳化 (Convex Optimization) 課程性質︰電機所、電信所選修 課程教師︰蘇柏青 開課學院：電機資訊學院 開課系所︰電信所 考試日期（年月日）︰2018 年 6 月 28 日 考試時限（分鐘）：14:20 ~ 17:20 (不延長) 試題 : Convex Optimization - Final Exam, Thursday June 28, 2018. Exam policy: Open book. You can bring any books, handouts, and any kinds of paper-based notes with you, but use of any electronic devices (including cell- phones, laptops, tablets, etc.) is strictly prohibited. Note: the total score of all problems is 112 points. 1. (45%) For each of the following optimization problems, find (i) the lagrangian L(x,λ,μ), (ii) dual function g(λ,μ), and (iii) the dual problem. (a) (5% + 5% + 5%) minimize (x^T)x subject to Ax <= b where A ∈ R^(m*n) and b ∈ R^m. (b) (5% + 5% + 5%) minimize (x^T)Px subject to (x^T)x <= 1 Ax = b where P ∈ (S^n)++. (c) (5% + 5% + 5%) minimize 2 * x_1 + 3 * x_2 + 4 * x_3 subject to x_1 [1 0] + x_2 [1 1] + x_3 [1 -1] <= [0 1] [0 1] [1 1] [-1 2] (S^2)+ [1 0]. Hint: the Lagrange multiplier for this problem is in the form of a symmetric matrix. You can use the notation Z, as in, e.g., L(x,Z) and g(Z), etc. 2. (40%) Consider the equality constrained problem n minimize f_0(x) = (c^T)x + Σ (x_i)^3 i=1 subject to Ax = b where x ∈ dom f_0 = (R^n)+, A ∈ R^(p*n), rank A = p, b ∈ R^p, and c ∈ R^n. (a) (10%) Derive the Lagrange dual function g(μ) of the problem (2a). Find also dom g. (b) (5%) Formulate the dual problem of the problem (2a). (c) (10%) Derive ▽f_0(x) and ▽^2 f_0(x). (d) (5%) Find the KKT conditions for the problem (2a). (e) (10%) Given a feasible point x (i.e., Ax=b), derive the Newton's step △x_nt by writing down a linear system in which (△x_nt,μ+) is the variable (μ+ is the updated version of dual variable μ): [ M_1 M_2 ] [ △x_nt ] = [ v_1 ] [ M_3 M_4 ] [ μ+ ] [ v_2 ]. Find M_1, M_2, M_3, M_4, v_1, and v_2 explicitly. 3. (15%) Consider the simple problem minimize x^2 - 1 subject to 1 <= x <= 3 whose feasible set is [1,3]. Suppose you are going to apply the barrier method to this problem (whose objective function is denoted f_0 and constraint functions f_1 and f_2). (a) (6%) Derive t*f_0 + Φ as a function of x, where t is any given positive number and Φ denotes the logarithmic barrier for the original problem. (b) (7%) Find the optimal point for the "approximated" problem minimize t*f_0 + Φ x for any given t > 0. In other words, find the central point x*(t) for any given t > 0. (c) (2%) What is lim x*(t)? t→∞ 4. (12%) For the following pairs of proper cones K ⊆ R^q and functions ψ: R^q → R, determine whether ψ is a generalized logarithm for K. Briefly explain why. (a) (4%) K = (R^3)+, ψ(x) = log(x_1) + log(x_2) + log(x_3). (b) (4%) K = (R^3)+, ψ(x) = log(x_1) + 2 * log(x_2) + 3 * log(x_3). (c) (4%) K = (R^2)+, ψ(x) = log(x_1) - log(x_2). --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.235.34.5 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1533382392.A.4EC.html