坐標下降法

坐標下降法（英語：coordinate descent）是一種非梯度優化算法。算法在每次迭代中，在當前點處沿一個坐標方向進行一維搜索（英語：line search）以求得一個函數的局部極小值。在整個過程中循環使用不同的坐標方向。對於不可拆分的函數而言，算法可能無法在較小的迭代步數中求得最優解。為了加速收斂，可以採用一個適當的坐標系，例如通過主成分分析獲得一個坐標間儘可能不相互關聯的新坐標系（參考自適應坐標下降法（英語：Adaptive coordinate descent））。

算法描述

坐標下降法基於的思想是多變量函數${\displaystyle F(\mathbf {x} )}$可以通過每次沿一個方向優化來獲取最小值。與通過梯度獲取最速下降的方向不同，在坐標下降法中，優化方向從算法一開始就予以固定。例如，可以選擇線性空間的一組基${\displaystyle \mathbf {e} _{1},\mathbf {e} _{2},\dots ,\mathbf {e} _{n}}$作為搜索方向。 在算法中，循環最小化各個坐標方向上的目標函數值。亦即，如果${\displaystyle \mathbf {x} ^{k}}$已給定，那麼，${\displaystyle \mathbf {x} ^{k+1}}$的第${\displaystyle i}$個維度為

${\displaystyle \mathbf {x} _{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},...,x_{i-1}^{k+1},y,x_{i+1}^{k},...,x_{n}^{k});}$

因而，從一個初始的猜測值${\displaystyle \mathbf {x} _{0}}$以求得函數${\displaystyle F}$的局部最優值，可以迭代獲得${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots }$的序列。

通過在每一次迭代中採用一維搜索（英語：line search），可以很自然地獲得不等式

${\displaystyle F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,}$

可以知道，這一序列與最速下降具有類似的收斂性質。如果在某次迭代中，函數得不到優化，說明一個駐點已經達到。

這一過程可以用下圖表示。

例子

對於非平滑函數，坐標下降法可能會遇到問題。下圖展示了當函數等高線非平滑時，算法可能在非駐點中斷執行。

應用

坐標下降法在機器學習中有應用，例如訓練線性支持向量機^[1]（可見LIBLINEAR（英語：LIBLINEAR））以及非負矩陣分解（英語：non-negative matrix factorization）^[2]。

參見

• 自適應坐標下降法（英語：Adaptive coordinate descent）
• 共軛梯度法
• 梯度下降法
• 牛頓法
• 最優化
• 一維搜索（英語：line search）