CS205A HW5

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾作业5。

Problem 1

(a)

令第一个式子为$\vec 0$可得

因为$A$正定,所以$\vec x’ ​$是极小值点。

(b)首先考虑如何将两个向量变成$A-$共轭,假设两个向量为$\vec v_1, \vec v_2$,取$\vec w_1=\vec v_1$,设

要使得$\vec w_1, \vec w_2​$为$A-​$共轭,那么

不难看出

接着,假设我们已经有了$k$个$A-$共轭向量$\vec w_1 ,\ldots ,\vec w_k​$,并且

现在讨论如何获得第$k+1$个$A-$共轭向量$\vec w_{k+1}$,假设

我们需要的条件为

那么$\forall 1\le i \le k$

显然有

上述讨论可以得到如下算法:

  1. 对$k=2…n​$

    1. 对$i=1,\ldots ,k-1$,计算

Problem 2

(a)拉朗格朗日乘子为

所以KKT条件为

  1. stationarity

  2. primal feasibility

  3. complementary slackness

  4. dual feasibility

(b)令

那么

所以新的线性规划问题为

(c)对偶问题可以化为

所以stationarity条件为

带回原式可得

complementary slackness条件为

所以在最优解处

因为驻点唯一,所以如下方程的解唯一:

设上述方程的解为

所以最优解满足

因为原始问题的驻点唯一,所以原始问题的解唯一,设为$\vec x’$,那么最优解为

其中$\vec x ‘​$满足

此即为对偶问题的解。注意(3)(4)和(5)(6)的形式一致,所以(3)(4)相等,即原问题和对偶问题的最优值相同。

Problem 3

(a)(i)取

(ii)因为

所以随机梯度下降法计算的梯度为

(b)(i)不一定,如果$f$无下界,那么无法收敛到局部最小值。

(ii)利用单调有界数列必收敛即可。

Problem 4

$\vec x​$是Pareto optimal的含义为

(i)如果第一个条件不成立,即$\forall y,i$,

如果$f_i​$全部相同,那么结论显然;如果$f_i​$不全相同,那么不妨设$f_i \neq f_j​$,那么必然存在函数值不相同的点$\vec x​$,设

(b)首先由$f_i$的凸性以及$\vec \gamma \ge \vec 0$,我们可得$g$也是凸函数,所以存在最小值。接着将$\gamma_i$视为变量,所以得到如下优化问题

构造拉格朗日乘子:

关于$\vec x, \gamma$求梯度并为$0$可得

所以

对偶互补条件为

因为

所以

因此

以及

注意我们有

如果不存在$i ,\vec x $,使得

那么必然有

所以$\forall i,\vec x $,

此时$\vec x’ ​$是Pareto optimal。

如果存在$i ,\vec x $,使得

那么$\vec x’ $同样是Pareto optimal。

(c)感觉原题有误,$\vec x’$应该是Pareto dominate。

关于$\vec x ​$求梯度可得

因为$\forall i$

以及$\nabla^2 f_i(\vec x) \ge $(半正定),所以$\nabla^2 h(\vec x)$半正定,因此最小值点唯一。

注意$\forall \vec x \neq \vec x’$

所以必然存在$i​$,使得

因此$\vec x’​$是Pareto dominate。

Problem 5

(a)当满足如下条件时$f​$取最小值

(b)

所以

所以

(c)显然

从这个角度来说这步更新是好的。

(d)注意最优点为

这和$\vec x_0 $的方向一致,但是和$\vec x_1 $的方向不一致,所以从这个角度来说不是一个好的更新。

本文标题:CS205A HW5

文章作者:Doraemonzzz

发布时间:2019年04月24日 - 00:37:00

最后更新:2019年04月24日 - 16:17:18

原始链接:http://doraemonzzz.com/2019/04/24/CS205A HW5/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。