结果简要分析：ALM和ADMM可以用比较少的迭代次数收敛到不错的结果，但是时间会比较长。如果迭代次数更多点应该是可以收敛更好。
采用线性化（一步精确最小用梯度下降替代）的方法，避免了矩阵求逆和乘法的运算，可以让计算速度显著提升，虽然迭代次数比较多，但是收敛的结果很好。
（一）增广拉格朗日解对偶问题：
对于原先的lasso问题，我们想要最小化
等价于
写出对偶问题:
写出增广拉格朗日函数：
根据ALM我们有下面的迭代形式：
先把对偶的变量做最小化：
然后再对x做最小化：
代码实现：设置了一个，然后取代原问题的
逐步让他下降（具体见本文（三）中的说明）
最后收敛的结果是fval= 0.0813和cvx_mosek算出的解的输出值相差 4.2459e-04，两个解之间的errfun是 0.0047，t= 23.2169, iter= 6940。
所以这个方法并没有收敛的很好，而且其中有高维矩阵的求逆运算，所以迭代次数少但是时间很长。（相比起本文（三））
（二）ADMM解对偶问题：
增广拉格朗日之前和上面思路一样，不同的是现在要对y z x交替优化：
先更新z：这一步的操作是投影到无穷范数球中。
再更新y：这一步有闭合的表达式：
但是会有高维矩阵求逆的运算。
最后是对x更新
代码实现：见代码文件
最后收敛的结果是fval= 0.0812和cvx_mosek算出的解的输出值相差 3.6905e-04，两个解之间的errfun是 0.0041，t= 6.0506, iter= 1820。
所以这个方法并没有收敛的很好，但是比ALM时间短，迭代次数少。
（三）原问题线性化：
对于原先的lasso问题，我们想要最小化
写成可以应用ADMM的形式：
写出增广拉格朗日函数：
分别最小化x，z，y，其中在最小化x的时候为了避免矩阵求逆的操作，我们直接采用一步梯度下降（不做精确的最小化）
迭代形式为：
其中S是 shrinkage 函数
代码实现：设置了一个，每次对每个mu1做一定的次数迭代之后让
，直到和
相等。前几次作业的经验是这样可以减少迭代的次数。
在这个问题里操作的时候对每一步的迭代次数和迭代步长选择如下：
以往的问题里每个步骤的迭代次数是一样的。但是这个问题我发现在的时候适当增加迭代次数会收敛得更好。
最后收敛的结果是fval= 0.0809 和cvx_mosek算出的解的输出值相差 4.8741e-06，两个解之间的errfun是1.7773e-05，t= 2.7666, iter=12000。
