無約束優化的非單調三次正則BB算法

楚王莉,劉紅衛,劉澤顯

(1.西安電子科技大學 數學與統計學院,西安 710126；2.中國科學院 數學與系統科學研究院,北京 100190)

0 引 言

目前,求解無約束優化問題的方法主要分為兩類: 線搜索法和信賴域法.線搜索法主要有牛頓法、擬牛頓法、梯度法、共軛梯度法,其中梯度算法以其計算簡單、易于存儲的特點更適應現代大數據計算的要求.

考慮一般無約束優化問題：

(1)

其中:f:n→是目標函數;x是決策變量.最簡單的梯度算法是最速下降法[1],其步長也被稱為Cauchy步長或者最優步長、精確步長,算法在迭代點接近極小點時,易產生鋸齒現象.Barzilai-Borwein算法(簡稱BB算法)[2]以其良好的數值性能得到廣泛關注,目前已成為求解大規模優化問題的重要方法之一.BB算法中的兩個BB步長分別為

其中:sk-1=xk-xk-1;yk-1=gk-gk-1.本文中fk=f(xk),gk=g(xk),g(xk)=f(xk),‖·‖表示Euclid范數.對于嚴格凸二次函數,BB算法具有全局收斂性和R-線性收斂性[3-4],其計算效果遠超過最速下降法.但對于一般的目標函數,BB步長可能為負,不能保證目標值單調下降.Raydan[5]通過結合Grippo等[6]提出的非單調線搜索,設計了一種高效的用于求解無約束優化問題的全局BB算法.對于大多數問題,非單調BB算法的表現均較好.之后,許多學者從不同的角度推導出了不同類型的修正BB步長[7-8],數值實驗表明,修正的BB類型步長數值效果較好,但對于最優的BB步長目前尚未達成共識.Liu等[9]從近似模型的角度解釋了BB步長,引入了一類新的步長----近似最優步長,提出了一種高效的求解大規模無約束優化問題的近似最優梯……