坐标下降法(Coordinate descent)

Dear 丶 2022-01-26 04:55 427阅读 0赞

坐标下降法属于一种非梯度优化的方法，它在每步迭代中沿一个坐标的方向进行搜索，通过循环使用不同的坐标方法来达到目标函数的**局部极小值**。

相当于每次迭代都只是更新x的一个维度，即把该维度当做变量，剩下的n-1个维度当作常量,通过最小化f(x)来找到该维度对应的新的值。坐标下降法就是通过迭代地构造序列x0,x1,x2,…

来求解问题，即最终点收敛到期望的局部极小值点。通过上述操作，显然有：

f(x0)≥f(x1)≥f(x2)≥…

相比梯度下降法而言，坐标下降法不需要计算目标函数的梯度，**在每步迭代中仅需求解一维搜索问题**，所以对于某些复杂的问题计算较为简便。但如果目标函数不光滑的话，坐标下降法可能会陷入非驻点。

### **注意事项** ###

关于坐标下降法，有几点需要注意的：

1.坐标下降的顺序是任意的，不一定非得按照从x1…xn的顺序来，可以是从1到n的任意排列。

2.坐标下降的关键在于一次一个地更新，所有的一起更新有可能会导致不收敛。

3.坐标上升法和坐标下降法的本质一样，只不过目标函数成为求f(x)的极大值了，每次迭代过程min变成max了。

### 首先介绍一个算法：coordinate-wise minimization ###

问题的描述：给定一个可微的凸函数![SouthEast][]，如果在某一点x，使得f(x)在每一个坐标轴上都是最小值，那么f(x)是不是一个全局的最小值。

形式化的描述为：是不是![SouthEast 1][]对于所有的d，i都有![SouthEast 2][]

这里的![SouthEast 3][]代表第i个标准基向量。

答案为成立。

![SouthEast 4][]

这是因为：

![SouthEast 5][]

但是问题来了，如果对于凸函数f，若不可微该会怎样呢？

![SouthEast 6][]

答案为不成立，上面的图片就给出了一个反例。

那么同样的问题，现在![SouthEast 7][]，其中g是可微的凸函数，每一个hi都是凸的？

答案为成立。

![SouthEast 8][]

证明如下，对每一个y

![SouthEast 9][]

## 坐标下降(Coordinate descent)： ##

这就意味着，对所有的![SouthEast 10][]，其中g是可微的凸函数，每一个hi都是凸的，我们可以使用坐标下降寻求一个最小值，我们从一个最初的猜想![SouthEast 11][]开始，对k进行循环：

![SouthEast 12][]

每一次我们解决了![SouthEast 13][]，我们都会使用新的值。

Tseng (2001)的开创性工作证明：对这种f（f在紧集![SouthEast 14][]上连续，且f到达了其最小值），![SouthEast 15][]的极限值，k=1,2,3….是f的一个最小元(minimizer)。

在实分析领域：

![SouthEast 16][]随后收敛与x\*( Bolzano-Weierstrass)

![SouthEast 17][]收敛于f\*( monotoneconvergence)

其中：

坐标下降的顺序是任意的，可以是从1到n的任意排列。

可以在任何地方将单个的坐标替代成坐标块

关键在于一次一个地更新，所有的一起更新有可能会导致不收敛

## 我们现在讨论一下坐标下降的应用： ##

## 线性回归： ##

令![SouthEast 18][]，其中![SouthEast 19][]，A有p列：![SouthEast 20][]

最小化xi，对所有的xj，j不等于i：

![SouthEast 21][]

解得：

![SouthEast 22][]

坐标下降重复这个更新对所有的![SouthEast 23][]

对比坐标下降与梯度下降在线性回归中的表现（100个实例，n=100，p=20）

![SouthEast 24][]

将坐标下降的一圈与梯度下降的一次迭代对比是不是公平呢？是的。

![SouthEast 25][]

其中r=y-Ax。每一次的坐标更新需要O(n)个操作，其中O(n)去更新r，O(n)去计算![SouthEast 26][]，所以一圈就需要O(np)，跟梯度下降是一样的。

![SouthEast 27][]

我们用相同的例子，用梯度下降进行比较，似乎是与计算梯度下降的最优性相违背。

