坐标下降法代码_海尔bcd-225wdgk「建议收藏」

大家好，欢迎来到IT知识分享网。

前言

本文简要介绍两种非梯度优化方法：坐标下降法和块坐标下降法。二者用于求解无约束优化问题，属于直接法。

我一直没太搞清楚坐标下降和坐标轮换的区别，但感觉应该是一个东西？都是循环沿单一维度进行线性搜索直至函数收敛，只是看很多坐标轮换法的介绍文章，提到该方法无需知道目标函数的解析式，但其实二者本质应该是一样的吧。另外，坐标下降和坐标上升是一对，前者用于求解最小化问题，后者用于求解最大化问题。

一、坐标下降法（Coordinate Descent）

• 基本思想：每次迭代只沿单一维度搜索，得到当前维度的极小值之后再循环沿其它维度搜索，最终收敛得到目标函数的极小值。也就是每次迭代只对一个变量进行优化，而固定其它变量的值。

• 算法原理：

  对于目标函数 \(f(\mathbf{x})\) ，\(\mathbf{x}=\{x_1,x_2,\cdots,x_n\}\) ，利用 CD 法求解该函数的最小值过程可以表示为：

  repeat

  \[\begin{aligned} &x_{1}^{(k)}=\underset{x_{1}}{\arg \min } f\left(x_{1}, x_{2}^{(k-1)}, x_{3}^{(k-1)}, \ldots x_{n}^{(k-1)}\right) \\ &x_{2}^{(k)}=\underset{x_{2}}{\arg \min } f\left(x_{1}^{(k)}, x_{2}, x_{3}^{(k-1)}, \ldots ,x_{n}^{(k-1)}\right) \\ &\ldots \\ &x_{n}^{(k)}=\underset{x_{n}}{\arg \min } f\left(x_{1}^{(k)},x_{2}^{(k)}, x_{3}^{(k)}, \ldots ,x_{n}\right) \end{aligned} \]

  until convergence

  其中，\(k\) 代表第 \(k\) 次迭代，每次对单变量求最小值时，若该函数可微，则可以令 \(\partial f(\mathbf{x})/\partial x_i=0\) 求解；若不可微，则可以利用黄金分割法、进退法等一维搜索方法求解。

• 算法特点：

  1. 无需计算梯度，逻辑简单，但计算效率低，适用于低维优化问题；

  2. 搜索方向的顺序是任意的，可选择 \(\{1,2,\cdots,n\}\) 的任意排列；

  3. 收敛程度很大程度上取决于目标函数等值线的形状；

     • 等值线为椭圆族，其长短轴与坐标轴平行时，收敛很快，即 \(\mathbf{x}\) 的维度步数即可收敛；

     • 当椭圆族的长短轴与坐标轴斜交时，迭代次数将大大增加，收敛速度慢；

     • 当目标函数等值线出现“脊线”时，沿坐标轴方向搜索不能使得函数值有所下降,坐标轮换法在求优过程中将失败,这类函数对于坐标轮换法就是病态函数。

       

  4. 只能得到局部极小值，为得到更好的解，需要选择多个初始点求解再选择。

  5. 若变量间的相关性很高，收敛过程会非常缓慢，可以利用主成分分析法（Principle Components Analysis，PCA）获得尽可能独立的变量进行优化。

二、块坐标下降法（Block Coordinate Descent，BCD）

BCD 法是 CD 法的一般化，用于解决 CD 法效率低下的问题。

• 基本思想：每次迭代对变量的子集进行优化，即每次沿着多个坐标轴的方向（超平面）取极值。其下降过程中子集的更新顺序可以是确定的也可以是随机的。子集的更新方法可参考： 非线性规划:坐标下降&&块坐标下降 一文。

• 算法通用框架：

  优化问题：\(\underset{\mathbf{x}}{\operatorname{minimize}} F\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{s}\right) \equiv f\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{s}\right)+\sum_{i=1}^{s} r_{i}\left(\mathbf{x}_{i}\right)\)

  其中，\(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_s\) 都是变量 \(\mathbf{x}\) 的子集。

  

参考链接

• 非线性规划:坐标下降&&块坐标下降
• 无约束优化方法-直接方法（坐标轮换法）
• 优化算法——坐标下降法(Coordinate Descent)
• 坐标上升/下降算法