基本介紹
- 中文名:次梯度法
- 外文名:Subgradient method
- 套用:凸函式最最佳化問題
- 分類:最最佳化算法
基本次梯度算法,步長的選取,收斂結果,有約束最最佳化,投影次梯度算法,一般約束問題,
基本次梯度算法
![](/img/a/817/4ad2d5943858b0f894ec740c944b.jpg)
![](/img/9/9a5/4be1fdb1561715813534a31812fb.jpg)
![](/img/5/378/605d4e95b7d602c0edfc298d9dd9.jpg)
![](/img/a/69f/2777c06e4d8afb28a8ab14c97127.jpg)
![](/img/0/c9a/ac48b2599d4ba9e58b692cc9fbe7.jpg)
![](/img/1/759/dc510b15fb33d4982e4569d31a08.jpg)
![](/img/0/a23/8898d904ca54f729e386122d89fc.jpg)
![](/img/0/c9a/ac48b2599d4ba9e58b692cc9fbe7.jpg)
![](/img/3/3ba/c07d959ee3ba3dd5ec9f48cd5210.jpg)
![](/img/a/538/cacaaa5862534ef448e8fe845d6c.jpg)
![](/img/e/ce4/c8389d05b6f6400e955c888cd0f5.jpg)
步長的選取
次梯度方法有許多可採用的步長。以下為5種能夠保證收斂性的步長規則:
1、恆定步長,![](/img/8/fa5/320c7fb19ba9b01e2a09c3fa7452.jpg)
![](/img/8/fa5/320c7fb19ba9b01e2a09c3fa7452.jpg)
2、恆定間隔,
,得出
。
![](/img/7/2f1/7bd720d5341c98775d7bcb6e66c5.jpg)
![](/img/f/3d9/96ec7c6f0c4c3fa6180af05ee49d.jpg)
3、步長平方可加,但步長不可加,即步長滿足![](/img/6/95c/d9325239f77b3f905923b4bf4ab0.jpg)
![](/img/6/95c/d9325239f77b3f905923b4bf4ab0.jpg)
4、步長不可加但步長遞減,即步長滿足![](/img/5/b20/ddeae62ab9d69894afd01fd75a2e.jpg)
![](/img/5/b20/ddeae62ab9d69894afd01fd75a2e.jpg)
5、間隔不可加但間隔遞減,即
,其中![](/img/d/429/db7a8497fdfba3f3abf093a921c2.jpg)
![](/img/b/956/6c8531fba9e6d72f717efed86750.jpg)
![](/img/d/429/db7a8497fdfba3f3abf093a921c2.jpg)
注意:上述步長是在算法執行前所確定的,不依賴於算法運行過程中產生的任何數據。這是與標準梯度下降法的顯著區別。
收斂結果
對於恆定間隔的步長以及恆定步長,次梯度算法收斂到最優值的某個鄰域,即
![](/img/d/557/a99c59c4d740817723d3277a42ff.jpg)
有約束最最佳化
投影次梯度算法
次梯度法的一個擴展版本是投影次梯度法,該方法用於求解有約束最最佳化問題:最小化
,其中 C為凸集。投影次梯度算方法的疊代公式為:
![](/img/4/541/055097338d2aeb43cae138ec66b3.jpg)
![](/img/c/dd2/9c1204629c9ffc60eec00d917d51.jpg)
![](/img/e/1e4/c1c1de712c7b6dceaf43c0be1417.jpg)
![](/img/3/d21/4880013ea772fe8595dd084ce05e.jpg)
![](/img/1/0a7/b2de8410436b956b77eaf4a9a185.jpg)
一般約束問題
![](/img/1/f40/caa41a3a60efe53fb3486488b131.jpg)
![](/img/2/032/7621130245104c80f808f2739743.jpg)
![](/img/e/1e4/c1c1de712c7b6dceaf43c0be1417.jpg)