由于非凸函数比凸函数通常能够更好地近似原问题, 所以大量问题需对非凸目标函数或非凸约束条件进行优化决策. 近年来, 非凸非光滑优化问题受到众多学者的广泛关注与研究^[1⇓-3], 并提出了一些有效和稳定的算法. 在本文中, 我们考虑解决如下非凸非光滑不可分优化问题

其中 $f:\mathbb{R}^l\rightarrow {(-\infty,+\infty]}$, $g:\mathbb{R}^m\rightarrow {(-\infty,+\infty]}$ 是正常下半连续函数, $Q(x,y):\mathbb{R}^l\times \mathbb{R}^m \rightarrow \mathbb{R}$ 连续可微且 $\nabla Q$ 在有界集上 Lipschitz 连续. 注意到目标函数都没有凸性的假设. 许多应用问题可以被建模为问题 (1.1), 例如, 信号与图像处理^[4⇓-6]、矩阵分解^[7]、二次分式规划^[8]、 压缩感知^[9,10]、应用统计和机器学习^[11] 等.

为了求解问题 (1.1), 自然考虑利用两分块结构, 采取交替极小化算法. 也就是, 给定一个初始点 $\left ( x_{0},y_{0} \right ) \in \mathbb{R}^l \times \mathbb{R}^m$, 通过以下算法生成迭代序列 $\left \{ \left ( x_{k},y_{k} \right ) \right \}$

在一些文献中, 交替极小化算法也被称为 Gauss-Seidel 法或块坐标下降法. 在文献 [12⇓-14] 中, 针对目标函数具有凸性的情况下研究交替极小化算法. 当 $L(x, y)$ 为连续可微凸函数, 且 $L$ 关于变量 $x$ 或 $y$ 严格凸时, 由该算法产生的序列 $\left \{ \left ( x_{k},y_{k} \right ) \right \}$ 的每一个极限点都是 $L$ 的极小值点^[12⇓-14]. 为了提高算法的收敛速度、减弱算法的收敛条件, 文献 [15] 通过引入邻近项来去掉严格凸性的假设, 提出了如下邻近交替极小化算法 (PAM)

其中 $\lambda_k>0$, $\mu_k>0$. Attouch 等在文献 [16] 中应用 (1.3) 式求解非凸非光滑不可分优化问题 (1.1), 并证明了由 PAM (1.3) 生成的序列收敛到稳定点.

因为邻近交替极小化算法在每次迭代时都需要得到精确解, 所以 (1.3) 式中的子问题可能很难解决. 线性化技术是克服子问题没有解析解的有效方法之一. Bolte 等^[7] 受邻近向前向后分裂算法的启发, 在耦合项 $Q(x, y)$ 连续可微的条件下对 (1.3) 式中的每个子问题进行线性化, 提出了邻近交替线性极小化算法 (PALM) 求解问题 (1.1). 具体来说, 对于 $x$ 子问题, 在 $x_k$ 处线性化函数 $Q(x,y_{k})$, 对于 $y$ 子问题, 在 $y_k$ 处线性化函数 $Q(x_{k+1},y)$, 提出了如下的 PALM

如果 $f$ 或 $g$ 的邻近算子有封闭的形式, 则 (1.4)式的子问题易于求解. 文献 [7] 证明了由 PALM 生成的每个有界序列全局收敛到稳定点. 当 $f$ 和 $g$ 连续可微时, 一个自然的想法是线性化 $f$ 和 $g$. Nikolova 等在文献 [17] 中提出了相应的算法, 称为交替结构自适应的邻近梯度下降 (ASAP) 法. 利用 Kurdyka-Łojasiewicz 性质, 他们建立了由所提算法生成的整个序列的收敛性.

惯性外推源于二阶动力系统的重力球方法^[18], 此技术在每次迭代的计算量基本不变, 在计算下一步时用到前两步或多步的信息. 惯性外推技术能有效地改进算法的数值表现 (特别是一阶算法), 所以这种方法被广泛应用于加速凸优化和非凸优化的迭代算法^[19,20].

近年来, 很多学者关注并提出多种惯性算法, 如 Le 等在文献 [21] 中提出了求解非凸非光滑优化问题的块坐标下降惯性算法. Feng 等在文献 [22] 中针对非凸非光滑优化问题提出了惯性 Douglas-Rachford 分裂算法, 并将惯性外推技术纳入了 Douglas-Rachford 分裂算法的框架中. 特别地, 为了解决问题 (1.1), Zhang 和 He^[23] 提出了惯性邻近交替极小化方法, Pock 和 Sabach^[24]结合线性化技术提出了如下惯性邻近交替线性极小化 (iPALM) 算法

其中 $\alpha _{1k},\alpha _{2k},\beta _{1k},\beta _{2k}\in \left [ 0,1 \right ]$. 当目标函数满足 Kurdyka-Łojasiewicz 性质时, 他们证明由该算法生成的序列全局收敛到稳定点. 当 $\alpha _{1k}=\alpha _{2k}=\beta _{1k}=\beta _{2k}=0$ 时, 惯性邻近交替线性极小化算法 (iPALM) 为 PALM. Cai 等^[25] 提出如下的 Gauss-Seidel 型惯性邻近交替线性极小化算法 (GiPALM)

为了尽可能地利用现有的信息, Wang 等^[26]提出了另一种惯性邻近交替线性极小化 (NiPALM) 算法, 该算法结合了 iPALM 和 GiPALM. 当 $f$, $g$ 连续可微时, Yang 等^[27] 基于交替结构自适应的邻近梯度下降法 (ASAP), 利用惯性外推技术提出了加速交替结构自适应的邻近梯度下降算法 (aASAP).

Bregman 距离作为 2 范数平方距离的推广, 在使用时具有更大的灵活性, 生成函数不局限于 2 范数平方. 虽然 Bregman 距离不是真正的距离, 但采用 Bregman 距离正则化使得算法的适用性更广. 有时选择适当的 Bregman 距离可以得到子问题的显示解, 提高算法的收敛速度, 因此很多算法采用 Bregman 距离正则化来提高数值效果. 在文献 [28] 中, 针对问题 (1.1), 作者利用前三步迭代信息提出了如下两步惯性 Bregman 交替极小化算法 (TiBAM)

