Advances in Applied Mathematics
Vol.
10
No.
03
(
2021
), Article ID:
41234
,
8
pages
10.12677/AAM.2021.103080
非凸优化中一种带非单调线搜索的 惯性邻近算法
刘海玉
河北工业大学,理学院,天津
收稿日期:2021年2月23日;录用日期:2021年3月19日;发布日期:2021年3月26日
摘要
本文考虑一类目标函数由可微(可能非凸)函数和凸(可能非光滑)函数组成的极小化问题。惯性邻近(iPiano)算法是解决这类问题的一种有效而重要的方法。通过引入非单调线搜索,提出了非单调线搜索的iPiano (iPiano-nml)算法。通过证明说明了由iPiano-nml生成的序列的任何聚点都是一个稳定点。最后,对图像处理问题进行了数值实验来说明新算法的理论结果。
关键词
非单调邻近梯度法,非凸,非光滑,图像降噪
An Inertial Proximal Algorithm with Non-Monotone Line Search for Non-Convex Optimization
Haiyu Liu
School of Science, Hebei University of Technology, Tianjin
Received: Feb. 23rd, 2021; accepted: Mar. 19th, 2021; published: Mar. 26th, 2021
ABSTRACT
We consider a class of minimization problems whose objective function is composed of a differentiable (possibly nonconvex) function and a convex (possibly nonsoomth) function. The inertial proximal algorithm is a common and important method for this kind of problems. By incorporating the non-monotone line search, iPiano algorithm with non-monotone line search is proposed. We show that any cluster point of sequence which is generated by iPiano-nml is a stationary point. Finally, we perform numerical experiments on the image processing problems to illustrate our theoretical results.
Keywords:Non-Monotone Proximal Gradient Method, Nonconvex, Non-Smooth, Image Denoising
Copyright © 2021 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本文考虑下列最小化问题:
(1)
其中, 是一个光滑(可能非凸)且为梯度李普希兹连续函数, 是一个正常下半连续凸(可能非光滑)函数。另外 是一个强制函数且有下界。
问题(1)出现在很多领域,如机器学习 [1],信号处理 [2] 等。解决上述问题的经典方法是邻近梯度法 [3]:
其中 是步长。然而,邻近梯度算法在解决一些问题时,它的收敛速度较慢,于是人们逐渐地寻找一些策略来改善这样的问题。常见的一个有效的策略是加速方法,因此在上述邻近梯度法中,通过引入外推项,一些文献提出了加速邻近梯度算法 [4],FISTA [5] 算法等。加速邻近梯度算法如下:
其中 是步长, 是外推参数。这些算法的收敛速度为 。除此自外,惯性项也是一类能加速算法的有效策略,通过将邻近梯度法和惯性项结合得到下列惯性邻近算法(iPiano) [6] ]:
(2)
其中, 是步长, 是惯性因子。iPiano在实际运行中收敛速度比邻近梯度法快,广泛地应用于非凸问题 [7] [8]。另一方面,线搜索也是一项能加速原始算法的有效策略,其非单调线搜索有更好的数值表现。非单调邻近梯度法(NPG) [9] 采用了下列线搜索:
其中c和M都大于0。该线搜索在每次迭代中通过选取k与 之间的最大值来满足条件,从而保证目标函数有更大的下降。
本文在惯性邻近算法的基础上,将其与NPG结合,提出一种带非单调线搜索的惯性邻近算法,并将其运用于图像处理,通过信噪比来说明新算法的有效性。
2. 预备定义
本节给出一些基本的定义。本文考虑欧式空间且维数 。
定义1:令 为一个正常下半连续凸函数,那么邻近算子定义为:
引理1: 为一个光滑函数且为L梯度李普希兹连续。则对于 ,,下式成立:
引理2: 为一个光滑函数且为L梯度李普希兹连续。则对于 ,我们成立以下下降引理
命题1:令 满足上述定义,则对于 ,我们有下式成立:
3. 算法和收敛性
本节给出iPiano-nml算法和收敛性分析。首先我们引入一个辅助序列:
易知当时 ,我们有 。
3.1. iPiano-nml算法
iPiano-nml算法:
步骤0:选择 。 接近0。 。
步骤k:1) 选择 。
1a) 求解子问题:
1b) 如果满足
那么进行步骤2)。
1c) 令 ,继续步骤1a)。
2) 令 然后进行步骤1)。
其中序列满足 。 单调递减,另有:
3.2. 收敛性分析
引理1:对于 ,存在 。另外给定 ,存在 满足 单调递减。
证明:该引理证明参考文献 [6]。
引理2:序列 单调递减且收敛,且我们有
证明:该引理证明参考文献 [6]。
定理1:
1)序列 有界。
2) 。
3)任意序列的聚点都是稳定点。
证明:
1) 由引理2可知整个序列 都包含于下列水平集合:
那么由 ,我们可推知序列 有界。
2) 显然,我们有:
由引理2可知:
将上式两边从 加到N。则由引理2和M的定义我们有
从而我们可以推断出 。
3) 令 为序列的聚点且存在 使得 。那么由一阶最优条件,我们有
由 ,我们可以得到
由函数 的凸性, 连续性以及 ,我们有
这就说明了 是算法的稳定点。
4. 数值实验
本节将算法用于数值实验,运行环境为MATLAB R2014a 2.80 GHz CPUs。我们先简单介绍一下问题模型。
问题模型为马尔科夫随机场:
其中u是所求图像信息, 是噪声图像信息, 是非凸罚函数,表达式为:
其中 是学习率,是基于 权重的线性算子, 是滤子数,本文考虑7 * 7的滤波器 [6],且 。
对于 ,我们考虑学生t分布:
我们考虑高斯噪声,其中函数模型为 。
对于终止条件我们选择下述能量差:
其中, 是真实值(数值由 [6] 给出), 是每次迭代的值,两者做差即为能量差 。
为了增强对比效果,我们用iPiano-nml和iPiano-Backtracking作比较。iPiano-Backtracking为带回溯线搜索的iPiano算法:
当满足回溯线搜索时,令 否则令 。
在iPiano-nml中,令 为BB步长 [10]:
另外参数选取为:
在iPiano-Backtracking中,令参数选取为:
接下来我们给出峰值信噪比与迭代变化关系图:
Figure 1. Comparison of two algorithms
图1. 两个算法效果对比图
由图1中可知在过程中iPiano-nml比iPiano-Backtracking效果表现好。
下面给出效果对比图:
图2出了效果对比。上方左图为原始图像,右图为噪声图像。下方左图为iPiano-nml去噪效果,右图为iPiano-Backtracking去噪效果。图2验证了iPiano-nml算法的有效性。
Figure 2. Effect comparison
图2. 效果对比
5. 结论
本文在考虑一类非凸非光滑问题中借鉴了NPG的思想,将非单调线搜索整合到iPiano中,提出了带非单调技术的iPiano算法,并通过一定的条件证明了新算法的收敛性。本文将新算法运用于图像降噪实验,通过与原算法的对比说明新算法的有效性。以后我们的工作将研究新算法的收敛速度。
文章引用
刘海玉. 非凸优化中一种带非单调线搜索的惯性邻近算法
An Inertial Proximal Algorithm with Non-Monotone Line Search for Non-Convex Optimization[J]. 应用数学进展, 2021, 10(03): 732-739. https://doi.org/10.12677/AAM.2021.103080
参考文献
- 1. Curtis, F.E. and Scheinberg, K. (2017) Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning. In: Leading Developments from INFORMS Communities, 89-114. https://doi.org/10.1287/educ.2017.0168
- 2. Combettes, P.L. and Pesquet, J.C. (2011) Proximal Splitting Methods in Signal Processing. In: Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, D. and Wolkowicz, H. (Eds.), Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, New York, NY, 185-212. https://doi.org/10.1007/978-1-4419-9569-8_10
- 3. Boţ, R.I., Csetnek, E.R. and Hendrich, C. (2015) Inertial Douglas-Rachford Splitting for Monotone Inclusion Problems. Applied Mathematics and Computation, 256, 472-487. https://doi.org/10.1016/j.amc.2015.01.017
- 4. Wen, B. and Xue, X. (2019) On the Convergence of the Iterates of Proximal Gradient Algorithm with Extrapolation for Convex Nonsmooth Minimization Problems. Journal of Global Optimization, 75, 767-787. https://doi.org/10.1007/s10898-019-00789-8
- 5. Beck, A. and Teboulle, M. (2009) A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM journal on Imaging Sciences, 2, 183-202. https://doi.org/10.1137/080716542
- 6. Ochs, P., Chen, Y., Brox, T., et al. (2014) iPiano: Inertial Proximal Algorithm for Nonconvex Optimization. SIAM Journal on Imaging Sciences, 7, 1388-1419. https://doi.org/10.1137/130942954
- 7. Ochs, P. (2019) Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano. SIAM Journal on Optimization, 29, 541-570. https://doi.org/10.1137/17M1124085
- 8. Ochs, P. (2018) Local Convergence of the Heavy-Ball Method and iPiano for Non-Convex Optimization. Journal of Optimization Theory and Applications, 177, 153-180. https://doi.org/10.1007/s10957-018-1272-y
- 9. Chen, X., Lu, Z. and Pong, T.K. (2016) Penalty Methods for a Class of Non-Lipschitz Optimization Problems. SIAM Journal on Optimization, 26, 1465-1492. https://doi.org/10.1137/15M1028054
- 10. Barzilai, J. and Borwein, J.M. (1988) Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8, 141-148. https://doi.org/10.1093/imanum/8.1.141