那么坐标下降是一个一阶的方法吗？事实上不是，它使用了比一阶更多的信息。

## 现在我们再关注一下支持向量机： ##

SVM对偶中的坐标下降策略：

![SouthEast 28][]

SMO(Sequentialminimal optimization)算法是两块的坐标下降，使用贪心法选择下一块，而不是用循环。

回调互补松弛条件(complementaryslackness conditions)：

![SouthEast 29][]

v，d，s是原始的系数，截距和松弛，其中![SouthEast 30][]，使用任何的（1）中i使得![SouthEast 31][]来计算d，利用（1）（2）来计算2.

v，d，s是原始的系数，截距和松弛，其中，使用任何的（1）中i使得来计算d，利用（1）（2）来计算2.

SMO重复下面两步：

选出不满足互补松弛的αi，αj

最小化αi，αj使所有的变量满足条件

![SouthEast 32][]

第一步使用启发式的方法贪心得寻找αi，αj，第二步使用等式约束。  
\---------------------  
作者：花折泪  
来源：CSDN  
原文：https://blog.csdn.net/u013802188/article/details/40476989  
版权声明：本文为博主原创文章，转载请附上博文链接！

[SouthEast]: /images/20220126/c36565f4d0c3454ea72b356e232b526d.png
[SouthEast 1]: https://img-blog.csdn.net/20141026151445015?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220126/ef859683c2e14f12a02db99e260a7b00.png
[SouthEast 3]: /images/20220126/eba20f6b338440aa94f3706771636416.png
[SouthEast 4]: /images/20220126/978bf2aaacfc4107ac387ee6494f9319.png
[SouthEast 5]: /images/20220126/d7fcba1dea1643aebfbcc750a25358c5.png
[SouthEast 6]: /images/20220126/f3370b6ab33a466d9790bef35730f949.png
[SouthEast 7]: /images/20220126/6f14731212584c4a8fa20839047133c3.png
[SouthEast 8]: /images/20220126/22ab047a0449421daa80b2d5f52f0ced.png
[SouthEast 9]: /images/20220126/e0bc68cd8dc5419abddcda0dcbf5a224.png
[SouthEast 10]: https://img-blog.csdn.net/20141026151642561?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 11]: /images/20220126/aadd9eb52164482d95f1e6a76ea11393.png
[SouthEast 12]: /images/20220126/d9c179c1af23478a8638cd914fdcae83.png
[SouthEast 13]: /images/20220126/bb896faf130d4323834c516e49967743.png
[SouthEast 14]: https://img-blog.csdn.net/20141026151747098?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 15]: /images/20220126/447e6e0aab0f4192ac373a1ea577c945.png
[SouthEast 16]: /images/20220126/d4e8df6a17cf423581e1e3740e5f28f3.png
[SouthEast 17]: /images/20220126/54c8e30be3064970ae25f75fe448cc17.png
[SouthEast 18]: https://img-blog.csdn.net/20141026155427310?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 19]: https://img-blog.csdn.net/20141026155507980?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 20]: /images/20220126/7bd38c0155c04f2f84a4e83a43444365.png
[SouthEast 21]: /images/20220126/8cb0043e28e343dea92aa4cf688e3826.png
[SouthEast 22]: /images/20220126/17baf70ed994447597e289ce2df21182.png
[SouthEast 23]: /images/20220126/e93ea051140f4629bf6f832da360e32e.png
[SouthEast 24]: /images/20220126/1bca4c2a3fb743e89185b7077eb2f87a.png
[SouthEast 25]: /images/20220126/f30b6984123d471598c92471a097c5e8.png
[SouthEast 26]: /images/20220126/b87518914e5d47578232f5fa7fdc9c90.png
[SouthEast 27]: /images/20220126/91d48645fd3d45cb8033d620c45437ad.png
[SouthEast 28]: /images/20220126/76440bad0d554e5497ac20a5018f9b3f.png
[SouthEast 29]: /images/20220126/1f9d54d899674b179ff4059f17d85af5.png
[SouthEast 30]: https://img-blog.csdn.net/20141026155715869?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzgwMjE4OA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 31]: /images/20220126/d889789a915646ad84dba44ad7b262d3.png
[SouthEast 32]: /images/20220126/37c322338c1b4f42871cfe36a1ec23a0.png