其中 $D_{\phi_i}(i=1,2)$ 是函数 $\phi_i(i=1,2)$ 生成的 Bregman 距离. 在效益函数满足 Kurdyka-Łojasiewicz 性质的条件下, 证明了算法的全局收敛性. 基于交替极小化算法, Chao 等^[29] 提出了如下惯性 Bregman 交替极小化算法 (BIAM) 求解问题(1.1)

在效益函数满足 Kurdyka-Łojasiewicz 性质且合理选择参数的条件下, 给出了算法的全局收敛性分析.

本文基于邻近交替极小化算法, 结合惯性外推技术、线性化技术和 Bregman 距离, 利用前三次迭代的信息, 构造了两步惯性 Bregman 邻近交替线性极小化算法, 并在效益函数满足 Kurdyka-Łojasiewicz 性质的假设下, 给出了所提出算法的全局收敛性分析.

本文内容组织如下: 在第二部分, 我们回顾了一些概念和重要引理, 这些概念和引理将用于证明主要的收敛结果. 在第三部分, 我们提出了两步惯性 Bregman 邻近交替线性极小化算法, 并给出收敛性分析. 最后, 在第四部分, 应用提出的算法求解稀疏非负矩阵分解、信号恢复和二次分式规划问题, 通过数值结果显示所提出算法的有效性.

维数为 $d\geq 1$ 的欧几里得向量空间记为 $\mathbb{R}^d$, 本文用 $\langle\cdot,\cdot\rangle$ 表示标准内积, 用 $\|\cdot\|_2$ 表示范数. 使用 $\omega(x_k)=\{x:\exists x_{k_j} \rightarrow x\}$ 来表示 $\{x_k\}_{k\in \mathbb{N}}$ 的极限集.

给定一个函数 $f: \mathbb{R}^d \rightarrow(-\infty,+\infty]$, $f$ 的有效域和上方图分别定义为 dom$f:=\{x\in \mathbb{R}^d: f(x)<+\infty\}$ 和 epi$f:=\{(x,\alpha )\in \mathbb{R}^d\times \mathbb{R}: f(x)\le \alpha \}$. 如果 dom$f\neq \emptyset$, 则称 $f$ 是正常的; 如果 epi$f$ 是闭的, 则 $f$ 在 $x$ 处下半连续. 下面给出本文所需要的一些基本概念和基本性质^[30,31].

定义 2.1 设 $f: \mathbb{R}^d \rightarrow(-\infty,+\infty]$ 是正常下半连续函数.

(1) 若 $x\in$ dom $f$, 定义如下集合

为函数 $f$ 在 $x\in$ dom $f$ 处的 Fréchet 次微分, 记作 $\hat{\partial}f(x)$. 若 $x\not\in$ dom$f$, 定义 $\hat{\partial}f(x)=\emptyset$. 称集合

为 $f$ 在 $x\in$ dom $f$ 处的极限次微分^[32], 记作 $\partial f(x)$.

注 2.1 根据上述定义, 可得

(a) 对于 $\forall x\in \mathbb{R}^d$, 有 $\hat{\partial}f(x)\subseteq \partial f(x)$, 其中 $\hat{\partial}f(x)$ 是闭凸的, $\partial f(x)$ 仅是闭集^[32].

(b) ($\partial f$ 的闭性) 设 $\{x_k\}_{k\in \mathbb{N}}$ 和 $\{v_k\}_{k\in \mathbb{N}}$ 为 $\mathbb{R}^d$ 中的序列, 并且对 $\forall k\in \mathbb{N}$, $v_k \in \partial f(x_k)$. 如果当 $k\rightarrow \infty$ 时, $(x_k,v_k)\rightarrow (x,v)$, $f(x_k)\rightarrow f(x)$, 那么 $v \in \partial f(x)$.

(c) $x\in \mathbb{R}^d$ 是 $f$ 极小值的一个必要 (但不充分) 条件是

(d) 如果 $f: \mathbb{R}^d \rightarrow(-\infty,+\infty]$ 是正常下半连续函数, $h : \mathbb{R}^d \rightarrow \mathbb{R}$ 是连续可微函数, 那么对 $\forall x \in \mathbb{R}^d$, 都有 $\partial(f+h)(x) = \partial f(x)+\nabla h(x)$.

Kurdyka-Łojasiewicz 性质对算法的收敛结果起着至关重要的作用. 现在我们给出 Kurdyka-Łojasiewicz 性质的定义.

设 $f: \mathbb R^d \rightarrow(-\infty,+\infty]$ 是正常下半连续函数, $\eta_1$, $\eta_2$ 满足 $-\infty <\eta_1<\eta_2 \leq +\infty$, 记

定义 2.2 (Kurdyka-Łojasiewicz 性质) 函数 $f: \mathbb R^d \rightarrow(-\infty,+\infty]$ 是正常下半连续函数, $x^\ast\in$ dom$f$, 若存在 $\eta\in (0,+\infty]$, $x^\ast$ 的邻域 $U$ 及连续凹函数 $\varphi:[0,\eta)\rightarrow \mathbb R_{+}$, 使得 $\varphi(0)=0$, $\varphi$ 在 $(0,\eta)$ 上连续可微, $\forall s\in(0,\eta)$ 有 $\varphi'(s)>0$, 且 $\forall x\in U\cap[f(x^\ast)<f<f(x^\ast)+\eta]$, Kurdyka-Łojasiewicz 不等式

都成立, 则称函数 $f$ 在 $x^\ast\in$ dom $f$ 具有 Kurdyka-Łojasiewicz (KŁ) 性质. 若函数 $f$ 在 dom $f$ 中的每一点都满足 KŁ 性质, 则函数 $f$ 称为 KŁ 函数.

