求解一类非凸非光滑问题的惯性邻近交替极小化算法

Inertial Proximal Alternating Minimization Algorithm for a Class of Nonconvex and Nonsmooth Problems

摘要: 本文考虑一类非凸非光滑优化问题，提出了一种惯性邻近交替极小化算法。通过构造一个新的效益函数H，并保证其具有下降性，证明了算法的全局收敛性。当H为Kurdyka-Lojasiewicz函数时，证明了算法的强收敛性。

Abstract: In this paper, we propose an inertial proximal alternating minimization algorithm for a class of nonconvex and nonsmooth problems. We show the global convergence by constructing a new merit function H with guaranteed descent property. If H satisfies the Kurdyka-Lojasiewicz property, we determine the strongly convergence of the whole sequence.

1. 引言

本文考虑如下非凸非光滑优化问题：

$\underset{x,y}{\min }L\left(x,y\right)=f\left(x\right)+g\left(y\right)+R\left(x,y\right)$ (1)

其中 $f:{ℝ}^n\to ℝ\cup \left\{\infty \right\}$ ， $g:{ℝ}^m\to ℝ\cup \left\{\infty \right\}$ 为正常下半连续函数， $R:{ℝ}^n\times {ℝ}^m\to ℝ$ 连续可微。这一模型广泛应用于信号恢复、图像处理等问题。

求解问题(1)的常用方法是基于Gauss-Seidel迭代的交替极小化方法，迭代形式如下：

