非凸優化中對于帶不同慣性項的前后分裂算法的一種加速技術

劉海玉

摘? 要：本文考慮最小化一類非凸非光滑優化問題，對帶不同慣性項的前后分裂算法中的步長作了改進，運用非單調線搜索技術來加快收斂速度。新算法利用了非單調線搜索技術，在每一次迭代中滿足預先設置條件，從而在總體上使目標函數值有更大的下降。通過假設算法產生序列的有界性，本文利用數學歸納法完成了算法的序列收斂性證明。最后對非凸二次規劃問題進行了數值實驗，通過合適的參數選取，說明新算法有效地減少了迭代次數，達到預先給定的終止條件。

關鍵詞：非凸優化? 非單調線搜索技術? 帶不同慣性項的前后分裂算法? 收斂速度

中圖分類號：O224 ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ?文章編號：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? 問題背景介紹

本文求解一類一階優化問題：

（1）

其中目標函數給出限定條件：，且：

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

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

3）函數F（x）有下界。

上述優化問題模型常見于圖像處理，信號恢復方面，解決此模型的一類有效算法是鄰近梯度算法[1-2]。其中，2016年，Liang J和 Fadili J通過在鄰近梯度法加多步外推項，通過一定的手段來設置參數，提出了新的多步的慣性鄰近梯度法[3]。

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

（2）

其中，s為步長，取分別是不同的慣性因子且為趨于固定值的數列，以滿足到更好加速效果，關于此類算法收斂速率的分析框架和應用已經被有關文獻[5-7]分析。

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

（3）

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

在以上研究的推動下，并受非單調線搜索的啟發，本文將兩者結合提出一種帶非單帶線搜索技術且帶不同慣性項的前后分裂算法。

2? 帶非單調線搜索技術的不同慣性項的前后分裂算法和收斂性

2.1 帶非單調線搜索技術的不同慣性項的前后分裂算法

在這一節，我們提出帶非單調線搜索技術的不同慣性項的前后分裂算法，稱為 cPADISNO-nml算法。

cPADISNO-nml算法：

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

令

選擇，

1a）求解子問題：

（4）

1b）如果

滿足條件，則繼續2）。

1c） 令然后繼續步驟1a）。

2） 令，然后繼續求解步驟1）。

2.2 算法收斂性

接下來，我們給出相關算法的證明，證明采用文獻[9]的框架：

定理1：

1）假設產生的序列有界，則算法滿足，且存在有。

2） 任意算法產生子序列的聚點都是問題的穩定點。

證明：

我們定義

要證明目標函數的收斂性，需要說明是單調遞減的。對于，我們有

由于函數F（x）有下界，則存在有

在（2.2）式中用k來代替，那我們有

重新排列并令我們有

另一方面，我們有

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

證明說明了j-1成立，假設證明對于j是成立的，當上指標集是j+1時，對于（2.2），我們將k代替為（我們假設足夠大保證非負），從而我們有

通過重新排列表達式，我們可知

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

其中，第二個等式由序列的有界性可以得到接下來說明，對于，必然存在中的指標使其相等。因此，存在j>0，我們有，從而我們有，易知

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

不妨假設x*是子序列的聚點，且由一階最優性條件，我們可知

另外，由于，我們可知

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

從而證明了聚點是穩定點，證畢。

3? 數值實驗

本節我們測試了新算法的數值實驗，運行環境為MATLAB R2014a with 2.80GHz CPUs。

考慮下列優化問題：

其中，是一個對稱矩陣，e為單位向量，且p是一個正數.我們將它寫成以下形式：

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

為了說明新算法的有效性，我們與鄰近梯度法和帶不同慣性項的前后分裂算法做效果對比。在數值實驗中，令初始是零向量。在鄰近梯度法（也就是cPADISNO算法中恒為0的情況，可參考文獻[1，2]）中，我們取步長為在cPADISNO算法中，我們取參數，則當k趨于無窮時，我們有，從而將步長選取為s=.在新算法中，我們取M=2，，步長系數，則，并選取步長SK=，當k≥1我們將李普希茲常數取為Barzilai-Borwen步：

為了讓數值實驗問題變成非凸優化問題，我們先隨機取N維矩陣D，再取，從而矩陣A是對稱矩陣。取向量b為N維[0，1]的隨機數向量，p取，其中t取[0，1]中的隨機數，并選取迭代終止條件為

令D的維數分別取，最后借助MATLAB分別畫出的圖像：

圖1說明了N=500下的對比，可知cPADISNO在數值上比PG 收斂速度快，cPADISNO-nml在數值表現上能更快達到預先給定的終止條件。

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

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

4? 結語

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

參考文獻

[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.