次梯度法

次梯度法是求解凸函數最優化（凸優化）問題的一種迭代法。次梯度法能夠用於不可微的目標函數。當目標函數可微時，對於無約束問題次梯度法與梯度下降法具有同樣的搜索方向。

雖然在實際的應用中，次梯度法比內點法和牛頓法慢得多，但是次梯度法可以直接應用於更廣泛的問題，次梯度法只需要很少的存儲需求。然而，通過將次梯度法與分解技術結合，有時能夠開發出問題的簡單分配算法。

基本次梯度算法

記$f:\mathbb {R} ^{n}\to \mathbb {R}$為定義在$\mathbb {R} ^{n}$上的凸函數。次梯度算法使用以下的迭代格式

$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$

其中$g^{(k)}$表示函數$f\$在$x^{(k)}\$的次梯度. 如果 $f\$可微，他的次梯度就是梯度向量$\nabla f$ ，有時$-g^{(k)}$不是函數$f\$在$x^{(k)}$處的下降方向。因此採用一系列可能的$f_{\rm {best}}\$來追蹤目標函數的極小值點，即

$f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}$。

步長的選取

次梯度方法有許多可採用的步長。以下為5種能夠保證收斂性的步長規則

• 恆定步長，$\alpha _{k}=\alpha$。
• 恆定間隔，$\alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2}$，得出$\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma$。
• 步長平方可加，但步長不可加，即步長滿足

$\alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty$。

• 步長不可加但步長遞減，即步長滿足

$\alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty$。

• 間隔不可加但間隔遞減，即$\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$，其中

$\gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty$。注意：上述步長是在算法執行前所確定的，不依賴於算法運行過程中產生的任何數據。這是與標準梯度下降法的顯著區別。

收斂結果

對於恆定間隔的步長以及恆定步長，次梯度算法收斂到最優值的某個鄰域，即

$\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon$。基本次梯度算法的性能較差，因此一般的優化問題並不推薦使用。

有約束最優化

投影次梯度算法

次梯度法的一個擴展版本是投影次梯度法，該方法用於求解有約束最優化問題

最小化$f(x)\ \quad x\in {\mathcal {C}}$

其中${\mathcal {C}}$為凸集。投影次梯度算方法的迭代公式為

$x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)$

其中$P$是在${\mathcal {C}}$上的投影，$g^{(k)}$是在點$x^{(k)}$處$f\$的次梯度。

一般約束問題

次梯度法可擴展到求解不等式約束問題

最小化$f_{0}(x)\quad f_{i}(x)\leq 0,\quad i=1,\dots ,m$

其中$f_{i}$為凸函數。該算法與無約束優化問題具有相同的形式

$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$

其中$\alpha _{k}>0$是步長，$g^{(k)}$是目標函數或約束函數在$x$處的次梯度

$g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}$

其中$\partial f$代表$f\$的次微分。如果當前點為可行點，算法採用目標函數的次梯度，否則採用任一違反約束的函數的次微分。

參考資料

• Bertsekas, Dimitri P. Nonlinear Programming. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0. 

• Shor, Naum Z. Minimization Methods for Non-differentiable Functions. Springer-Verlag. 1985. ISBN 0-387-12763-1. 

外部連結

• EE364a （頁面存檔備份，存於網際網路檔案館） and EE364b （頁面存檔備份，存於網際網路檔案館）, a Stanford course homepage