在应用中很多目标函数具有 KŁ 性质, 典型的函数包括强凸函数、实解析函数、半代数函数^[16]、 次解析函数^[33] 和对数--指数函数. 我们注意到当 $0 < q< 1$ 时, $L_q$ 上的拟范数 $\|x\|_q:= (\Sigma_i|x_i|^q)^{1/q}$, 无穷范数 $\|x\|_\infty:= \max_i|x_i|$, 以及关于 $x$ 的函数 $\|Ax-b\|_q^q$ 和 $\|Ax-b\|_\infty$ 都是半代数函数, 所以它们都满足 Kurdyka-Łojasiewicz 性质.

已知实解析函数和半代数函数都是次解析的. 一般来说, 两个次解析函数的和不一定是次解析的. 然而, 对于两个次解析函数, 如果至少有一个函数将有界集映射到有界集, 那么它们的和也是次解析的, 见文献 [34]. 特别地, 次解析函数与解析函数的和函数是次解析的. 典型的次解析函数包括 $\|Ax-b\|^2_2+\lambda\|y\|_q^q$, $\|Ax-b\|_2^2+\lambda\Sigma_i(y_i^2 +\varepsilon)^{q/2}$ 等.

定义 2.3 设 $f: \mathbb R^d \rightarrow(-\infty,+\infty]$, 如果有效域 dom$f$ 是凸集, 且对任意的 $x$, $y\in$dom$f$, $\alpha\in[0,1]$, 有

成立, 则称函数 $f$ 是凸的. 如果存在 $\theta>0$ 使得 $f-\frac{\theta}{2}\|\cdot\|^2$ 是凸的, 则称 $f$ 为 $\theta$-强凸的, 即对任意的 $x$, $y\in$dom$f$, $\alpha\in[0,1]$, 有

成立.

假设函数 $f$ 是可微的, 那么 $f$ 是凸的当且仅当 dom$f$ 是凸集并且对任意的 $x$, $y\in$dom$f$, 有

成立. 再者, $f$ 为 $\theta$-强凸的当且仅当对任意的 $x$, $y\in$dom$f$, 有

成立.

作为 2 范数平方距离的推广, Bregman 距离具有许多与 2 范数平方距离相似的良好性质. 然而, Bregman 距离并不是真正的距离, 因为它不满足三角不等式或对称性, 但使用 Bregman 距离使得算法的应用更加广泛.

定义 2.4 设 $\phi:\mathbb{R}^d \rightarrow(-\infty,+\infty]$ 是凸可微函数. 定义

为 $\phi$ 生成的 Bregman 距离, 其中 $D_\phi :$ dom$\phi\,\,\times$ intdom$\phi \rightarrow [0,+\infty)$.

若 $\phi(x)=\frac{1}{2}\|x\|^2$, 则 $D_\phi(x,y)=\frac{1}{2}\|x-y\|^2$. 此外, 对于 $d$ 阶正定矩阵 $M$, 令 $\|x\|_M:=\sqrt{\langle x,Mx\rangle}$, 并取 $\phi(x)=\|x\|_M^2$, 则 $D_\phi(x,y)=\|x-y\|_M^2$, 见文献 [35]. 特别地, 如果 $M$ 是单位矩阵, 那么 $D_\phi(x,y)$ 为欧几里得平方距离.

由 Bregman 距离定义可知, 如果 $\phi$ 是 $\theta$-强凸的, 则

引理 2.1 (下降引理)^[20] 设 $f: \mathbb{R}^{d}\rightarrow \mathbb{R}$ 是一个连续可微函数, 假设梯度 $\nabla f$ 为 $L_{f}$-Lipschitz 连续的. 那么

假设 2.1 设 $\{u_k\}_{k\in \mathbb{N}}:=\{(z_k, z_{k-1}, z_{k-2})\}_{k\in \mathbb{N}}$ 是 $\mathbb{R}^{3p}$ 中的序列, 其中 $z_k, z_{k-1}, z_{k-2}\in \mathbb{R}^p$. 为了方便起见, 使用缩写 $\triangle_k := \|z_k-z_{k-1}\|_2$, 其中 $k\in \mathbb{N}$. 令 $F : \mathbb{R}^{3p}\rightarrow {(-\infty,+\infty]}$ 是正常下半连续函数且存在 $a>0$, $b>0$, 使得序列 $\{u_k\}_{k\in \mathbb{N}}$ 满足如下条件

(H1) (充分下降性). 任意 $k\in \mathbb{N}$, 都有

其中 $u_k=(z_k,z_{k-1},z_{k-2})$, 即 $F(z_{k+1}, z_{k}, z_{k-1})+ a\|z_{k+1}-z_k\|_2^2\leq F(z_k, z_{k-1}, z_{k-2})$ (此时称函数 $F$ 满足充分下降性);

(H2) (相对误差性). 任意 $k\in \mathbb{N}$, 存在 $w_{k+1}\in \partial F(u_{k+1})$ 使得

成立, 即 ${\|w_{k+1}\|_2\leq b(\|z_{k+1}-z_k\|_2+\|z_k-z_{k-1}\|_2+ \|z_{k-1}-z_{k-2}\|_2)}$ (此时称函数 $F$ 满足相对误差性);

(H3) (连续性条件). {存在子序列 $\{u_{k_j}\}_{j\in \mathbb{N}}$ 和 $\tilde{u}$} 使得当 $j\rightarrow\infty$ 时, 有

成立 (此时称函数 $F$ 满足连续性).

下面给出一个框架性收敛结果^[28], 可应用于分析本文提出算法的收敛性.

引理 2.2^[28] 设 $F: \mathbb{R}^{3p}\rightarrow {(-\infty,+\infty]}$ 是正常下半连续函数, 并且序列 $\{u_k\}_{k\in \mathbb{N}}= \{(z_k, z_{k-1},z_{k-2})\}_{k\in \mathbb{N}}$ 满足假设 2.1, 也就是条件 (H1), (H2) 和 (H3). 假设 $F$ 在 (H3) 中的聚点 $\widetilde{u}$ 处有 KŁ 性质, 则序列 $\{z_k\}_{k\in \mathbb{N}}$ 具有有限的长度, 即 $\sum\limits_{k=0}^{\infty}\|z_{k+1}-z_k\|_2<+\infty$. 而且, 当 $k \rightarrow\infty$ 时, 序列 $\{z_k\}_{k\in \mathbb{N}}$ 收敛于 $\widetilde{z}$, 其中 $\widetilde{u}=(\widetilde{z}, \widetilde{z}, \widetilde{z})$ 是 $F$ 的稳定点.

