1.坐标下降法
坐标下降法,是一种非梯度优化算法,算法在每次迭代中，在当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系.
对于一个函数,变量个数为n,也即坐标轴有n个,那么在固定n-1个轴,只在其中一个轴上求解极值,这个极值对应的也是全局极值,将所有的坐标轴循环一遍,就可以求得最优解,很多大规模的问题用这种方法都能够快速解决。
例子:
这个两维的函数的最优解是0，这个问题收敛是没有问题的，但它可能会慢一些。但对于一般问题，用CD还要注意一下，它不一定会收敛。
在什么情况下收敛？如果目标函数是光滑而且凸的，就一定会收敛。但很多问题不光滑，比如Lasso就不光滑，那怎么办？如果是不光滑的，只要光滑部分可分就可以了。在很多稀疏问题上，CD是可以保证是收敛的。
总结来说，当问题是光滑且凸的时候，坐标下降算法一定可以收敛，当问题不光滑的时候，当不光滑的部分是可分的，那么坐标下降算法也可以收敛。
坐标下降算法的优点是容易计算，同时收敛很快；缺点是当loss比较复杂时，会很明显的降低速度。
2.交替方向乘子法（ADMM）
假设有两个变量f(x)＋g(z)，然后给定一个约束，将其放入两组变量，我们可以首先生成增广拉格朗日，再增加penalty，然后就可以通过反复、依次对x、z、y优化，对模型求解。
ADMM对于大规模的问题非常有效，它能够将复杂问题变成很多个较为容易求解的问题。
我们以lasso为例，一个传统的LASSO是有一个loss加一个一范数约束，我们将x变成z，所以约束为z=x，就可以生成如下增广拉格朗日模型：
可以看出，求解x、z、u都非常容易，通过几个简单的更新就能将lasso，一个复杂的非凸问题对齐求解。
因此，ADMM的优点是解释非常简单，对于复杂模型也能够进行有效的处理，同时可以分布式的进行计算，并对低秩可以很快的学习；缺点是收敛比较慢。
3.梯度下降法（Gradient Descent）
梯度下降法可以有效求解光滑问题。通过不断的沿着梯度方向迭代，该方法就能求出凸光滑问题的解。
但是我们需要关注的问题是如何将梯度下降将其推广到非光滑的问题上面，这就要考虑梯度下降算法——
通过换一种表达方式，对其进行低阶的逼近，用一个低阶的taylor展开，做一个一阶的逼近，再利用正则项使得x在可行域范围内，对M函数找到最优的x，然后不断迭代。
通过数学验证可以发现，最优的x刚好等于梯度下降的值，也就是说，这种方式是梯度下降的另外一种表达方式，即将梯度下降转化为了一个有优化问题。
对于稀疏问题，我们每一步只需要最小化M函数和penalty之和。梯度下降的关键问题在于penalty。如果penalty简单，那么每一步最小化问题可能有解析解，如果penalty复杂，那么模型会很复杂，每一步的成本会很大。这个算法的另外一个好处是稍作变化后就可以加速。
