課程名稱︰ 機器學習特論
課程性質︰ 選修
課程教師︰ 林智仁
開課學院： 電資院
開課系所︰ 資工系
考試日期（年月日）︰2017/5/23
考試時限（分鐘）： 210 (吧)
試題 :
● Please give details of your answer. A direct answer without explanation is
not counted.
● Your answers must be in English.
● You can bring notes and the textbook. Other books or electronic device are
not allowed.
"""
數學式用latex格式表示
可以丟到這個網站去看看原樣
https://www.codecogs.com/latex/eqneditor.php
數學式會用$$夾起來
"""
Problem 1 (5 pts)
A function $f: R^n \rightarrow R$ is call separable if
$f(x) = f_1(x_1) + f_2(x_2) + ... + f_n(x_n)$ (1)
Is the conjugate function also separable?
Problem 2 (10 pts)
Consider the following optimization problem
min $\frac{4}{3}(x_1^2 - x_1 x_2 + x_2^2)^{\frac{3}{4}} - x_3$
subject to $x_3 \leq 2,x_1 \geq 0, x_2 \geq 0, x_3 \geq 0$ (2)
(a) (5 pts) What is its solution?
(b) (5 pts) Does the solution satisfy KKT condition?
Problem 3 (15 pts)
Consider
min $f_0(x)$
subject to $f_1(x) \leq 0$,
where $x \in R^1$
Given an example (may not be convex problem) so that
● $f_0(x),f_1(x)$ are differentiable
● slater condition holds
● KKT condition holds
● strong duality does not hold.
Show that your example satisfies the required conditions and explain the
failure of strong duality using the way on slides 5-15 and 5-16.
Problem 4 (25 pts)
Consider the following linear program
min $c^T x$
subject to $Ax = b$
$-1 \preceq x \preceq 1$
(a) (5 pts) Derive the dual problem
max $-b^T \nu -1^T \lambda_1 - 1^T \lambda_2$
subject to $c + A^T \nu + \lambda_1 - \lambda_2 = 0$ (3)
$\lambda_1 \preceq 0, \lambda_2 \preceq 0$
by checking the Lagrange dual.
(b) (5 pts) Prove that for any optimal $(\nu^*,\lambda_1^*,\lambda_2^*)$ of (3)
$(\lambda_1^*)_i(\lambda_2^*)_i = 0, \forall 1 \leq i \leq n$
(c) (8 pts) On page 5-27, we derive another dual problem
max $-b^T \nu - ||A^T + c||_1$ (4)
Assume $(\nu^*, \lambda_1^*,\lambda_2^*)$ is optimal for (3). Can you
formally prove that $\nu^*$ is the optimal for (4)?
(d) (7 pts) Similarly, if $\bar{\nu}$ is optimal for (4), can you prove the
existance of $(\bar{\nu},\bar{\lambda_1},\bar{\lambda_2})$ such that it
is the optimal for (3).
Problem 5 (30 pts)
Consider the following optimization problem
min $-3x_1 - 5x_2$
subject to $x_1 \leq 4$
$9 x_1^2 + 5 x_2^2 \leq 216$ (12)
$x-1 \geq 0, x_2 \geq 0$
(a) (5 pts) Is this a convex optimization problem? Draw a figure to show the
feasible region.
(b) (10 pts) Is slater condition satisfied? Solve this optimization problem
via KKT condition. We mean that you derive solutions from KKT rather than
showing that some points satisfy KKT. (Hint: The order of checking
$\lambda_1..., \lambda_4$ is important. Try to check $\lambda_3,\lambda_4$
first)
(c) (5 pts) On slide 4-9, we have that for convex problems,
x is optimal $\Leftrightarrow \bigtriangledown f(x)^T (y -x) \geq 0
\forall$ feasible y (13)
Can you directly prove that your optimal solution satisfies the condition?
(i.e. prove the "$\Rightarrow$" result).
(d) (10 pts) Derive the dual problem.
Problem 6 (15 pts)
Consider the following dual SVM problem:
min $\frac{1}{2} \alpha^T Q \alpha - e^T a$
subject to $y^T \alpha = 0, \alpha \succeq 0$ (18)
(a) (5 pts) Prove that if
${i|y_i = 1} \neq \phi$ and ${i|y_i = -1} \neq \phi$ (19)
then $\alpha = 0$ is not a dual optimal solution.
(b) (5 pts) Explain that the problem
min || \sum_{i = 1}^{N} \theta_i x_i - \sum_{i = 1}^{M} \gamma_i y_i||
subject to $\theta \succeq 0, 1^T \theta = 1, \gamma \succeq 0, 1^T \gamma=1$
(20)
on slide 8-10 can be written as
\min_{\beta} $\frac{1}{2}\beta^T Q \beta$ (21)
subject to $e^T \beta = 2, y^T \beta = 0, \beta \succeq 0$ (21)
Note that we slightly abuse the notation, In (20), $y_i$ is a negative
instance but in (21), y is the label vector.
(c) (5 pts) Assume that (19) holds and $\alpha$ is an optimal solution of (18).
Can you generate a solution for (21)? You need to prove that your solution
is optimal for (21).