下面给出两步惯性 Brgeman 邻近交替线性极小化算法 (TiBPALM) 来求解问题 (1.1). 假设 $\phi_i$ 是 $\theta_i$-强凸可微函数, 且 $\nabla\phi_i$ 是 $L_{\nabla\phi_i}$-Lipschitz 连续的 $(1\le i\le 2)$. 令 $\theta=\min\{\theta_1,\theta_2\}$.

算法 3.1 选取 $(x_0,y_0)\in{\rm dom}L$, 并令 $(x_{-i},y_{-i})=(x_0,y_0)$, $i=1, 2$. 取序列 $\{\alpha_{1k}\}$, $\{\beta_{1k}\}\subseteq[\alpha_1]$ 和 $\{\alpha_{2k}\}$, $\{\beta_{2k}\}\subseteq[\alpha_2]$, 其中 $\alpha_1\geq0$ 和 $\alpha_2\geq0$. 对于 $k\geq 0$, 迭代步骤如下

其中 $D_{\phi_1}$ 和 $D_{\phi_2}$ 分别是函数 $\phi_1$ 和 $\phi_2$ 生成的 Bregman 距离.

由于 $f$ 和 $g$ 是正常下半连续函数, 且 $\phi_i$ ($i=1,2$) 是强凸的, 因此上面定义的迭代序列是有意义的, 即对每个 $k\geq 0$, 都可以保证 $(x_{k+1},y_{k+1})$ 存在.

注 3.1 下面给出了算法 1 的特殊情况.

(1) 设 $\lambda$ 和 $\mu$ 为正常数. 取 $\phi_1(x)=\frac{1}{2\lambda}\|x\|^2_2$ 和 $\phi_2(y)=\frac{1}{2\mu}\|y\|^2_2$, 其中 $x\in \mathbb{R}^l$ 和 $y\in \mathbb{R}^m$, 那么算法1 为

在这种情况下, 令 $\alpha_{2k}\equiv\beta_{2k}\equiv 0$, 算法1就是如下的一步惯性算法

令 $\alpha_{2k}\equiv\beta_{2k}=\alpha_{1k}\equiv\beta_{1k}\equiv 0$, 算法 1 就是邻近交替线性极小化算法 (PALM) PALM, 其中 $\lambda_k\equiv\lambda$ 和 $\mu_k\equiv\mu$.

(2) 令 $\alpha_{2k}\equiv\beta_{2k}\equiv 0$, 算法1为如下一步惯性 Bregman 邻近交替线性极小化算法 (iBPALM)

(3) 令 $\alpha_{2k}\equiv\beta_{2k}=\alpha_{1k}\equiv\beta_{1k}\equiv 0$, 算法 1 为如下 Bregman 邻近交替线性极小化算法 (BPALM)

为了得到算法 1 的收敛性分析, 我们作如下必要的假设.

假设 3.1 (1) $f(x)$, $g(y)$ 都是正常下半连续函数, $Q(x, y)$ 连续可微且梯度在有界集上 Lipschitz 连续, $L(x, y)$ 下方有界且强制.

(2) 对于任意固定的 $y$, 偏梯度 $\nabla_{x} Q$ 是全局 $L_1{\left ( y \right )}$-Lipschitz 连续的, 即

同样地, 对于任意固定的 $x$, 偏梯度 $\nabla_{y} Q$ 是全局 $L_2{\left (x \right )}$-Lipschitz 连续的, 即

(3) 对于 $i=1,2$, 存在 $0<L _{i}^{+}<\theta _{i}$, 使得

记 $\rho =\min\{\theta _{1} -L_{1}^{+}\, \theta _{2} -L_{2}^{+}\}$. 本文设 $\{(x_k,y_k)\}_{k\in \mathbb{N}}$ 是由算法 1 生成的序列且假设 3.1 成立. $\forall k\in \mathbb{N}$, 记 $z_k=(x_k,y_k)$, $\triangle_k=\|z_k-z_{k-1}\|_2$. 引入效益函数

值得注意的是, 当 $u=v=w$ 时, $H(u,v,w)= L(u)$.

引理 3.1 设 $2(\alpha_1+\alpha_2)<\rho$, 则如下结论成立

(1) 序列 $\{H(z_{k},z_{k-1},z_{k-2})\}_{k\in \mathbb{N}}$ 是单调递减且收敛的, 且

其中 $a=\frac{\rho-2(\alpha_1+\alpha_2)}{2}>0$;

(2) $\sum\limits_{k=0}^\infty\triangle_{k}^2<+\infty$, 因此 $\lim\limits_{k\rightarrow\infty}\triangle_{k}=0$;

(3) 序列 $\{L(x_k,y_k)\}_{k\in \mathbb{N}}$ 是收敛的.

证 (1) 根据算法 1, 可得

根据引理 2.1, 有

将 (3.5) 式和 (3.6) 式相加, 可得

则

根据 (2.1) 式和假设 3.1 (3), 再结合 (3.8) 式可得

同理,

将 (3.9) 式和 (3.10) 式相加, 可得

由于 $\rho =\min\{\theta _{1} -L_{1}^{+}\, \theta _{2} -L_{2}^{+}\}>0$, $\{\alpha_{1k}\}$, $\{\beta_{1k}\}\subseteq[\alpha_1]$ 且 $\{\alpha_{2k}\}$, $\{\beta_{2k}\}\subseteq[\alpha_2]$, 故

则

