【优化】一篇入门之-坐标下降算法

坐标下降法(Coordinate Descent)顾名思议就是按坐标轴(Coordinate )来迭代、使目标函数逐步下降的一种优化算法，机器学习中的Lasso回归模型、FA因子分析等模型，一般都是使用坐标下降法来进行求解，今天就带大家来看看坐标下降法是个什么东西吧！

一、坐标下降法

坐标下降法与梯度下降一类的算法不同，梯度下降一类的算法往往依靠梯度信息来小步迭代，而坐标下降法则是通过逐坐标优化的方式来优化目标函数，它每次都把一个参数，迭代到最优的位置，这使得它的优化速度往往更加的快：

如图所示，坐标下降法每次都固定其它参数，然后把其中一个参数迭代到最优位置，如此反复，直到满足终止条件。所以，要使用坐标下降法，就必须知道单个参数的位置在哪，一般来说，在目标函数可求单个变量的驻点时，就可以使用坐标下降法，因为单个参数的最优位置就是它的驻点。

坐标下降法每次只迭代一个参数，主要是考虑到单个参数的驻点相对比较容易求得，如果可以同时求得多个参数的驻点，也可以每次把几个参数一起迭代，这时就称为"块坐标下降法"了。

二、坐标下降法-算法流程

好了，下面我们来正式的看看坐标下降算法的详细算法流程。

2.1.坐标下降法-算法流程图

先来上个算法流程图，然后大家再结合下面的算法流程描述来理解。

2.2. 坐标下降法-算法流程描述

坐标下降法算法流程如下：

一、初始化

      初始化参数X，可以采用随机初始化

二、逐坐标优化

      1. 对所有随机(或按顺序)逐个优化：

          (1) 计算当前的驻点

          (2) 将x更新到驻点：

      2. 检查是否满足终止条件

          终止条件如下：

          (1) 是否达到最大迭代次数

          (2) 本次是否所有参数x的变化都很小

          (3) 本次函数下降是否过小

三、输出

      输出训练好的X

流程其实挺简单的，耐心看一下就明白了，如果还是不明白，再结合下面的代码来理解就好了。

三、坐标下降法-代码实现

好了，讲了那么多的理论，是时候用个实例来试试坐标下降法的效果。

不妨用它来求解 的极小值。

我们先来计算出的驻点，如下：

由 ，得到的驻点为：      

由 ，得到的驻点为： 

接下来按坐标下降法的算法流程进行迭代就可以了，具体代码如下：

"""
本代码用于展示坐标下降法求y= -x1^2-3*x2^2+2x1*x2的最小解
本代码来自《老饼讲解-机器学习》 www.bbblearn.com
"""
import numpy as np                      
x = np.array([100,500])                     # 初始化x
for i in range(100):                        # 迭代100次
    old_x = x.copy()                        # 先保存好未更新的x    
    x[0]  = x[1]                            # 更新x0到驻点
    x[1]  = x[0]/3                          # 更新x1到驻点
    y     = -x[0]**2-3*x[1]**2+2*x[0]*x[1]  # 计算目标函数值
    print(f"第{i}轮迭代:x= {x},y={y}")      # 打印结果
    if (max(abs(old_x-x))<0.001):           # 检查x是否变化都很小
        break                               # 满足上述条件,则退出迭代

代码运行结果如下：

可以看到，经过7轮迭代中，X不再变化，最终得到的解为，事实上，在代码中我故意设置了一个很离谱的初始值，但即使如此，坐标下降法也能很快地迭代到局部最优解，这就是坐标下降法的强大之处了。

总结

坐标下降法其实就是把参数轮流迭代到最优点，来使目标函数不断下降，它的速度比起其它算法相对更快，但要使用它，一般需要目标函数能求出单个参数的驻点。当然，也可以逐批参数轮流迭代，这时候就是"块坐标下降法"了。