坐標下降法

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

基本介紹

• 中文名：坐標下降法
• 外文名：coordinate descent
• 分類：最最佳化算法
• 套用：機器學習、支持向量機

算法描述

坐標下降法基於的思想是多變數函式 可以通過每次沿一個方向最佳化來獲取最小值。與通過梯度獲取最速下降的方向不同，在坐標下降法中，最佳化方向從算法一開始就予以固定。例如，可以選擇線性空間的一組基 作為搜尋方向。 在算法中，循環最小化各個坐標方向上的目標函式值。亦即，如果 已給定，那么， 的第 個維度為:

因而，從一個初始的猜測值 以求得函式 的局部最優值，可以疊代獲得 的序列。

通過在每一次疊代中採用一維搜尋，可以很自然地獲得不等式:

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

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

例子

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

套用

坐標下降法在機器學習中有套用，例如訓練線性支持向量機以及非負矩陣分解。