次梯度法是求解凸函數最佳化(凸最佳化)問題的一種迭代法。次梯度法能夠用於不可微的目標函數。當目標函數可微時,對於無約束問題次梯度法與梯度下降法具有同樣的搜尋方向。
雖然在實際的應用中,次梯度法比內點法和牛頓法慢得多,但是次梯度法可以直接應用於更廣泛的問題,次梯度法只需要很少的儲存需求。然而,通過將次梯度法與分解技術結合,有時能夠開發出問題的簡單分配演算法。
記
為定義在
上的凸函數。次梯度演算法使用以下的迭代格式
![{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/74b27669f0798ab15d71cd3a4a002fed80577801)
其中
表示函數
在
的次梯度. 如果
可微,他的次梯度就是梯度向量
,有時
不是函數
在
處的下降方向。因此採用一系列可能的
來追蹤目標函數的極小值點,即
。
次梯度方法有許多可採用的步長。以下為5種能夠保證收斂性的步長規則
- 恆定步長,
。
- 恆定間隔,
,得出
。
- 步長平方可加,但步長不可加,即步長滿足
。
。
- 間隔不可加但間隔遞減,即
,其中
。注意:上述步長是在演算法執行前所確定的,不依賴於演算法執行過程中產生的任何數據。這是與標準梯度下降法的顯著區別。
對於恆定間隔的步長以及恆定步長,次梯度演算法收斂到最佳值的某個鄰域,即
。基本次梯度演算法的效能較差,因此一般的最佳化問題並不推薦使用。
次梯度法的一個擴充版本是投影次梯度法,該方法用於求解有約束最佳化問題
- 最小化
![{\displaystyle f(x)\ \quad x\in {\mathcal {C}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87eea9469091b60e59c4c3e6c0fbb2ec022a76f1)
其中
為凸集。投影次梯度算方法的迭代公式為
![{\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/243d11f56cb22ca2899e56c85a507a75a33e3777)
其中
是在
上的投影,
是在點
處
的次梯度。
次梯度法可延伸到求解不等式約束問題
- 最小化
![{\displaystyle f_{0}(x)\quad f_{i}(x)\leq 0,\quad i=1,\dots ,m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f945c598ee5f576843dbab82efbcc665cd2e33)
其中
為凸函數。該演算法與無約束最佳化問題具有相同的形式
![{\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/74b27669f0798ab15d71cd3a4a002fed80577801)
其中
是步長,
是目標函數或約束函數在
處的次梯度
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7717279e41b04388383e1cadddbf0c7aa13af9e)
其中
代表
的次微分。如果當前點為可行點,演算法採用目標函數的次梯度,否則採用任一違反約束的函數的次微分。