一種求解結構組合優化問題的BB型算法

李凱 林彭壯漢 胡子健 程萬友

(東莞理工學院 計算機科學與技術學院,廣東東莞 523808)

考慮以下無約束優化問題:

(1)

(2)

(3)

近年來壓縮感知和稀疏優化不斷發展,為了求解問題(3)式,人們提出了不同的求解方法,其中常見迭代閾值算法ISTA[4]算法,因其內存需求低、迭代簡單的特點,常用于求解大規模問題。為了加速ISTA[4]算法的收斂速度,Beck和Teboulle[5]提出了快速迭代收縮閾值算法(FISTA)。Wright[6]等人提出了可分離近似的稀疏重構算法(SpaRSA),該方法使用帶保障的BB步長和非單調線搜索,算法的數值結果很好,適用于實際問題。此外求解問題(2)和(3)的算法還有乘子交替方向法SALSA[7]、內點法[8]、梯度投影法[9]、近端梯度方法[2]等。

本文第1節將提出一種求解問題(3)的BB型算法,并分析算法的收斂性。在第2節,通過數值實驗與一些現有的算法進行比較,證明了所提出算法的有效性。

1 算法描述

在本文中,使用Huang[10]等人提出新的BB步長來求解稀疏優化問題。在一些假設下,證明了所提出算法的全局收斂性。算法的迭代格式如下:

xk+1=xk+βkdk,

其中dk是搜索方向,βk∈(0,1]是步長參數。由于目標函數φ(x)是非光滑的,因此搜索方向不能使用負梯度方向,根據函數φ(x)的近似函數的極小值點來確定如下搜索方向:

dk=Pro(xk)-xk,

(4)

其中Pro(xk)是以下問題的極小值點:

其中(αk)-1I是函數f(x)的Hessian矩陣?2f(xk)的近似,uk=xk-αk?f(xk)。顯然,函數Q(z,xk)可以看成是函數φ(x)在xk處的二次近似。由于函數Q(z,xk)是強凸函數,因此問題(5)式有唯一最小值點:

αk的選取會直接影響算法的效率,BB型算法以其快速收斂和較低的計算復雜度而受到廣泛關注,Barzilai和Borwein[11]提出了以下長和短的步長選擇: