凸优化上机作业

2019-12-20 本文已影响0人苏格兰低地弟弟打滴滴

结果简要分析：ALM和ADMM可以用比较少的迭代次数收敛到不错的结果，但是时间会比较长。如果迭代次数更多点应该是可以收敛更好。

采用线性化（一步精确最小用梯度下降替代）的方法，避免了矩阵求逆和乘法的运算，可以让计算速度显著提升，虽然迭代次数比较多，但是收敛的结果很好。

（一）增广拉格朗日解对偶问题：

对于原先的lasso问题，我们想要最小化 $\text { minimize } \quad(1 / 2)\|A x-b\|_{2}^{2}+\mu\|x\|_{1}$

等价于 $\min _{x, y} \mu\|x\|_{1}+\frac{1}{2}\|y\|_{2}^{2}\\ s.t. y=A x-b$

写出对偶问题: $\begin{array}{l} {\min -b^{T} y+\frac{1}{2}\|y\|^{2}} \\ {\text { s.t. } z=A^{T} y} \\ {\|z\|_{\infty} \leq \mu} \end{array}$

写出增广拉格朗日函数：

${L(y, z, x)=-b^{T} y+\frac{1}{2}\|y\|_{2}^{2}+I_{||.||_{\infty}\leq\mu}(z)+x^{T}\left(A^{T} y-z\right)+\frac{t}{2}\left\|A^{T} y-z\right\|_{2}^{2}}$

根据ALM我们有下面的迭代形式：

先把对偶的变量做最小化： $\left(y^{k+1}, z^{k+1}\right)=\arg \min L\left(y, z,x^{k}\right)$

然后再对x做最小化： $x^{k+1}=x^{k}+t\left(A^{T} y^{k+1}-z^{k+1}\right)$

代码实现：设置了一个 $\mu_1=100$ ，然后取代原问题的 $\mu$ 逐步让他下降（具体见本文（三）中的说明）

最后收敛的结果是fval= 0.0813和cvx_mosek算出的解的输出值相差 4.2459e-04，两个解之间的errfun是 0.0047，t= 23.2169, iter= 6940。

所以这个方法并没有收敛的很好，而且其中有高维矩阵的求逆运算，所以迭代次数少但是时间很长。（相比起本文（三））

（二）ADMM解对偶问题：

增广拉格朗日之前和上面思路一样，不同的是现在要对y z x交替优化：

先更新z： $z^{k+1}=\arg \min L\left(y^{k}, z, x^{k}\right)$ 这一步的操作是投影到无穷范数球中。

再更新y： $y^{k+1}=\arg \min L\left(y, z^{k+1}, x^{k}\right)$ 这一步有闭合的表达式：

$y^{k+1} =\left(I+t A A^{T}\right)^{-1}\left(t A z^{k+1}+b-A x^{k}\right)$

但是会有高维矩阵求逆的运算。

最后是对x更新 $x^{k+1}=x^{k}+t\left(A^{T} y^{k+1}-z^{k+1}\right)$

代码实现：见代码文件

最后收敛的结果是fval= 0.0812和cvx_mosek算出的解的输出值相差 3.6905e-04，两个解之间的errfun是 0.0041，t= 6.0506, iter= 1820。

所以这个方法并没有收敛的很好，但是比ALM时间短，迭代次数少。

（三）原问题线性化：

对于原先的lasso问题，我们想要最小化 $\text { minimize } \quad(1 / 2)\|A x-b\|_{2}^{2}+\mu\|x\|_{1}$

写成可以应用ADMM的形式： $min \quad(1 / 2)\|A x-b\|_{2}^{2}+\mu\|z\|_{1} \\ st \quad x-z=0$

写出增广拉格朗日函数：

$\frac{1}{2}\|A x-b\|_{2}^{2}+\mu\|z\|_{1}+y^{\top}(x-z)+\frac{\rho}{2}\|x-z\|_{2}^{2}$

分别最小化x，z，y，其中在最小化x的时候为了避免矩阵求逆的操作，我们直接采用一步梯度下降（不做精确的最小化）

迭代形式为：

$x^{k+1}:=x^{k}-\eta\left[A^{T}\left(A x^{k}-b\right)+y^{k}+\rho\left(x^{k}-z^{k}\right)\right]$

$z^{k+1}:=S_{\lambda / \rho}\left(x^{k+1}+y^{k} / \rho\right)$

$y^{k+1}:=y^{k}+\rho\left(x^{k+1}-z^{k+1}\right)$

其中S是 shrinkage 函数

代码实现：设置了一个 $\mu_1=100$ ，每次对每个mu1做一定的次数迭代之后让 $\mu_1=\mu_1/10$ ，直到和 $\mu=1e-3$ 相等。前几次作业的经验是这样可以减少迭代的次数。

在这个问题里操作的时候对每一步的迭代次数和迭代步长选择如下：

(步长取到e-3级别都会发散）

以往的问题里每个步骤的迭代次数是一样的。但是这个问题我发现在 $\mu_1=0.1,1$ 的时候适当增加迭代次数会收敛得更好。

最后收敛的结果是fval= 0.0809 和cvx_mosek算出的解的输出值相差 4.8741e-06，两个解之间的errfun是1.7773e-05，t= 2.7666, iter=12000。

上一篇下一篇

猜你喜欢

热点阅读