非凸優(yōu)化中對(duì)于帶不同慣性項(xiàng)的前后分裂算法的一種加速技術(shù)

劉海玉

摘? 要：本文考慮最小化一類(lèi)非凸非光滑優(yōu)化問(wèn)題，對(duì)帶不同慣性項(xiàng)的前后分裂算法中的步長(zhǎng)作了改進(jìn)，運(yùn)用非單調(diào)線搜索技術(shù)來(lái)加快收斂速度。新算法利用了非單調(diào)線搜索技術(shù)，在每一次迭代中滿足預(yù)先設(shè)置條件，從而在總體上使目標(biāo)函數(shù)值有更大的下降。通過(guò)假設(shè)算法產(chǎn)生序列的有界性，本文利用數(shù)學(xué)歸納法完成了算法的序列收斂性證明。最后對(duì)非凸二次規(guī)劃問(wèn)題進(jìn)行了數(shù)值實(shí)驗(yàn)，通過(guò)合適的參數(shù)選取，說(shuō)明新算法有效地減少了迭代次數(shù)，達(dá)到預(yù)先給定的終止條件。

關(guān)鍵詞：非凸優(yōu)化? 非單調(diào)線搜索技術(shù)? 帶不同慣性項(xiàng)的前后分裂算法? 收斂速度

中圖分類(lèi)號(hào)：O224 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ?文章編號(hào)：1674-098X（2021）03（a）-0184-04

An Acceleration Technique of the Forward-backward Splitting Algorithm with Different Inertial Terms for Non-convex Optimization

LIU Haiyu*

（Hebei University Of Technology， School of Science，Tianjin， 300401 China）

Abstract： In this paper， we consider minimizing a class of non-convex and non-smooth optimization problems， improve the step size of the forward-backward algorithm with different inertia terms， and use the nonmonotone proximal gradient technology to speed up the convergence. The new algorithm uses the nonmonotone proximal gradient technology to select the maximum value of adjacent objective functions in the iteration， so that the value of the function drops more. We prove the convergence of the new algorithm under strong hypothetical conditions. Finally， the numerical experiment is carried out on the non-convex quadratic programming problem， which proves that the new algorithm effectively improves the convergence speed of the original algorithm.

Key Words： Non-convex optimization; Nonmonotone proximal gradient method; Forward-backward algorithm with different inertial terms; Convergence speed

1? 問(wèn)題背景介紹

本文求解一類(lèi)一階優(yōu)化問(wèn)題：

（1）

其中目標(biāo)函數(shù)給出限定條件：，且：

1）函數(shù)f（x）是連續(xù)可微函數(shù)（可能非凸）且梯度李普希茲連續(xù)，即存在常數(shù)Lf>0，對(duì)任意的滿足：

2）函數(shù)g（x）是正常、閉凸函數(shù)（可能非光滑），在其有效域內(nèi)有下界。

3）函數(shù)F（x）有下界。

上述優(yōu)化問(wèn)題模型常見(jiàn)于圖像處理，信號(hào)恢復(fù)方面，解決此模型的一類(lèi)有效算法是鄰近梯度算法[1-2]。其中，2016年，Liang J和 Fadili J通過(guò)在鄰近梯度法加多步外推項(xiàng)，通過(guò)一定的手段來(lái)設(shè)置參數(shù)，提出了新的多步的慣性鄰近梯度法[3]。

László S C在2020年提出了求解非凸問(wèn)題模型（1）的算法，即帶不同慣性項(xiàng)的前后分裂算法（cPADISNO）[4]：

（2）

其中，s為步長(zhǎng)，取分別是不同的慣性因子且為趨于固定值的數(shù)列，以滿足到更好加速效果，關(guān)于此類(lèi)算法收斂速率的分析框架和應(yīng)用已經(jīng)被有關(guān)文獻(xiàn)[5-7]分析。

另一方面，線搜索技術(shù)是另一項(xiàng)加快算法收斂速度的有效方法，非單調(diào)的線搜索更能有效地減少迭代次數(shù)和加快收斂速度，文獻(xiàn)[8]提出了一種非單調(diào)的線搜索技術(shù)，采用以下迭代格式：

