非凸优化中一种带非单调线搜索的惯性邻近算法

An Inertial Proximal Algorithm with Non-Monotone Line Search for Non-Convex Optimization

摘要: 本文考虑一类目标函数由可微(可能非凸)函数和凸(可能非光滑)函数组成的极小化问题。惯性邻近(iPiano)算法是解决这类问题的一种有效而重要的方法。通过引入非单调线搜索，提出了非单调线搜索的iPiano (iPiano-nml)算法。通过证明说明了由iPiano-nml生成的序列的任何聚点都是一个稳定点。最后，对图像处理问题进行了数值实验来说明新算法的理论结果。

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.

1. 引言

本文考虑下列最小化问题：

$\underset{x\in R^n}{\min }F\left(x\right)=f\left(x\right)+g\left(x\right),$ (1)

其中， $f\left(x\right):R^N\to R$ 是一个光滑(可能非凸)且为梯度李普希兹连续函数， $g\left(x\right):R^N\to R$ 是一个正常下半连续凸(可能非光滑)函数。另外 $F\left(x\right)$ 是一个强制函数且有下界。

问题(1)出现在很多领域，如机器学习 [1]，信号处理 [2] 等。解决上述问题的经典方法是邻近梯度法 [3]：

$x^{k+1}\in \underset{x}{\arg \min }\left\{\langle \nabla f\left(x^k\right),x\rangle +\frac{\alpha }{2}{\Vert x-x^k\Vert }^2+g\left(x\right)\right\},$

其中 $\alpha$ 是步长。然而，邻近梯度算法在解决一些问题时，它的收敛速度较慢，于是人们逐渐地寻找一些策略来改善这样的问题。常见的一个有效的策略是加速方法，因此在上述邻近梯度法中，通过引入外推项，一些文献提出了加速邻近梯度算法 [4]，FISTA [5] 算法等。加速邻近梯度算法如下：

$x^{k+1}\in \underset{x}{\arg \min }\left\{\langle \nabla f\left(y^k\right),x\rangle +\frac{\alpha }{2}{\Vert x-y^k\Vert }^2+g\left(x\right)\right\},$

$y^k=x^k+{\beta }_k\left(x^k-x^{k-1}\right),$

其中 $\alpha$ 是步长， ${\beta }_k$ 是外推参数。这些算法的收敛速度为 $O\left(\frac{1}{k^2}\right)$。除此自外，惯性项也是一类能加速算法的有效策略，通过将邻近梯度法和惯性项结合得到下列惯性邻近算法(iPiano) [6] ]：

$x^{k+1}={\left(I+\alpha \partial g\right)}^{-1}\left(x^k-\alpha \nabla f\left(x^k\right)+\beta \left(x^k-x^{k-1}\right)\right),$ (2)

其中， $\alpha$ 是步长， $\beta$ 是惯性因子。iPiano在实际运行中收敛速度比邻近梯度法快，广泛地应用于非凸问题 [7] [8]。另一方面，线搜索也是一项能加速原始算法的有效策略，其非单调线搜索有更好的数值表现。非单调邻近梯度法(NPG) [9] 采用了下列线搜索：

$u\in \underset{x}{\arg \min }\left\{\langle \nabla f\left(x^k\right),x-x^k\rangle +\frac{L}{2}{\Vert x-x^k\Vert }^2+g\left(x\right)\right\},$

$F\left(u\right)\le \underset{{\left[k-M\right]}_{+}\le i\le k}{\max }F\left(x^i\right)-\frac{c}{2}{\Vert u-x^k\Vert }^2,$

其中c和M都大于0。该线搜索在每次迭代中通过选取k与 $k-M$ 之间的最大值来满足条件，从而保证目标函数有更大的下降。

本文在惯性邻近算法的基础上，将其与NPG结合，提出一种带非单调线搜索的惯性邻近算法，并将其运用于图像处理，通过信噪比来说明新算法的有效性。

2. 预备定义

本节给出一些基本的定义。本文考虑欧式空间且维数 $N\ge 1$。