因此, (3.4) 式成立, 并且序列 $\{H(z_k,z_{k-1},z_{k-2})\}_{k\in \mathbb{N}}$ 是单调递减的. 根据假设 3.1 (1), $L$ 下方有界, 因此序列 $\{H(z_k,z_{k-1},z_{k-2})\}_{k\in \mathbb{N}}$ 收敛.

(2) 从 (3.4) 式中可得不等式

成立. 任取正整数 $K$, 将 (3.12) 式从 $k= 0,\cdots,K$ 相加 (注意到 $H(z_0, z_{-1},z_{-2})=L(z_0)$), 有

令 $K\rightarrow +\infty$, 由 $a>0$, 可得结论成立.

(3) 由效益函数定义可知

根据结论 (1) 和 (2), 可得序列 $\{L(x_k,y_k)\}_{k\in \mathbb{N}}$ 收敛并且

证毕.

引理 3.2 设 $\{z_k\}_{k\in \mathbb{N}}$ 是由算法 1 生成的序列. 当 $k\geq 0$ 时, 定义

则

进而, 如果序列 $\{z_k\}_{k\in \mathbb{N}}$ 是有界的, 则存在 $M>0$, 使得

证 根据 $x_{k+1}$ 的定义, $0$ 一定属于如下函数在 $x_{k+1}$ 点处的次微分

因为 $\phi$ 是可微的, 所以有

即

同理,

即

根据函数 $L$ 的结构, 有 $\partial_xL(x_{k+1},y_{k+1})=\partial f(x_{k+1})+\nabla_x Q(x_{k+1},y_{k+1})$ 和 $\partial_yL(x_{k+1},y_{k+1})=\nabla_y Q(x_{k+1},y_{k+1})+\partial g(y_{k+1})$. 因此, 由 (3.16) 式和 (3.17) 式可得

和

由

可得 (3.14) 式成立. 进而, 如果序列 $\{z_k\}_{k\in \mathbb{N}}$ 是有界的, 注意到 $\nabla Q$ 在有界子集上 Lipschitz 连续, 则存在 $M>0$ 使得

因此, 根据序列 $\{w_{k+1}\}_{k\in\mathbb{N}}$ 的定义有 (3.15) 式成立.

引理 3.3 设 $2(\alpha_1+\alpha_2)<\rho$ 且序列 $\{z_k\}_{k\in \mathbb{N}}$ 由算法 1 生成, 则如下结论成立

(1) 序列 $\{z_k\}_{k\in \mathbb{N}}$ 有界, 且集合 $\omega(z_k)$ 非空;

(2) 对任意 $\tilde{z}\in \omega(z_k)$ 及 $z_{k_j}\rightarrow \tilde{z}$($j\rightarrow\infty$), 当 $j\rightarrow\infty$ 时, 序列 $H(z_{k_j},z_{k_j-1},z_{k_j-2})\rightarrow H(\tilde{z},\tilde{z},\tilde{z})$ 且 $0\in\partial L(\tilde{z})$.

证 (1) 根据引理 3.1 和 $H(z_0,z_{-1},z_{-2})=L(z_0)$, 当 $k\geq 0$ 时, 有

显然整个序列 $\{z_k\}_{k\in\mathbb{N}}$ 是水平集 $\{z\in \mathbb{R}^l\times \mathbb{R}^m : \inf\limits_{z\in \mathbb{R}^l\times \mathbb{R}^m}L(z)\leq L(z) \leq L(z_0)\}$ 的子集. 由 $L$ 的强制性和 $\inf\limits_{z\in \mathbb{R}^l\times \mathbb{R}^m}L(z)>-\infty$ 可得序列 $\{z_k\}_{k\in\mathbb{N}}$ 有界, 故集合 $\omega(z_k)$ 非空.

(2) 对于任意 $\tilde{z}\in \omega(z_k)$ 和 $z_{k_j}\rightarrow \tilde{z}$ ($j\rightarrow\infty$), 下面证明 $L(z_{k_j})\rightarrow L(\tilde{z})$($j\rightarrow\infty$). 令 $\tilde{z}=(\tilde{x},\tilde{y})$, 则 $x_{k_j}\rightarrow \tilde{x}$ 且 $y_{k_j}\rightarrow \tilde{y}$ ($j\rightarrow\infty$). 由引理 3.1 (2) 可得

所以有 $\lim\limits_{k\rightarrow\infty}\|x_{k}-x_{k-1}\|_2=\lim\limits_{k\rightarrow\infty}\|y_{k}-y_{k-1}\|_2=0$. 根据 $x_{k}$ 的定义, 可得

则

令 $j\overset{}{\rightarrow} \infty$, 可得

根据 $f$ 的下半连续性可知

所以 $\lim\limits_{j\rightarrow\infty}f(x_{k_j})= f(\tilde{x})$. 同理可得$\lim\limits_{j\rightarrow\infty}g(y_{k_j})= g(\tilde{y})$, 因此

根据(3.20) 式和

有 $\lim\limits_{j\rightarrow\infty}H(z_{k_j},z_{k_j-1},z_{k_j-2})= L(\tilde{z})=H(\tilde{z},\tilde{z},\tilde{z})$ 成立. 由(3.18) 式和 (3.19) 式可得

其中

由于 $\nabla Q$ 在有界集上是 Lipschitz 连续的, 并且 $\nabla \phi_i$ ($i=1,2$) 也是 Lipschitz 连续的. 因此, $s_{k}\rightarrow 0$($k\rightarrow\infty$). 根据次微分 $\partial L$ 的闭性, 可得 $0\in \partial L(\tilde{z})$.

现在, 利用引理 2.2, 可以得到算法 1 生成的序列 $\{(x_k,y_k)\}_{k\in\mathbb{N}}$ 具有收敛性.