（3）

其中，L是梯度f(wàn)函數(shù)的李普希茲常數(shù)，c和M是大于0的常數(shù)。該方法在每一步迭代下選取鄰近迭代目標(biāo)函數(shù)值的最大值，直至滿足線搜索條件，從而保證了每一次的函數(shù)值有更大的下降。

在以上研究的推動(dòng)下，并受非單調(diào)線搜索的啟發(fā)，本文將兩者結(jié)合提出一種帶非單帶線搜索技術(shù)且?guī)Р煌瑧T性項(xiàng)的前后分裂算法。

2? 帶非單調(diào)線搜索技術(shù)的不同慣性項(xiàng)的前后分裂算法和收斂性

2.1 帶非單調(diào)線搜索技術(shù)的不同慣性項(xiàng)的前后分裂算法

在這一節(jié)，我們提出帶非單調(diào)線搜索技術(shù)的不同慣性項(xiàng)的前后分裂算法，稱為 cPADISNO-nml算法。

cPADISNO-nml算法：

選擇初始值，c>0，，其中，

令

選擇，

1a）求解子問(wèn)題：

（4）

1b）如果

滿足條件，則繼續(xù)2）。

1c） 令然后繼續(xù)步驟1a）。

2） 令，然后繼續(xù)求解步驟1）。

2.2 算法收斂性

接下來(lái)，我們給出相關(guān)算法的證明，證明采用文獻(xiàn)[9]的框架：

定理1：

1）假設(shè)產(chǎn)生的序列有界，則算法滿足，且存在有。

2） 任意算法產(chǎn)生子序列的聚點(diǎn)都是問(wèn)題的穩(wěn)定點(diǎn)。

證明：

我們定義

要證明目標(biāo)函數(shù)的收斂性，需要說(shuō)明是單調(diào)遞減的。對(duì)于，我們有

由于函數(shù)F（x）有下界，則存在有

在（2.2）式中用k來(lái)代替，那我們有

重新排列并令我們有

另一方面，我們有

其中，等式的第二行可由序列的有界性得到。我們接下來(lái)歸納證明下列極限對(duì)于j≥1是成立的：

證明說(shuō)明了j-1成立，假設(shè)證明對(duì)于j是成立的，當(dāng)上指標(biāo)集是j+1時(shí)，對(duì)于（2.2），我們將k代替為（我們假設(shè)足夠大保證非負(fù)），從而我們有

通過(guò)重新排列表達(dá)式，我們可知

通過(guò)令和歸納證明中的收斂性，由此可知從而我們有

其中，第二個(gè)等式由序列的有界性可以得到接下來(lái)說(shuō)明，對(duì)于，必然存在中的指標(biāo)使其相等。因此，存在j>0，我們有，從而我們有，易知

證畢。最后由函數(shù)F（x）的連續(xù)性可知

不妨假設(shè)x*是子序列的聚點(diǎn)，且由一階最優(yōu)性條件，我們可知

另外，由于，我們可知

由1） 可知，函數(shù)g（x）的凸性和的連續(xù)性，我們可知

從而證明了聚點(diǎn)是穩(wěn)定點(diǎn)，證畢。

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

本節(jié)我們測(cè)試了新算法的數(shù)值實(shí)驗(yàn)，運(yùn)行環(huán)境為MATLAB R2014a with 2.80GHz CPUs。

考慮下列優(yōu)化問(wèn)題：

其中，是一個(gè)對(duì)稱矩陣，e為單位向量，且p是一個(gè)正數(shù).我們將它寫(xiě)成以下形式：

其中，顯然，函數(shù)f（x）是梯度李普希茲連續(xù)的，且函數(shù)F（x）有下界，這滿足本文研究的問(wèn)題模型。