定义1：令 $g\left(x\right)$ 为一个正常下半连续凸函数，那么邻近算子定义为：

${\left(I+\alpha \partial g\right)}^{-1}\left(\hat{x}\right)=\underset{x}{\arg \min }\frac{{\Vert x-\hat{x}\Vert }^2}{2}+\alpha g\left(x\right).$

引理1： $f\left(x\right):R^N\to R$ 为一个光滑函数且为L梯度李普希兹连续。则对于 $\forall x,y\in R^N$， $\exists L>0$，下式成立：

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert .$

引理2： $f\left(x\right):R^N\to R$ 为一个光滑函数且为L梯度李普希兹连续。则对于 $\forall x,y\in R^N$，我们成立以下下降引理

$f\left(x\right)\le f\left(y\right)+\langle \nabla f\left(y\right),x-y\rangle +\frac{L}{2}{\Vert x-y\Vert }^2.$

命题1：令 $F,f,g$ 满足上述定义，则对于 $x\in domF$，我们有下式成立：

$\partial F\left(x\right)=\nabla f\left(x\right)+\partial g\left(x\right).$

3. 算法和收敛性

本节给出iPiano-nml算法和收敛性分析。首先我们引入一个辅助序列：

$H_{\delta }\left(x,y\right)=f\left(x\right)+g\left(x\right)+\delta {\Vert x-y\Vert }^2.$

易知当时 $x=y$，我们有 $H_{\delta }\left(x,y\right)=f\left(x\right)+g\left(x\right)$。

3.1. iPiano-nml算法

iPiano-nml算法：

步骤0：选择 $x^0\in domF,x^0=x^{-1}$。 $c_1,c_2$ 接近0。 $L_{\max }\ge L_{\min }>0,\tau >1,c>0,M\ge 0$。

步骤k：1) 选择 $L_k\in \left[L_{\min },L_{\max }\right],y^k=x^k+{\beta }_k\left(x^k-x^{k-1}\right)$。

1a) 求解子问题：

$u\in \underset{x}{\arg \min }\left\{g\left(x\right)+\langle \nabla f\left(x^k\right),x\rangle +\frac{1}{2{\alpha }_k}{\Vert x-y^k\Vert }^2\right\}.$

1b) 如果满足

$H_{{\delta }_{k+1}}\left(u,x^k\right)\le \underset{{\left[k-M\right]}_{+}\le i\le k}{\max }{H}_{{\delta }_i}\left(x^i,x^{i-1}\right)-\frac{c}{2}{\Vert u-x^k\Vert }^2,$

那么进行步骤2)。

1c) 令 $L_k\leftarrow \tau L_k$，继续步骤1a)。

2) 令 $x^{k+1}\leftarrow u,k\leftarrow k+1$ 然后进行步骤1)。

其中序列满足 ${\alpha }_k\ge c_1,{\beta }_k\ge 0,{\delta }_k\ge {\gamma }_k\ge c_2$。 ${\delta }_k$ 单调递减，另有：

${\delta }_k=\frac{1}{{\alpha }_k}-\frac{L_k}{2}-\frac{{\beta }_k}{2{\alpha }_k},{\gamma }_k=\frac{1}{{\alpha }_k}-\frac{L_k}{2}-\frac{{\beta }_k}{{\alpha }_k}.$

3.2. 收敛性分析

引理1：对于 $k\ge \text{0}$，存在 ${\delta }_k\ge {\gamma }_k,{\beta }_k\in \left[0,1\right),{\alpha }_k<\frac{2\left(1-{\beta }_k\right)}{L_k}$。另外给定 $L_k\ge \text{0}$，存在 ${\alpha }_k,{\beta }_k$ 满足 ${\delta }_k$ 单调递减。

证明：该引理证明参考文献 [6]。

引理2：序列 ${\left(H_{{\delta }_k}\left(x^k,x^{k-1}\right)\right)}_{k=0}^{\infty }$ 单调递减且收敛，且我们有

$H_{{\delta }_{k+1}}\left(x^{k+1},x^k\right)\le H_{{\delta }_k}\left(x^k,x^{k-1}\right)-{\gamma }_k{\Vert x^k-x^{k-1}\Vert }^2.$

