課程名稱︰凸函數最佳化 課程性質︰電機所選修 課程教師︰蘇柏青 開課學院：電資學院 開課系所︰電機所 考試日期（年月日）︰108.06.20 考試時限（分鐘）：100 試題 : 註：以下部分數學符號與式子以LaTeX語法表示。 1. (15%) Consider the convex unconstrained optimization problem whose variable is x \in R^2: minimize f_0(x) = [x_1 x_2][5 1 \\ 1 5][x_1 x_2]. We will study some types of descent methods in this problem. (a) (3%) Find \nabla f_0, the gradient of f_0 for any x \in R^2. (b) (4%) Find \nabla^2f_0, the Hessian of f_0 for any x \in R^2. (c) (3%) Suppose the initial point is chosen to be x^{(0)} = [3 2]^T. Find the gradient descent direction \Delta x_{gd} (d) (5%) Again, let the initial point be x^{(0)} = [3 2]^T. Find the Newton st- ep \Delta x_{nt} 2. (45%) Consider the convex piecewise-linear minimization problem minimize \max_{i=1,...,m} (a_i^Tx + b_i) -- (1) with variable x \in R^n. Suppose the optimal value is attained and is p^*. (a) (5%) Find the Lagrange dual function of the problem (1). (b) (5%) Consider an equivalent problem minimize \max_{i=1,...,m} y_i -- (2) subject to a_i^Tx + b_i = y_i, i = 1,...,m, with variables x \in R^n, y \in R^m. Find the Lagrange dual function of problem (2). (c) (5%) Derive the dual problem for problem (2). (d) (5%) Formulate the piecewise-linear minimization problem (1) as an equival- ent LP. (Hint: by introducing a slack variable s and putting it in the objective function.) (e) (10%) Form the dual problem of the LP you obtained in (d). (f) (5%) For the LP you obtained in (d) (with variable \bar{x} = (x,s) \in R^{n+1}), and given the barrier method's parameter t, formulate the a- pproximated equality constrained (or unconstrained) problem. (g) (10%) Write down the KKT conditions of the problem you obtained in (f). 3. (25%) Consider the problem minimize (1/2)x^Tx + c^Tx subject to Ax \preceq b -- (3) where A \in R^{m\times n}. Suppose you are going to apply the barrier method to this problem, whose objective function is denoted f_0 and constraint functi- ons f_i, i=1,...,m. You can denote a_i^T by the ith row of the matrix A. (a) (10%) Derive tf_0 + \phi as a function of x, where t is any given positive number and \phi denotes the logarithmic barrier for problem (3). (b) (15%) For any given strictly feasible point x of (3), derive the Newton st- ep \Delta x_{nt} at for the "approximated" problem minimize _x tf_0 + \phi for any given t>0. 4. (15%) For the following pairs of proper cones K \subseteq R^q and functions \psi : R^q -> R, determine whether \psi is a generalized logarithm for K. Just- ify your answers. (a) (5%) K = R^3_+, \psi(x) = \log x_1 + 2\log x_2 + 3\log x_3. (b) (5%) K = R^3_+, \psi(x) = \log(x_1 + x_2 +x_3). (c) (5%) K = R^2_+, \psi(x) = \log x_1 - \log x_2. --

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