定理 3.1 设 $2(\alpha_1+\alpha_2)<\rho$ 且 $\{(x_k,y_k)\}_{k\in \mathbb{N}}$ 由算法 1 生成, 则由 (3.3) 式定义的函数 $H(u,v,w):\mathbb{R}^{3(l+m)}\rightarrow {(-\infty,+\infty]}$ 对于序列 $\{(z_{k+1}, z_k,z_{k-1})\}_{k\in \mathbb{N}}$ 满足假设2.1 (即满足条件 (H1), (H2) 和 (H3)). 此外, 如果 $H(u,v,w)$ 在序列 $\{(z_{k+1}, z_k,z_{k-1})\}_{k\in \mathbb{N}}$ 的聚点 $(z^\ast,z^\ast,z^\ast)$ 处具有 KŁ 性质, 则序列 $\{z_k\}_{k\in \mathbb{N}}$ 具有有限的长度, 即 $\sum\limits_{k=0}^{\infty}\|z_{k+1}-z_k\|_2<+\infty$. 并且, $z_k\rightarrow z^\ast$($k \rightarrow\infty$), $z^\ast$ 是 $L$ 的稳定点, $(z^\ast,z^\ast,z^\ast)$ 是 $H$ 的稳定点.

证 根据引理 2.2, 只需验证函数 $H(u,v,w)$ 对于序列 $\{(z_{k+1}, z_k,z_{k-1})\}_{k\in \mathbb{N}}$ 满足条件 (H1), (H2) 和 (H3). 由引理 3.1 (1) 可得条件 (H1) 成立. 根据引理3.2, 对 $k\in \mathbb{N}$, 有

其中 $w_{k+1}$ 由 (3.13) 式定义. 由引理 3.3(1) 可知, 序列 $\{z_k\}_{k\in\mathbb{N}}$ 是有界的. 令 $c=\max\{L_{\nabla\phi_1},$$L_{\nabla\phi_2}\}$, $d=M+L_2^+$, 不等式

成立. 根据 (3.15) 式有

于是取 $b=\sqrt{2}(c+d+\alpha_1+2\alpha_2)$ 时条件 (H2) 成立. 由引理 3.3(1) 知 $\omega(z_k)\neq\emptyset$, 因此存在子序列 $\{z_{k_j}\}_{j\in\mathbb{N}}\subseteq \{z_k\}_{k\in\mathbb{N}}$ 及 $\tilde{z}$, 使得当 $j\rightarrow\infty$ 时, $z_{k_j}\rightarrow \tilde{z}$. 根据引理 3.1(2), 当 $j\rightarrow\infty$ 时, $\triangle_{k_j}=\|z_{k_j}-z_{k_j-1}\|_2\rightarrow 0$. 令 $u_{k_j}=(z_{k_j}, z_{k_j-1},z_{k_j-2})$, $\tilde{u}=(\tilde{z},\tilde{z},\tilde{z})$, 则当 $j\rightarrow\infty$ 时, $u_{k_j}\rightarrow \tilde{u}$. 由引理 3.3(2) 可知

且 $0\in\partial L(\tilde{z})$. 所以条件 (H3) 成立.

例 4.1 稀疏非负矩阵分解问题. 给定一个矩阵 $A$, 非负矩阵分解 (NMF)^[36⇓-38] 的目标是将数据库 $A$ 分解成若干个稀疏基, 这样每个数据库都可以通过使用少量部分来近似. 即寻找一个分解 $A \approx XY$, 其中 $X \in \mathbb{R} ^{ n\times r}$, $Y \in \mathbb{R} ^{r\times d}$ 是非负的且 $X$ 是稀疏的. 为了刻画稀疏性, 此处使用 $l_0$ 稀疏约束^[39]. 因此, 稀疏非负矩阵分解问题可以表示为如下模型

其中 $X_i$ 表示 $X$ 的第 $i$ 列. 在 (4.1) 式中, $X$ 的稀疏性使用非凸的 $l_ 0$ 约束, 且将 $75\%$ 的元素限制为 0. 模型 (4.1)可以转换为非凸非光滑优化问题 (1.1), 其中 $Q(X,Y)=\frac{\lambda}{2}\left \| A-XY \right \| _{F}^{2}$, $f(X)=\iota_{X\ge0}(X)+\iota_{\left \| X_1\right \| _0\le sn}(X)+\cdots +\iota_{\left \| X_r \right \| _0\le sn}(X)$, $g(Y)=\iota_{Y\ge0}(Y)$, $\iota_C$ 是 $C$ 上的指示函数, $s$ 为稀疏度.

在数值实验中, 使用由人脸图像组成的标准人脸识别基准1: Yale-B 数据集和 ORL 数据集, 其中 Yale-B 数据集包含 2414 张大小为 $32 \times 32$ 的人脸裁剪图像, ORL 数据集包含 400 张大小为 $64 \times 64$ 的人脸图像, 见图1. 针对 Yale-B 数据集, 提取了 49 张稀疏基图像. 针对 ORL 数据集, 提取了 25 张稀疏基图像.

取实验参数 $\lambda=0.5$. 在算法1 中, 令 $\phi_1(X)=\frac{\mu_1 }{2} \left \| X\right \|_{2}^{2}$, $\phi_2(Y)=\frac{\mu_2 }{2} \left \|Y \right \|_{2}^{2}$, 其中 $\mu_1$ 和 $\mu_2$ 分别通过计算 $\lambda YY^T$ 和 $\lambda X^TX$ 在第 $k$ 次迭代时的最大特征值来得到. 在数值实验中, 比较邻近交替线性极小化算法 (PALM)(1.4), 一步惯性邻近交替线性极小化算法 (iPALM) (1.5), Gauss-Seidel 型邻近交替线性极小化算法 (GiPALM) (1.6) 和算法 1 求解问题(4.1) 的收敛速度. 令稀疏度 $s=0.25$. 下面给出惯性参数的选取方式

(1) PALM: $\alpha_{1k}=\beta _{1k}=\alpha_{2k}=\beta _{2k}=0$.

(2) iPALM、GiPALM: 固定惯性参数 $\alpha_{1k}=\beta _{1k}=\alpha_{2k}=\beta _{2k}=0.5$; FISTA 惯性参数 $\alpha_{1k}=\beta _{1k}=\alpha_{2k}=\beta _{2k}=\frac{k-1}{k+2}$.