為了說(shuō)明新算法的有效性，我們與鄰近梯度法和帶不同慣性項(xiàng)的前后分裂算法做效果對(duì)比。在數(shù)值實(shí)驗(yàn)中，令初始是零向量。在鄰近梯度法（也就是cPADISNO算法中恒為0的情況，可參考文獻(xiàn)[1，2]）中，我們?nèi)〔介L(zhǎng)為在cPADISNO算法中，我們?nèi)?shù)，則當(dāng)k趨于無(wú)窮時(shí)，我們有，從而將步長(zhǎng)選取為s=.在新算法中，我們?nèi)=2，，步長(zhǎng)系數(shù)，則，并選取步長(zhǎng)SK=，當(dāng)k≥1我們將李普希茲常數(shù)取為Barzilai-Borwen步：

為了讓數(shù)值實(shí)驗(yàn)問(wèn)題變成非凸優(yōu)化問(wèn)題，我們先隨機(jī)取N維矩陣D，再取，從而矩陣A是對(duì)稱矩陣。取向量b為N維[0，1]的隨機(jī)數(shù)向量，p取，其中t取[0，1]中的隨機(jī)數(shù)，并選取迭代終止條件為

令D的維數(shù)分別取，最后借助MATLAB分別畫(huà)出的圖像：

圖1說(shuō)明了N=500下的對(duì)比，可知cPADISNO在數(shù)值上比PG 收斂速度快，cPADISNO-nml在數(shù)值表現(xiàn)上能更快達(dá)到預(yù)先給定的終止條件。

圖2說(shuō)明了N=1000下的對(duì)比，cPADISNO-nml算法可以更快地接近終止條件。

這幾幅圖片中，PG代表的是鄰近梯度法，cPADISNO代表的是帶不同慣性項(xiàng)的前后分裂算法，cPADISNO-nml是我們提出的新算法。下面表格給出我們分別運(yùn)行3種方法5次取平均值的結(jié)果，見(jiàn)表1。

4? 結(jié)語(yǔ)

本文為極小化非凸非光滑函數(shù)的帶不同慣性項(xiàng)的前后分裂算法提出了一種加速技術(shù)，我們將非單調(diào)線搜索運(yùn)用到算法中來(lái)加快原算法的收斂速度。通過(guò)假設(shè)序列的有界性，我們證明了算法的序列收斂性。非凸的數(shù)值實(shí)驗(yàn)表明，新算法有效地減少了迭代次數(shù)。以后的工作我們將著重研究新算法的收斂速率。

參考文獻(xiàn)

[1] TANABE H， FUKUDA E H， YAMASHITA N. Proximal gradient methods for multiobjective optimization and their applications[J].Computational Optimization and Applications，2019，72（2）： 339-361.

[2] Bo R I，CSETNEK E R. A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function[J]. ESAIM： Control， Optimisation and Calculus of Variations， 2018， 24（2）： 463-477.

[3] LIANG J， FADILI J， PEYRé G. A Multi-step Inertial Forward-Backward Splitting Method for Non-convex Optimization[J].Advances in Neural Information Processing Systems， 2016， 29：4035-4043.

[4] László S C. A forward-backward algorithm with different inertial terms for the minimization of the sum of two non-convex functions[J]. arXiv preprint arXiv：2002.07154， 2020.

[5] ATTOUCH H， CABOT A. Convergence of a relaxed inertial forward–backward algorithm for structured monotone inclusions[J]. Applied Mathematics & Optimization， 2019， 80（3）： 547-598.

[6] LI G， PONG T K. Calculus of the exponent of Kurdyka–ojasiewicz inequality and its applications to linear convergence of first-order methods[J]. Foundations of computational mathematics， 2018， 18（5）： 1199-1232.

[7] DONG Q， JIANG D， CHOLAMJIAK P， et al. A strong convergence result involving an inertial forward–backward algorithm for monotone inclusions[J]. Journal of Fixed Point Theory and Applications， 2017， 19（4）： 3097-3118.

[8] CHEN X， LU Z， PONG T K. Penalty methods for a class of non-Lipschitz optimization problems[J].SIAM Journal on Optimization，2016，26（3）：1465-1492.

[9] WRIGHT S J， NOWAK R D， FIGUEIREDO M A T. Sparse reconstruction by separable approximation[J]. IEEE Transactions on signal processing， 2009， 57（7）： 2479-2493.