次梯度法是求解凸函數(shù)最優(yōu)化（凸優(yōu)化）問題的一種迭代法。次梯度法能夠用于不可微的目標(biāo)函數(shù)。當(dāng)目標(biāo)函數(shù)可微時(shí)，對(duì)于無(wú)約束問題次梯度法與梯度下降法具有同樣的搜索方向。雖然在實(shí)際的應(yīng)用中，次梯度法比內(nèi)點(diǎn)法和牛頓法慢得多，但是次梯度法可以直接應(yīng)用于更廣泛的問題，次梯度法只需要很少的存儲(chǔ)需求。然而，通過將次梯度法與分解技術(shù)結(jié)合，有時(shí)能夠開發(fā)出問題的簡(jiǎn)單分配算法。

基本次梯度算法

記

為定義在

上的凸函數(shù)。次梯度算法使用以下的迭代格式：

其中

表示函數(shù) f在

的次梯度. 如果 f可微，他的次梯度就是梯度向量

有時(shí)，

不是函數(shù) f在

處的下降方向。因此采用一系列可能的

來(lái)追蹤目標(biāo)函數(shù)的極小值點(diǎn)，即

步長(zhǎng)的選取

次梯度方法有許多可采用的步長(zhǎng)。以下為5種能夠保證收斂性的步長(zhǎng)規(guī)則：

1、恒定步長(zhǎng)，

2、恒定間隔，

，得出

。

3、步長(zhǎng)平方可加，但步長(zhǎng)不可加，即步長(zhǎng)滿足

4、步長(zhǎng)不可加但步長(zhǎng)遞減，即步長(zhǎng)滿足

5、間隔不可加但間隔遞減，即

，其中

注意：上述步長(zhǎng)是在算法執(zhí)行前所確定的，不依賴于算法運(yùn)行過程中產(chǎn)生的任何數(shù)據(jù)。這是與標(biāo)準(zhǔn)梯度下降法的顯著區(qū)別。

收斂結(jié)果

對(duì)于恒定間隔的步長(zhǎng)以及恒定步長(zhǎng)，次梯度算法收斂到最優(yōu)值的某個(gè)鄰域，即

基本次梯度算法的性能較差，因此一般的優(yōu)化問題并不推薦使用。

有約束最優(yōu)化

投影次梯度算法

次梯度法的一個(gè)擴(kuò)展版本是投影次梯度法，該方法用于求解有約束最優(yōu)化問題：最小化

,其中 C為凸集。投影次梯度算方法的迭代公式為:

其中P是在C的投影，

是在點(diǎn)

處 的次梯度。一般約束問題

次梯度法可擴(kuò)展到求解求解不等式約束問題，最小化

，其中 為凸函數(shù)。該算法與無(wú)約束優(yōu)化問題具有相同的形式：

其中，

是步長(zhǎng)，

是目標(biāo)函數(shù)或約束函數(shù)在 x處的次梯度

其中

是f的次微分。如果當(dāng)前點(diǎn)為可行點(diǎn)，算法采用目標(biāo)函數(shù)的次梯度，否則采用任一違反約束的函數(shù)的次微分。