次梯度法是求解凸函數最優化(凸優化)問題的一種迭代法。次梯度法能夠用於不可微的目標函數。當目標函數可微時,對於無約束問題次梯度法與梯度下降法具有同樣的搜索方向。
雖然在實際的應用中,次梯度法比內點法和牛頓法慢得多,但是次梯度法可以直接應用於更廣泛的問題,次梯度法只需要很少的存儲需求。然而,通過將次梯度法與分解技術結合,有時能夠開發出問題的簡單分配算法。
基本次梯度算法[編輯]
記
為定義在
上的凸函數。次梯度算法使用以下的迭代格式
![{\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)
其中
代表
的次微分。如果當前點為可行點,算法採用目標函數的次梯度,否則採用任一違反約束的函數的次微分。
參考資料[編輯]
外部連結[編輯]