$\{\begin{array}{l}{x}^{k+1}\in \arg \min \left\{L\left(x,y^k\right):x\in {ℝ}^n\right\},\\ y^{k\text{+}1}\in \arg \min \left\{L\left(x^{k+1},y\right):y\in {ℝ}^m\right\}\end{array}$ (2)

在凸的情况下， [1] 证明当 $L\left(x,y\right)$ 连续可微，且关于x或y严格凸时，序列 $\left\{\left(x^k,y^k\right)\right\}$ 的每一个极限点都是 $L\left(x,y\right)$ 的稳定点。 [2] 通过引入正则项去掉了 [1] 中的严格凸条件，提出邻近交替极小化方法(PAM)，迭代格式如下：

$\{\begin{array}{l}{x}^{k+1}\in \text{arg}\underset{x}{\min }\left\{L\left(x,y^k\right)+\frac{c_k}{2}{\Vert x-x^k\Vert }^2\right\},\\ y^{k+1}\in \text{arg}\underset{y}{\min }\left\{L\left(x^{k+1},y\right)+\frac{d_k}{2}{\Vert y-y^k\Vert }^2\right\}\end{array}$

对于问题(1)，本文在惯性思想的启发下，结合邻近交替极小化方法，提出一种惯性邻近交替极小化算法。惯性思想最早由Alvarez [3] 提出，用来解决动力系统问题。惯性思想是指为了得到下一步迭代点需要用到当前迭代点与上一步迭代点的信息，其优点是加快收敛速度。近年来，这一惯性类型的算法越来越受关注。如惯性向前向后分裂算法 [4] [5] ，惯性Douglas-Rachford 分裂算法 [6] ，惯性ADMM [7] 等。

2. 预备知识

本节列出本文用到的基本概念及性质。

设 $\eta \in \left(0,+\infty \right]$ ，记 ${\Phi }_{\eta }$ 为满足如下条件的凹可微函数 $\phi :\left[0,\eta \right)\to \left[0,+\infty \right)$ 的集合

(i) $\phi =0$ ；

(ii) $\phi$ 在 $\left(0,\eta \right)$ 上连续；

(iii) ${\phi }^{\prime }\left(s\right)>0$ ， $\forall s\in \left(0,\eta \right)$ 。

定义1 (Kurdyka-Lojasiewicz性质)设 $\sigma :{ℝ}^d\to \left(-\infty ,+\infty \right]$ 是正常下半连续函数。

(i) 设 $\bar{u}\in \text{dom}\partial \sigma :=\left\{u\in {ℝ}^d:\partial \sigma \left(u\right)\ne \varnothing \right\}$ ，若存在 $\eta \in \left(0,+\infty \right]$ ， $\bar{u}$ 的一个邻域U及 $\phi \in {\Phi }_{\eta }$ 有

${\phi }^{\prime }\left(\sigma \left(u\right)-\sigma \left(\bar{u}\right)\right)\text{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1$ ， $\forall u\in U\cap \left[\sigma \left(\bar{u}\right)<\sigma \left(u\right)<\sigma \left(\bar{u}\right)+\eta \right]$

则称 $\sigma$ 在 $\bar{u}$ 处有Kurdyka-Lojasiewicz (KL)性质。

(ii) 若 $\sigma$ 在 $\text{dom}\partial \sigma$ 中的每一点都满足KL性质，则称 $\sigma$ 为KL函数。

引理1 (一致Kurdyka-Lojasiewicz性质)设集合 $\Omega$ 是紧集， $\sigma :{ℝ}^d\to ℝ\cup \left\{\infty \right\}$ 是正常下半连续函数。若 $\sigma$ 在 $\Omega$ 上为常数，且在 $\Omega$ 的每一点处都满足KL性质。设 $\bar{u}\in \Omega$ ，则存在 $\epsilon >0,\eta >0,\phi \in {\Phi }_{\eta }$ 使得

${\phi }^{\prime }\left(\sigma \left(u\right)-\sigma \left(\bar{u}\right)\right)\text{dist}\left(0,\partial \sigma \left(u\right)\right)\ge 1$ ， $\forall \left\{u\in {ℝ}^d:d\left(u,\Omega \right)<\epsilon \right\}\cap \left\{\sigma \left(\bar{u}\right)<\sigma \left(u\right)<\sigma \left(\bar{u}\right)+\eta \right\}$

引理2 [8] $h:{ℝ}^n\to ℝ$ 是连续可微函数， $\nabla h$ Lipschitz连续(Lipschitz常数为L)，则对任意 $x,y\in {ℝ}^n$ ，有

$\left|h\left(y\right)-h\left(x\right)-\langle \nabla h\left(x\right),y-x\rangle \right|\le \frac{h}{2}{\Vert y-x\Vert }^2$

3. 算法及假设条件

本文需要如下假设条件：

假设1 (i) $\inf L\left(x,y\right)=f\left(x\right)+g\left(y\right)+R\left(x,y\right)>-\infty$ ,

(ii) 对任意固定的y， ${\nabla }_{x}R\left(x,y\right)$ 关于x是Lipschitz连续的， $L_1\left(y\right)$ 为Lipschitz常数，即

$\Vert {\nabla }_{x}R\left(x_1,y\right)-{\nabla }_{x}R\left(x_2,y\right)\Vert \le L_1\left(y\right)\Vert x_1-x_2\Vert ,\forall x_1,x_2\in {ℝ}^n$

(iii) 对任意固定的x， ${\nabla }_{y}R\left(x,y\right)$ 关于y是Lipschitz连续的，为Lipschitz常数，即

(iv) 存在，使得，。

(v)在的有界子集上Lipschitz连续，即对任意有界集，，使得，，有

惯性邻近交替极小化算法(IPAM)：

步0. 给定初始点，选取，。

步1. 令，计算

(3)

步2. 取，并计算

(4)

步3. 令，计算

(5)

4. 收敛性分析

记为惯性邻近交替极小化算法产生的序列。

4.1. 充分下降性

引理3：若假设1成立，则

(6)

其中，，。

证明：由(3)，(5)知，

(7)

(8)

由引理2得

将上述不等式代入(7)，(8)得

以上两式相加得

由不等式，，，及假设(v)可知，

进一步由，及假设(ii)，得

移项后可证得(6)式成立。

注1. 若参数满足下列不等式条件

则有，且。

注2. 记,。则有

(9)

其中。

4.2. 次微分的范数估计

引理4：若假设1成立，有界，令

(10)

则，。更进一步，存在常数，使得

证明：由最优性条件可知，

因此，

根据函数H的定义，得

故。

由假设1(v)，得

因此，存在，使得。

引理5：若假设1成立，有界，则。

证明：由假设1(i)知有下界，故也有下界，再由注2，非增。根据单调有界定理可知，收敛，其极限为。

令N为正整数，将(9)式从到相加，得

令N趋于无穷，得

故，。

又

因此，。

4.3. 收敛结论

记为序列的一个极限点，。

定理1：设为序列的极限点集。若假设1成立，有界，则有以下结论成立

(i)是非空紧的连通集，且，

(ii)，

(iii) 当且仅当时，，

(iv)，

(v) H在上恒为常数。

证明：(i) 证明可参照文献 [9] 引理5。

(ii) 对任意，则存在一个子序列，有。由f的下半连续性，有。

再由的定义得，

取，有

(11)

在引理5的证明中得，。

而，对(11)式中的取上极限，得。因此，。同样地，。根据R的连续性， 。故

由引理4及(10)知， ()。再由的闭性，有。因此，。

(iii) 由引理5及的定义，结论得证。

(iv) 由引理4及引理5知，，。则()，再由的闭性，有，即。

(v) 记，(h为常数)。对任意，则存在一个子序列，使得。再根据(iii)证明过程中所得。于是，，即H在上恒为常数。

定理2：假设H是Kurdyka-Lojasiewicz函数，有界，则

(i)，

(ii)序列收敛到L的一个稳定点。

证明：由定理1，，。接下来，将分成两种情况证明。

Case1. 存在一个正整数，使得。由注2知，，则，。于是，定理得证。

Case2. 对所有，有。根据极限的定义，由，则对给定，，，使得当时，有。由定理1(i)，即对给定，，，使得当时，有。于是，对给定，有，，。

(i) 由引理1，则，有

由的凹性，

(12)

记。利用注2，结合(12)式，有

移项后，不等号两边同时开方，根据不等式得

(13)

再由得

将(13)式代入上式，得

将上式从相加得

因为，则

于是，

令N趋于无穷，得

故，。

于是，

，

因此，。

(ii) 由(i)可知为柯西序列，故收敛。由定理1，可知收敛到L的一个稳定点。

5. 数值试验

为了验证算法的有效性与可行性，本节应用惯性邻近交替极小化算法(IPAM)及邻近交替极小化算法(PAM)求解问题。数值试验过程均由MATLAB(2014a)实现，程序运行环境为：Windows 7 (64 bite)，RAM：4G，CPU：@ 1.60 GHz 2.30 GHz。

在压缩感知中，基础的问题是从m个不完全实验数据中恢复一个n维的稀疏信号x，()。该问题可转化为如下模型：

或正则化形式

其中是实验矩阵，是观察信号，是正则化参数，表示x中非零元素的个数。一般情况下，上述模型是NP难问题。为了克服这一困难，可以用拟范数来松弛问题，考虑下述问题

其中。通过引入一个新的变量，将问题转化为带约束的问题

再用罚函数方法将上述问题转化为问题(1)的形式

(14)

利用IPAM求解问题(14)，有

其中被称为half-shrinkage算子 [10] 。

利用PAM求解问题(14)，有

在试验过程中，选取，并正则化每一列，随机生成含有100个非零元素的稀疏向量，每一个样本都服从正态分布。向量，其中，正则化参数，其中。选取参数如下：，，，，，。除外的其他参数，两种算法选取相同的参数值。终止准则为

为给定的误差值。计算两种算法在不同情况下分别所需的迭代次数，迭代时间及目标函数值。由图1可知，IPAM与PAM目标函数都趋于一个固定值，说明两种算法都收敛。且由表1知，IPAM比PAM运行时间更少，收敛速度更快。

Table 1. Numerical result

表1. 数值结果

Figure 1. The trend of objective function varies with iterations

图1. 目标函数随迭代次数变化趋势

基金项目

获国家自然科学基金青年基金(No. 1160195)，国家自然科学基金(No. 71861002)，广西自然科学基金青年基金(2017GXNSFBA380185)，(2017GXNSFBA198238)资助。

NOTES

^*通讯作者。