(3) 算法 1 (TiBPALM): 固定惯性参数 $\alpha_{1k}=\beta _{1k}=0.2$, $\alpha_{2k}=\beta _{2k}=0.3$; FISTA 惯性参数 $\alpha_{1k}=\alpha_{2k}=\beta _{1k}=\beta _{2k}=\frac{k-1}{k+2}$.

结果分析: 当选取固定惯性参数时, 图2 和图4分别给出了使用不同算法得到的目标函数值在 Yale-B 数据集和 ORL 数据集下数值结果. 当选取 FISTA 惯性参数时, 图3 和图5 分别给出了使用不同算法得到的目标函数值在 Yale-B 数据集和 ORL 数据集下数值结果. 从这些图中可以看出, 在几乎相同的计算时间内, 所提出的算法 1 可以得到比其他三种算法略低的值.

将算法1 与 PALM、iPALM 和 GiPALM 在不同稀疏度设置 ($s$ 值) 下进行比较, 此时惯性参数采用 FISTA 选取方式. 稀疏基图像的结果如图6所示. 从图6 可以看出, $s$ 值越小, 四种算法得到的人脸图像显示的更明显, 有助于提高图像显现的泛化能力.

例 4.2 稀疏信号恢复问题. 假设 $x$ 是 $\mathbb{R }^{m}$ 中的未知向量 (一个信号), 给定测量矩阵 $A\in \mathbb{R }^{m\times n }$, 以及观测数据 $b\in \mathbb{R }^{m}$, 计划从观测数据 $b$ 中恢复稀疏信号 $x$ (即 $x$ 具有最少的非零元素), 使用 $l_0$ 稀疏约束. 因此, 稀疏信号恢复问题可以表示为如下的模型$\min_{x} {\rm } \left \| x \right \| _{0},$${\rm s.t.} \ Ax=b,$其中 $\left \| x \right \| _{0}$ 表示 $x$ 中非零元素的个数, 即 $l_0$ 范数. 实际计算中, 常将上式中的 $l_0$ 范数松弛到 $l_{1/2}$ 范数, 从而转化为如下非凸优化问题

其中参数 $\eta >0$, $\left \| x \right \| _{1/2}$ 是 $\mathbb{R }^{m}$ 的 $l_{1/2}$ 范数, 定义为 $\left \| x \right \| _{1/2} =( {\textstyle \sum\limits_{i=1}^{m}}\left | x_{i} \right | ^{1/2} )^{2}$. 下面将此问题转化为问题 (1.1).

通过引入辅助变量 $y\in \mathbb{R }^{m}$, 问题 (4.2) 可重新表述为

进一步转化为

其中 $\gamma$ 为惩罚参数. 令 $f(x)=\frac{1}{2} \left \| Ax-b \right \| _{2}^{2}$, $Q(x,y)=\frac{\gamma}{2}\left \| x-y \right \| _{2}^{2}$, $g(y)=\eta \left \| y \right \| _{1/2}^{1/2}$, 则问题 (4.3) 转化为非凸非光滑不可分优化问题 (1.1). 下面选择适当的 Bregman 距离, 利用算法 1 求解本例. 令 $\phi_1(x)= \langle x,Mx\rangle$, $\phi_2(y)=\frac{\lambda }{2} \left \| y\right \|_{2}^{2}$, 取 $M=\mu I- A^{T}A$ 时, $x$ 子问题为

由上式可知, $x$ 子问题有显式的表达式

$y$ 子问题为

对于任何 $\kappa >0$, $\mathcal{H}(\cdot,\kappa )$ 称为半收缩算子^[40], 定义如下

其中

并且 $\varphi (a_{i} )=$ arccos $\big( \frac{\kappa }{8} \big ( \frac{\left | a_{i} \right | }{3} \big )^{-3/2} \big )$.

参数选取: 设 $A$ 服从标准正态分布, 并对 $A$ 进行列单位化, 则 $\left \| A\right \|\le1$. 随机生成稀疏向量 $x$, 噪声向量 $\omega \sim N\left ( 0,10^{-3}I \right )$, 向量 $b=Ax+\omega$. 取正则化参数 $\eta=0.001\left \| A^{T}b \right \|_{\infty }$, 惩罚参数 $\gamma =0.2$. 根据引理 3.1, 取 $\alpha_1>0$, $\alpha_2>0$ 使得 $2(\alpha_1+\alpha_2)<\rho$, 其中 $\rho =\min\{\mu - \left \| A \right \| ^{2} -\gamma, \lambda -\gamma\}$, $\mu =2$, $\lambda =1.5$. 在算法 1 和两步惯性 Bregman 交替极小化算法 (TiBAM) 中, 惯性参数 $\alpha_{1k}=\alpha_{2k}=\beta _{1k}=\beta _{2k}=0.99\rho/4$; 在一步惯性 Bregman 邻近交替线性极小化算法 (iBPALM) 中, 惯性参数 $\alpha_{1k}=\beta _{1k}=0.99\rho/2$; Bregman 邻近交替线性极小化算法 (BPALM) 是算法 1 没有惯性外推的的特殊情况, 即 $\alpha_{1k}=\alpha_{2k}=\beta _{1k}=\beta _{2k}=0$. 将原点作为所有算法的初始点并设 $E_k=\|x_{k+1}-x_k\|+\|y_{k+1}-y_k\|<10^{-4}$为停止准则. 下面分别针对不同维度的矩阵 $A$, 如 $(n,m)=(40,200)$ 和 $(n,m)=(100,500)$, 将算法 1 与 TiBAM、iBPALM 和 BPALMA 进行比较.

结果分析: 表1 和表2 分别显示了维数 $(n,m)=(40,200)$ 和 $(n,m)=(100,500)$ 时的迭代次数、CPU 时间和 $x_{k}-y_k$ 的 2 范数. 显然, 算法 1 在解决上述问题时的迭代次数和时间方面都优于 TiBAM、iBPALM 和 BPALM 算法. 在图7 和图8 中, 针对不同的维数 $(n,m)=(40,200)$ 和 $(n,m)=(100,500)$, 左边的图片显示了无噪声 ($b = Ax$) 的误差函数的下降趋势, 右边的图片显示了有噪声 $(b=Ax+\omega)$ 的误差函数的下降趋势. 其数值结果显示了算法 1 的有效性.

