求解可分解強(qiáng)凸優(yōu)化問(wèn)題的FISTA-Barzilai-Borwein算法

李 星，鄧康康， 李 超

(1.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350100；2.武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300)

近年來(lái)，結(jié)構(gòu)凸優(yōu)化模型及其算法已經(jīng)成為機(jī)器學(xué)習(xí)研究的熱點(diǎn)，尤其是非光滑優(yōu)化技術(shù)。更好地利用非光滑項(xiàng)的結(jié)構(gòu)對(duì)于一個(gè)算法獲得良好的性能是至關(guān)重要的?？紤]如下形式的可分解強(qiáng)凸優(yōu)化問(wèn)題

其中E為歐氏空間。通篇假設(shè)：

（a）f：E → （-∞，∞］是強(qiáng)凸函數(shù)，dom （f）=Rn，即存在 σ>0，

且在E上梯度▽f是利普希茨連續(xù)的,即存在一個(gè)常數(shù) Lf，使得

‖ ▽ f（x）-▽ f（y）‖ ≤ Lf‖ x-y‖ ,? x，y∈ dom （f）；

（b）g：E→（-∞，∞］是閉凸（不一定可微）函數(shù)，且dom （g）? int（dom （f））；

（c）問(wèn)題（1）的最優(yōu)解集Ω*是非空的，最優(yōu)值記為Fopt。

臨近梯度算法[9]是求解各種非光滑優(yōu)化問(wèn)題的常用方法之一，具有計(jì)算成本低、收斂性強(qiáng)和步長(zhǎng)選擇廣[4,5,6]等優(yōu)勢(shì)。該算法具有如下迭代格式：

其中▽ f（xk）是 f在 xk處的梯度。

經(jīng)過(guò)簡(jiǎn)單運(yùn)算，并省略常數(shù)項(xiàng)，可將式（2）改寫(xiě)為

采用臨近點(diǎn)算子，式（3）寫(xiě)為

臨近梯度算法僅具有O（1/k）的收斂速率，這里k是迭代次數(shù)。Beck和Teboulle[2]提出了一種快速臨近梯度（簡(jiǎn)稱(chēng)FISTA）算法，并證明算法的全局收斂性和目標(biāo)函數(shù)值的的收斂速率。雖然FISTA算法[7,8]可以保證目標(biāo)函數(shù)值具有O（1/k2）的收斂速率，但在實(shí)際應(yīng)用中，由于它的局部震蕩性，實(shí)驗(yàn)效果往往并不理想。為了克服FISTA算法的缺陷，Chambolle和Dossal[3]提出了快速迭代收縮/閾值（簡(jiǎn)稱(chēng)FISTA-CD）算法，通過(guò)對(duì)參數(shù)更新規(guī)則的修正，提高了算法的實(shí)現(xiàn)效率，并證明算法仍具有的收斂速率。2017年，Beck[1]總結(jié)了大量的一階優(yōu)化方法，詳細(xì)地介紹了不同的可分解優(yōu)化問(wèn)題，給出許多有效的求解算法模型，同時(shí)證明了算法的全局收斂性和O（1/k2）的收斂速率。

算法1：FISTA-CD算法

初始化：給定 x0∈Rn,t0=1,令

執(zhí)行下列步驟：

4）令 k=k+1，返回 1）；

直到收斂．

Barzilai-Borwein算法[4]是求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題的重要方法之一，該方法在計(jì)算當(dāng)前迭代步長(zhǎng)時(shí)充分利用前一步的信息，嘗試用一個(gè)標(biāo)量矩陣γkI逼近Bk，使Bk=γkI滿(mǎn)足擬牛頓公式，達(dá)到較好逼近目標(biāo)函數(shù)在xk處的Hessian陣的效果。BB步長(zhǎng)具有如下形式

其中 sk=xk-xk-1，yk=▽ f（xk）-▽ f（xk-1）。

受文獻(xiàn)[1,3]的啟發(fā)，提出一種與BB算法相結(jié)合的快速臨近BB（簡(jiǎn)稱(chēng)FISTA-BB）算法，主要有兩個(gè)目的：一是采用BB步長(zhǎng)作為FISTA-CD算法中的步長(zhǎng)因子，使其有一個(gè)好的初始選擇；二是選擇合適的更新準(zhǔn)則，加快算法的收斂速度。

全文結(jié)構(gòu)如下：第1節(jié)描述了求解可分解強(qiáng)凸優(yōu)化問(wèn)題的FISTA-BB算法，并證明該算法具有全局收斂性和0（1/k2）的收斂速率；第2節(jié)通過(guò)與當(dāng)前高效算法進(jìn)行詳細(xì)的收斂性能數(shù)據(jù)比對(duì)，從而驗(yàn)證本文所構(gòu)造的算法的有效性；最后，第3節(jié)對(duì)全文進(jìn)行總結(jié)。

