跳至內容

次梯度法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

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

基本次梯度演算法

為定義在上的凸函數。次梯度演算法使用以下的迭代格式

其中表示函數次梯度. 如果 可微,他的次梯度就是梯度向量 ,有時不是函數處的下降方向。因此採用一系列可能的來追蹤目標函數的極小值點,即

步長的選取

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

  • 恆定步長,
  • 恆定間隔,,得出
  • 步長平方可加,但步長不可加,即步長滿足
  • 步長不可加但步長遞減,即步長滿足
  • 間隔不可加但間隔遞減,即,其中
。注意:上述步長是在演算法執行前所確定的,不依賴於演算法執行過程中產生的任何數據。這是與標準梯度下降法的顯著區別。

收斂結果

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

。基本次梯度演算法的效能較差,因此一般的最佳化問題並不推薦使用。

有約束最佳化

投影次梯度演算法

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

最小化

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

其中是在上的投影,是在點的次梯度。

一般約束問題

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

最小化

其中為凸函數。該演算法與無約束最佳化問題具有相同的形式

其中是步長,是目標函數或約束函數在處的次梯度

其中代表的次微分。如果當前點為可行點,演算法採用目標函數的次梯度,否則採用任一違反約束的函數的次微分。

參考資料

外部連結