課程名稱︰凸函數最佳化 (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).