论文部分内容阅读
摘 要：本文考虑最小化一类非凸非光滑优化问题，对带不同惯性项的前后分裂算法中的步长作了改进，运用非单调线搜索技术来加快收敛速度。新算法利用了非单调线搜索技术，在每一次迭代中满足预先设置条件，从而在总体上使目标函数值有更大的下降。通过假设算法产生序列的有界性，本文利用数学归纳法完成了算法的序列收敛性证明。最后对非凸二次规划问题进行了数值实验，通过合适的参数选取，说明新算法有效地减少了迭代次数，达到预先给定的终止条件。
关键词：非凸优化 非单调线搜索技术 带不同惯性项的前后分裂算法 收敛速度
中图分类号：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.
关键词：非凸优化 非单调线搜索技术 带不同惯性项的前后分裂算法 收敛速度
中图分类号：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.