证明：该引理证明参考文献 [6]。

定理1：

1)序列 $\left\{x^k\right\}$ 有界。

2) $\underset{k\to \infty }{\lim }\Vert x^k-x^{k-1}\Vert =0$。

3)任意序列的聚点都是稳定点。

证明：

1) 由引理2可知整个序列 $\left\{x^k\right\}$ 都包含于下列水平集合：

$\left\{x\in R^N:\underset{\_}{F}\le F\left(x\right)\le H_{{\delta }_0}\left(x^0,x^{-1}\right)\right\}.$

那么由 $\underset{\_}{F}=\inf F\left(x\right)>\infty$，我们可推知序列 $\left\{x^k\right\}$ 有界。

2) 显然，我们有：

$\begin{array}{l}{H}_{{\delta }_{k+1}}\left(x^{k+1},x^k\right)-\underset{{\left[k-M\right]}_{+}\le i\le k}{\max }{H}_{{\delta }_i}\left(x^i,x^{i-1}\right)\\ =f\left(x^{k+1}\right)+g\left(x^{k+1}\right)+{\delta }_{k+1}{\Vert x^{k+1}-x^k\Vert }^2-\underset{{\left[k-M\right]}_{+}\le i\le k}{\max }\left\{f\left(x^i\right)+g\left(x^i\right)+{\delta }_i{\Vert x^i-x^{i-1}\Vert }^2\right\}\\ \le f\left(x^{k+1}\right)+g\left(x^{k+1}\right)+{\delta }_{k+1}{\Vert x^{k+1}-x^k\Vert }^2-f\left(x^k\right)-g\left(x^k\right)-{\delta }_k{\Vert x^k-x^{k-1}\Vert }^2\\ =H_{{\delta }_{k+1}}\left(x^{k+1},x^k\right)-H_{{\delta }_k}\left(x^k,x^{k-1}\right).\end{array}$

由引理2可知：

$H_{{\delta }_{k+1}}\left(x^{k+1},x^k\right)-\underset{{\left[k-M\right]}_{+}\le i\le k}{\max }{H}_{{\delta }_i}\left(x^i,x^{i-1}\right)\le -{\gamma }_k{\Vert x^k-x^{k-1}\Vert }^2.$

将上式两边从 $k=0$ 加到N。则由引理2和M的定义我们有

$\begin{array}{l}0<{\displaystyle \underset{k=0}{\overset{N}{\sum }}{\gamma }_k{\Vert x^k-x^{k-1}\Vert }^2}\le {\displaystyle \underset{k=0}{\overset{N}{\sum }}\underset{{\left[k-M\right]}_{+}\le i\le k}{\max }{H}_{{\delta }_i}\left(x^i,x^{i-1}\right)-H_{{\delta }_{k+1}}\left(x^{k+1},x^k\right)}\\ =\left(M-1\right)H_{{\delta }_0}\left(x^0,x^{-1}\right)-\cdots -H_{{\delta }_{N-M+2}}\left(x^{N-M+2},x^{N-M+1}\right)\\ -H_{{\delta }_{N-M+3}}\left(x^{N-M+3},x^{N-M+2}\right)-\cdots -H_{{\delta }_N}\left(x^N,x^{N-1}\right)-H_{{\delta }_{N+1}}\left(x^{N+1},x^N\right)<\infty ,\end{array}$

从而我们可以推断出 $\underset{k\to \infty }{\lim }\Vert x^k-x^{k-1}\Vert =0$。

3) 令 $x^{*}$ 为序列的聚点且存在 $\left\{x^{k_j}\right\}$ 使得 $\underset{j\to \infty }{\lim }{x}^{k_j}=x^{*}$。那么由一阶最优条件，我们有

$-\frac{1}{{\alpha }_{k_j}}\Vert x^{k_j+1}-y^{k_j}\Vert \in \partial g\left(x^{k_j+1}\right)+\nabla f\left(x^{k_j}\right).$