为了给出算法 1 在不同 Bregman 距离下的数值结果, 下面介绍三种不同的 Bregman 距离

(1) 定义函数 $\varphi_1(x)=\mu\sum\limits_{i=1}^m x_i\ln x_i$, 其定义域为

值域为 $(-\infty,+\infty)$. 故

及 $\varphi_1$ 生成的 Bregman 距离 (Kullback-Leibler 距离) 是

(2) 定义函数 $\varphi_2(x)=-\mu\sum\limits_{i=1}^m \ln x_i$, 其定义域为

值域为 $(-\infty,+\infty)$. 故

及 $\varphi_2$ 生成的 Bregman 距离 (Itakura-Saito 距离) 是

(3) 定义函数 $\varphi_3(x)=\frac{\mu}{2}\|x\|^2$, 其定义域为 $\text{dom}\varphi_3=\mathbb{R}^m,$ 值域为 $[0,+\infty)$. 故 $\nabla \varphi_3(x)=x$ 及 $\varphi_3$ 生成的 Bregman 距离 (2 范数平方距离) 是

显然, $\varphi_i$ ($i=1,2,3$) 是 1-强凸的.

例 4.3 非凸二次分式规划问题

其中 $C=\left \{ x\in \mathbb{R}^m :1\le x_{i}\le 3,i=1,2,\cdots,m \right \}$, $M:\mathbb{R}^m\to \mathbb{R}^m$ 是有界线性算子, $a\in \mathbb{R}^m$, $b\in \mathbb{R}^m$, $c=-2$ 且 $d=20$. 由文献 [8] 知 $f$ 在开集 $E=\left \{ x\in \mathbb R^{m} :b^{T}x+d >0 \right \}$ 上是伪凸的. 如果 $C\subseteq E$, 那么 $f$ 是非凸的.

上述二次分式规划问题可以转化为非凸非光滑不可分优化问题 (1.1)

其中 $\iota_C$ 是 $C$ 上的指示函数. 由算法 1 可知 $x$ 子问题和 $y$ 子问题的迭代格式如下

在本例中, 取 $\alpha_{1k}=\beta_{1k}=0.2$, $\alpha_{2k}=\beta_{2k}=0.3$, $\gamma=10$, $\mu=36$. 使用不同的 Bregman 距离对算法 1 进行数值实验并设

为停止准则. 使用“算法 (ij)” 表示算法 1 中 $\phi_1(x)=\varphi_i(x)$ 和 $\phi_2(x)=\varphi_j(x)$$(1\leq i\leq 3, 1\leq j\leq 3)$. 对于上述的二次分式规划问题, 给出算法 1 在不同矩阵 $M$ 下的数值结果. 随机选择初始点并随机进行 30 次, 得到平均迭代次数和平均 CPU 时间. 算法1 在不同 Bregman 距离下的数值结果如表3 和表4 所示.

情形 1 取固定矩阵 $M\!=\!\begin{bmatrix} 5& -1& 2& 0& 2\\ -1& 6& -1& 3& 0\\ 2& -1& 3& 0& 1\\ 0& 3& 0& 5& 0\\ 2& 0& 1& 0&4 \end{bmatrix}$, 向量 $a=(1,2,-1,-2,1)^{T}$, $b=(1,0,-1,0,1)^{T}$, 在这种情况下, $C\subseteq E$. 对于不同的 Bregman 距离, 表3 中给出了一步惯性算法和两步惯性算法的数值结果, 其中一步惯性参数 $\alpha_{1k}=\beta_{1k}=0.5$.

结果分析: 可以看出, 在迭代次数和 CPU 时间方面, Kullback-Leibler 距离和 Itakura-Saito 距离比 2 范数平方距离具有计算优势. 对于一步惯性算法, 计算结果表明, 算法 (23) ($\phi_1(x)=\varphi_2(x)$, $\phi_2(x)=\varphi_3(x)$) 求解二次分式规划问题的性能最好, 算法 (33) ($\phi_1(x)=\varphi_3(x)$, $\phi_2(x)=\varphi_3(x)$) 的性能最差. 同样地, 对于两步惯性算法, 计算结果表明, 算法 (23) ($\phi_1(x)=\varphi_2(x)$, $\phi_2(x)=\varphi_3(x)$) 求解二次分式规划问题的性能最好, 算法 (33) ($\phi_1(x)=\varphi_3(x)$, $\phi_2(x)=\varphi_3(x)$) 的性能最差.

情形 2 随机选择矩阵 $M\in \mathbb R^{m\times m}$ 和向量 $a\in \mathbb R^{m}, b\in \mathbb R^{m}$. 当 $m=5,20,50,100$ 时, 表4 给出了算法 1 在不同 Bregman 距离下的数值结果.

结果分析: 表4 中数值结果显示, 当矩阵 $M$ 的维数较低时, 算法(23) ($\phi_1(x)=\varphi_2(x)$,$\phi_2(x)=\varphi_3(x)$) 的数值结果最好. 当矩阵 $M$ 的维数略高时, 算法(12) ($\phi_1(x)=\varphi_1(x)$, $\phi_2(x)=\varphi_2(x)$) 数值结果最好.

针对非凸非光滑不可分优化问题, 本文基于邻近交替线性极小化算法, 结合惯性外推技术和 Bregman 距离提出了两步惯性 Bregman 邻近交替线性极小化算法. 在目标函数满足 Kurdyka-Łojasiewicz 不等式且参数满足合理条件的假设下, 构造适当的效益函数, 得到算法生成的序列全局收敛到稳定点. 最后, 对稀疏非负矩阵分解、稀疏信号恢复和二次分式规划问题进行了数值实验, 并选择适当的 Bregman 距离使稀疏信号恢复问题的子问题有显示表达式, 还应用不同的 Bregman 距离来求解二次分式规划问题. 数值结果表明了所提出算法的有效性.