1 算法描述及收斂性分析

首先定義臨近梯度算子

針對(duì)問(wèn)題（1），我們提出一種FISTA-BB算法，具體框架如下：

算法2：FISTA-BB算法

S0)初始化:給定 x0∈Rn，令 y0=x0，kmax>0，ε>0，t0=1，L0>0，ρ∈［0,1］，0＜q＜（2-p）2，μ>1，令 k=0；

S1)計(jì)算 xk+1，即

令Lk+1=μkak+1，這里的ik是滿(mǎn)足下述條件的最小非負(fù)整數(shù)，即

S4)當(dāng)k>kmax或‖ yk+1-yk‖ ＜ε 時(shí)，停止迭代；否則令k=k+1，返回 S1）．

為了證明算法的收斂性，先給出如下3個(gè)引理:

引理 1：假設(shè) f和 g 滿(mǎn)足（a）和（b）,對(duì)于任意的x∈ E，y∈ int（dom （f）），且 L>0 時(shí)，滿(mǎn)足

證明：見(jiàn)文獻(xiàn)[1]中第281頁(yè)的定理10．16。

引理 2：假設(shè)f是強(qiáng)凸函數(shù)，且滿(mǎn)足

則對(duì)于任意的k≥0，是Lk有界的，即

其中 σ>0，μ>1。

證明：由于f是強(qiáng)凸函數(shù)，且Lk≥ak>0，則有

從而得到Lk≥σ.

為了證明Lk≤μLf，根據(jù)假設(shè)中函數(shù)f的光滑性，得到

用反證法，假設(shè)Lk>μLf,等價(jià)于μikak>μLf,于是有μik-1ak>Lf，根據(jù)假設(shè)中函數(shù)f的光滑性有

對(duì)式（20），根據(jù) y0=x0,得到

2 數(shù)值實(shí)驗(yàn)

為了說(shuō)明算法的有效性，下面對(duì)本文所提出的FISTA-BB算法進(jìn)行初步的數(shù)值實(shí)驗(yàn)。測(cè)試問(wèn)題均選自文獻(xiàn)[1]，算法的程序采用Matlab R2016a編制，且所有實(shí)驗(yàn)在筆記本為 CPU 1．90GHz，RAM 6．00GB 上運(yùn)行實(shí)現(xiàn)。

算例 3．1[1]:求解如下問(wèn)題

設(shè)計(jì)如下實(shí)驗(yàn)參數(shù)：

終止條件：‖ yk+1-yk‖＜ε；

參數(shù)設(shè)定：ε=1．0e-6，t0=1，L0=2，μ=2，kmax=104，在FISTA-CD算法中取d=2，在FISTA-BB算法中取p=0，q=4；

實(shí)驗(yàn)數(shù)據(jù)：算例 3．1 中，令 λ=0．002，初始點(diǎn)為 x=ones（n,1），x=（1:n/4）=0，b=A*x；算例 3．2 中，初始點(diǎn)為x=zeros（n,1），B=rand（n，n），b=rand（n，1），這里兩個(gè)算例均取A為對(duì)稱(chēng)正定矩陣，定義如下

通過(guò)使用MATLAB編程運(yùn)算得到下面的測(cè)試結(jié)果，表1和表2均列出了在不同的維數(shù)下，分別對(duì)算例3．1和算例3．2進(jìn)行求解，統(tǒng)計(jì)FISTA-CD算法和FISTA-BB算法的迭代次數(shù)（iter）和運(yùn)算時(shí)間（cput以秒為單位）的結(jié)果。

表1 算例3.1的數(shù)值結(jié)果Table 1 Numerical results of example 3．1

表2 算例3.2的數(shù)值結(jié)果Table 2 Numerical results of example 3．2

根據(jù)上述的數(shù)值實(shí)驗(yàn)結(jié)果可以看出：FISTA-BB算法能夠有效求解本文所考慮的相關(guān)問(wèn)題，同時(shí)在不同維數(shù)的情況下，該算法的迭代次數(shù)和運(yùn)算時(shí)間明顯優(yōu)于FISTA-CD算法。

3 結(jié)論

本文提出了求解可分解強(qiáng)凸優(yōu)化問(wèn)題 （1）的FISTA-BB算法，與文獻(xiàn)[3]給出的FISTA-CD算法相比，F(xiàn)ISTA-BB算法從很大程度上減少了迭代次數(shù)和降低了運(yùn)算時(shí)間．本文證明了FISTA-BB算法具有0（1/k2）的收斂速率，初步數(shù)值實(shí)驗(yàn)表明了算法的可行性和有效性。