次梯度法

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

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

基本次梯度演算法

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

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

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

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

步長的選取

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

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

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

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

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

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

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

收斂結果

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

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

有約束最佳化

投影次梯度演算法

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

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

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

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

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

一般約束問題

次梯度法可延伸到求解不等式約束問題

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

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

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

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

${\displaystyle 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}}}$

其中${\displaystyle \partial f}$代表${\displaystyle 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