坐标下降法（）是一种非梯度优化算法。算法在每次迭代中，在当前点处沿一个坐标方向进行以求得一个函数的局部极小值。在整个过程中循环使用不同的坐标方向。对于不可拆分的函数而言，算法可能无法在较小的迭代步数中求得最优解。为了加速收敛，可以采用一个适当的坐标系，例如通过主成分分析获得一个坐标间尽可能不相互关联的新坐标系（参考）。
算法描述
坐标下降法基于的思想是多变量函数F(\mathbf{x})可以通过每次沿一个方向优化来获取最小值。与通过梯度获取最速下降的方向不同，在坐标下降法中，优化方向从算法一开始就予以固定。例如，可以选择线性空间的一组基\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n 作为搜索方向。 在算法中，循环最小化各个坐标方向上的目标函数值。亦即，如果\mathbf{x}^k已给定，那么，\mathbf{x}^{k+1}的第i个维度为
: \mathbf{x}^{k+1}_i = \underset{y\in\mathbb R}{\operatorname{arg\,min}}\; f(x^{k+1}_1,...,x^{k+1}_{i-1},y,x^k_{i+1},...,x^k_n);
因而，从一个初始的猜测值\mathbf{x}_0以求得函数F的局部最优值，可以迭代获得\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots的序列。
通过在每一次迭代中采用，可以很自然地获得不等式
:F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,
可以知道，这一序列与最速下降具有类似的收敛性质。如果在某次迭代中，函数得不到优化，说明一个驻点已经达到。
这一过程可以用下图表示。
例子
对于非平滑函数，坐标下降法可能会遇到问题。下图展示了当函数等高线非平滑时，算法可能在非驻点中断执行。
应用
坐标下降法在机器学习中有应用，例如训练线性支持向量机（可见）以及。
参见
*
- 共轭梯度法
- 梯度下降法
- 牛顿法
- 最优化
*
参考
*
- Bertsekas, Dimitri P. (1999). Nonlinear Programming, Second Edition Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0.
- .
*.
*.
*.
*.
评论 (0)