由 $y^{k_j}=x^{k_j}+{\beta }_{k_j}\left(x^{k_j}-x^{k_j-1}\right)$，我们可以得到

$-\frac{1}{{\alpha }_{k_j}}\Vert x^{k_j+1}-x^{k_j}-{\beta }_{k_j}\left(x^{k_j}-x^{k_j-1}\right)\Vert \in \partial g\left(x^{k_j+1}\right)+\nabla f\left(x^{k_j}\right).$

由函数 $g\left(x\right)$ 的凸性， $\nabla f\left(x\right)$ 连续性以及 $\Vert x^k-x^{k-1}\Vert =0$，我们有

$0\in \nabla f\left(x^{*}\right)+\partial g\left(x^{*}\right),$

这就说明了 $x^{*}$ 是算法的稳定点。

4. 数值实验

本节将算法用于数值实验，运行环境为MATLAB R2014a 2.80 GHz CPUs。我们先简单介绍一下问题模型。

问题模型为马尔科夫随机场：

$\underset{u\in R^N}{\min }{\displaystyle \underset{i=1}{\overset{N_f}{\sum }}{\zeta }_i\varphi \left(K_{i}u\right)}+g\left(u,u^0\right),$

其中u是所求图像信息， $u^0$ 是噪声图像信息， $\varphi$ 是非凸罚函数，表达式为：

$\varphi \left(K_{i}u\right)={\displaystyle \underset{p}{\sum }\phi }\left({\left(K_{i}u\right)}_p\right),$

其中 $K_i$ 是学习率，是基于 ${\zeta }_i$ 权重的线性算子， $N_f$ 是滤子数，本文考虑7 * 7的滤波器 [6]，且 $K_{i}u=k_i\ast u$。

对于 $\phi \left(t\right)$，我们考虑学生t分布：

$\phi \left(t\right)=\log \left(1+t^2\right).$

我们考虑高斯噪声，其中函数模型为 $g\left(u,u^0\right)=\frac{\lambda }{2}{\Vert u-u^0\Vert }^{\text{2}}$。

对于终止条件我们选择下述能量差：

${\epsilon }_k=F_k-F_{*},$

其中， $F_{*}$ 是真实值(数值由 [6] 给出)， $F_k$ 是每次迭代的值，两者做差即为能量差 ${\epsilon }_k$。

为了增强对比效果，我们用iPiano-nml和iPiano-Backtracking作比较。iPiano-Backtracking为带回溯线搜索的iPiano算法：

$f\left(x^{k+1}\right)\le f\left(x^k\right)+\langle \nabla f\left(x^k\right),x^{k+1}-x^k\rangle +\frac{L_k}{2}{\Vert x^{k+1}-x^k\Vert }^2\left(k\in N\right).$

当满足回溯线搜索时，令 $L_{k+1}=L_k/1.05$ 否则令 $L_{k+1}=L_k\ast 1.2$。

在iPiano-nml中，令 $L_k$ 为BB步长 [10]：

$L_k=\{\begin{array}{l}\min \left(\max \left(\frac{{\Vert s_{k-1}\Vert }^2}{s_{k-1}^{\text{T}}{l}_{k-1}},L_{\min }\right),L_{\max }\right)\left(s_{k-1}^{\text{T}}{l}_{k-1}\ne 0\right)\\ L_{\max },\text{otherwise}.\end{array}$

另外参数选取为：

$L_1=3,{\alpha }_k=\frac{2\ast \left(1-\beta \right)}{L_k}\ast 0.99,\beta =0.8,\lambda =1,c=4.8,\tau =1.6,M=2.$

在iPiano-Backtracking中，令参数选取为：

$L_1=3,{\alpha }_k=\frac{2\ast \left(1-\beta \right)}{L_k}\ast 0.99,\beta =0.8,\lambda =1.$

接下来我们给出峰值信噪比与迭代变化关系图：

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算法，并通过一定的条件证明了新算法的收敛性。本文将新算法运用于图像降噪实验，通过与原算法的对比说明新算法的有效性。以后我们的工作将研究新算法的收敛速度。