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算法的有效性。
5. 结论
本文在考虑一类非凸非光滑问题中借鉴了NPG的思想,将非单调线搜索整合到iPiano中,提出了带非单调技术的iPiano算法,并通过一定的条件证明了新算法的收敛性。本文将新算法运用于图像降噪实验,通过与原算法的对比说明新算法的有效性。以后我们的工作将研究新算法的收敛速度。