求解非凸优化问题的带惯性项Majorized Bregman交替方向乘子法

Majorized Bregman Alternating Direction Method of Multipliers with Inertia Terms for Solving Nonconvex Optimisation Problems

摘要: 对非凸两分块优化问题，提出一种带惯性的Majorized Bregman交替方向乘子法。该算法在迭代中结合了目标函数的极大化线性技术和Bregman距离来简化子问题的求解，同时通过引入惯性项加快收敛效果。在适当条件下证明了算法的收敛性质。初步数值实验结果表明该算法是有效的。

Abstract: A Majorized Bregman alternating direction method of multipliers (Bregman-ADMM) with inertial terms is proposed for nonconvex two-block optimization problems. The algorithm combines a linearization technique for the objective function and the Bregman distance in each iteration to simplify subproblem solutions, while accelerating the convergence rate through inertial terms. The convergence of the algorithm is established under appropriate conditions. Preliminary numerical experiments demonstrate the effectiveness of the proposed algorithm.

1. 引言

本文考虑如下带线性等式约束的两块可分结构非凸优化问题：

$\begin{array}{l}\min f\left(x\right)+g\left(y\right)\\ s.t.Ax-By=0,\end{array}$ (1)

其中$f:R^{s_1}\to R$ 是梯度Lipschitz连续可微的凸函数，$g:R^{s_2}\to R\cup \left\{+\infty \right\}$ 是适当下半连续函数，$A\in R^{m\times s_1},B\in R^{m\times s_2}$ 。问题(1)广泛应用于信号处理[1]、图像处理[2]、机器学习[3]和经济调度[4]等领域，其中$f$ 通常是一个(二次或逻辑)损失函数，$g$ 通常是一个正则项，如$l_1$ 范数或$l_{1/2}$ 拟范数。问题(1)的增广拉格朗日函数定义为

$L_{\beta }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)+\langle \lambda ,Ax-By\rangle +\frac{\beta }{2}{\Vert Ax-By\Vert }^2,$

其中$\lambda \in R^m$ 是拉格朗日乘子，$\beta >0$ 是一个惩罚参数。

求解问题(1)的经典ADMM的第$k+1$ 步迭代格式为

$\{\begin{array}{l}{y}^{k+1}=\underset{y}{\arg \min }{L}_{\beta }\left(x^k,y,{\lambda }^k\right)\\ x^{k+1}=\underset{x}{\arg \min }{L}_{\beta }\left(x,y^{k+1},{\lambda }^k\right)\\ {\lambda }^{k+1}={\lambda }^k+\beta \left(A{x}^{k+1}-B{y}^{k+1}\right).\end{array}$ (2)

尽管ADMM在解决凸优化问题方面得到了广泛的应用，但对于非凸优化问题，ADMM的收敛性分析仍值得研究，目前一些学者已经得到了部分研究成果。如Deng Zhao等[5]针对非凸两分块优化问题，在增广拉格朗日函数满足KL性质且罚参数大于某阈值的条件下，证明了ADMM的收敛性。在此基础上，Wang Y等[6]进一步拓展了ADMM的理论框架，他们放松了文献[5]中对矩阵列满秩的严格限制，并在目标函数和系数矩阵满足一些常见约束条件下，证明了ADMM的全局收敛性。

一般将ADMM直接应用于非凸优化问题时，其收敛性不能保证，由此学者们对原始ADMM方法做了改进研究，如线性化技术、松弛技巧等。为了有利于迭代子问题的求解，Wang F等[7]针对非凸两分块优化问题(1)引入Bregman距离改善子问题目标函数的结构，提出Bregman ADMM (BADMM)算法。其过程如下

$\{\begin{array}{l}{y}^{k+1}=\underset{y}{\arg \min }\left\{L_{\beta }\left(x^k,y,{\lambda }^k\right)+D_{T_1}\left(y,y^k\right)\right\}\\ x^{k+1}=\underset{x}{\arg \min }\left\{L_{\beta }\left(x,y^{k+1},{\lambda }^k\right)+D_{T_2}\left(x,x^k\right)\right\}\\ {\lambda }^{k+1}={\lambda }^k+\beta \left(A{x}^{k+1}-B{y}^{k+1}\right)\end{array}$

其中$T_i\left(i=1,2\right)$ 是凸可微函数，其Bregman距离$D_{T_i}$ 定义为：

$D_{T_i}\left(x,y\right)=T_i\left(x\right)-T_i\left(y\right)-\langle \nabla T_i\left(y\right),x-y\rangle ,\forall x\in dom{T}_i,y\in \mathrm{int}dom{T}_i\left(i=1,2\right)$ .

比如当$T_i\left(x\right)=x^{\text{T}}Cx$ ，其中$C$ 是半正定矩阵时有$D_{T_i}\left(x_1,x_2\right)={\left(x_1-x_2\right)}^{\text{T}}C\left(x_1-x_2\right)$ 。

在此基础上，陈建华等[8]的Majorized Bregman ADMM(MBADMM)算法针对非凸两分块优化问题，对目标函数中的光滑函数项进行了极大化线性处理，由于目标函数中的$f$ 是光滑凸函数，这意味着存在一个半正定矩阵${\sum }_f$ 使得对任意$x,x^{\prime }\in R^{s_1}$ ，都有：$f\left(x\right)\ge f\left(x^{\prime }\right)+\langle \nabla f\left(x^{\prime }\right),x-x^{\prime }\rangle +\frac{1}{2}{\Vert x-x^{\prime }\Vert }_{{\sum }_f}^2$ ，又由于函数$f$ 的梯度是Lipschitz连续的，所以可以找到一个半正定矩阵${\widehat{\sum }}_f$ ，且${\widehat{\sum }}_f\underset{\_}{\succ }{\sum }_f$ ，使得对任意的$x,x^{\prime }\in R^{s_1}$ 都有

$f\left(x\right)\le \widehat{f}\left(x,x^{\prime }\right):=f\left(x^{\prime }\right)+\langle \nabla f\left(x^{\prime }\right),x-x^{\prime }\rangle +\frac{1}{2}{\Vert x-x^{\prime }\Vert }_{{\widehat{\sum }}_f}^2$ .

于是针对问题(1)，文献[8]构建Majorized增广拉格朗日函数为

${\widehat{L}}_{\beta }\left(x,y,\lambda ,x^{\prime }\right)=\widehat{f}\left(x,x^{\prime }\right)+g\left(y\right)+{\lambda }^{\text{T}}\left(Ax-By\right)+\frac{\beta }{2}{\Vert Ax-By\Vert }^2.$ (3)

相应的MBADMM算法迭代过程如下：

$\{\begin{array}{l}{y}^{k+1}=\underset{y}{\arg \min }\left\{{\widehat{L}}_{\beta }\left(x^k,y,{\lambda }^k,x^k\right)+D_{T_1}\left(y,y^k\right)\right\}\\ x^{k+1}=\underset{x}{\arg \min }\left\{{\widehat{L}}_{\beta }\left(x,y^{k+1},{\lambda }^k,x^k\right)+D_{T_2}\left(x,x^k\right)\right\}\\ {\lambda }^{k+1}={\lambda }^k+\beta \left(A{x}^{k+1}-B{y}^{k+1}\right)\end{array}$ (4)

另一方面，注意到在迭代算法中，增加惯性力或惯性项可以在产生新方向时充分利用部分旧方向的信息，从而对算法起到加速的作用[9]-[11]，Xu J等[12]提出带惯性项的Bregman Generalized ADMM (IBGADMM)算法。针对线性约束$Ax+By=b$ 非凸优化问题，[12]结合惯性步和Bregman距离思想给出迭代过程

$\{\begin{array}{l}{x}^{k+1}\in \underset{x}{\arg \min }\{L_{\beta }\left(x,y^k,{\lambda }^k\right)+D_{T_2}\left(x,x^k\right)+{\theta }_k\langle x,x^{k-1}-x^k\rangle \}\\ x_{ad}^{k+1}=\alpha A{x}^{k+1}+\left(1-\alpha \right)\left(b-B{y}^k\right)\\ y^{k+1}\in \underset{y}{\arg \min }\{g\left(y\right)-\langle {\lambda }^k,B{y}^k\rangle +\frac{\beta }{2}{\Vert x_{ad}^{k+1}+By-b\Vert }^2+D_{T_1}\left(y,y^k\right)+{\rho }_k\langle y,y^{k-1}-y^k\rangle \}\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(x_{ad}^{k+1}+B{y}^{k+1}-b\right),\end{array}$

并建立了算法的子序列收敛性和全局收敛性。

受上述文献的启发，对目标函数中的光滑函数项进行极大化线性处理，可以简化关于该函数子问题的求解，针对目标函数加入Bregman距离可以提升算法在求解非凸优化问题时的性能和收敛性，引入惯性项也可以缩短收敛所需时间。本文提出了针对非凸优化问题(1)的带惯性项Majorized-Bregman-ADMM (IMBADMM)算法，该算法涵盖了ADMM和MBADMM作为其特殊情形。与文献[13]有所区别的是，本文在两个子问题中引入了惯性力[9]-[11]。此外，效益函数的充分递减特性并不需要假设$A$ 或$B$ 是满秩。在IMBADMM生成的序列具有有界性且效益函数满足KL性质的条件下，我们证明了IMBADMM的子序列收敛性和全局收敛性。最后运用所提出的IMBADMM算法对稀疏逻辑回归问题进行了数值实验比较。

2. 预备知识

2.1. 基本概念与结论

对任意$x,y\in R^n$ ，定义它们的内积为$\langle x,y\rangle =x^{\text{T}}y$ ，定义$x$ 的$G$ 范数${\Vert x\Vert }_G=\sqrt{x^{\text{T}}Gx}$ ，其中$G\underset{\_}{\succ }0\left(\succ 0\right)$ 表明$G$ 是半正定(正定)矩阵。${\lambda }_{\max }\left(G\right)$ 表示矩阵$G$ 的最大特征值。

任意点$y$ 到集合$S$ 的距离定义如下

$dist\left(y,S\right)=\{\begin{array}{l}\underset{x\in S}{\inf }\Vert x-y\Vert ,S\ne \varnothing \\ +\infty ,S=\varnothing .\end{array}$

定义1 ([14]，引理2.2) 称可微函数$f\left(x\right)$ 是$\mu$ -强凸函数，若如下不等式成立：

$f\left(y\right)\ge f\left(x\right)+\langle \nabla f\left(x\right),y-x\rangle +\frac{\mu }{2}{\Vert y-x\Vert }^2,\forall x,y\in domf.$

关于Bregman距离，有下述性质。

性质1 ([15]，命题2.3) 令$T:R^n\to R$ 是可微凸函数，$D_T\left(x,y\right)$ 是与它相关的Bregman距离，则

1) 对任意的$x,y\in R^n$ ，有：$D_T\left(x,y\right)\ge 0,D_T\left(x,x\right)=0$ ；

2) 对于固定的$y$ ，$D_T\left(\cdot ,y\right)$ 是凸的；

3) 对于任意$x,y\in R^n$ ，$D_T\left(x,y\right)\ge \frac{\mu }{2}{\Vert x-y\Vert }^2$ ，其中$\mu$ 是$T$ 的强凸系数；

4) 如果$\nabla T$ 是Lipschitz连续的，且其Lipschitz常数为$l_T$ ，则对任意$x,y\in R^n$ ，有

$\nabla T\left(x,y\right)\le \frac{l_T}{2}{\Vert x-y\Vert }^2$ .

定义2 ([14]，定义8.5]) 定义满足以下条件的凹连续函数$\phi :\left[0,\eta \right)\to R_{+}$ 的集合为${\Phi }_{\eta }$ 函数类：

1) $\phi \left(0\right)=0$ ；

2) $\phi$ 在$\left(0,\eta \right)$ 内连续可微，在点$0$ 处连续；

3) 对任意$s\in \left(0,\eta \right)$ ，都有${\phi }^{\prime }\left(s\right)>0$ 。

根据上面的定义我们可以引入KL性质。

定义3 ([14]，定义8.6) (KL性质) 设$g:R^{s_2}\to R\cup \left\{+\infty \right\}$ 为适当下半连续函数。

1) 称函数$g$ 在给定点$\overline{y}\in dom\partial g\underset{\_}{\underset{\_}{de\text{f}}}\left\{y|\partial g\left(y\right)\ne \varnothing \right\}$处具有KL性质，若存在$\eta \in \left(0,+\infty \right]$ ，$\overline{y}$ 的一个邻域$U$ 及函数$\phi \in {\Phi }_{\eta }$ ，使得对

$\forall y\in U\cap \left[g\left(\overline{y}\right)<g<g\left(\overline{y}\right)+\eta \right]$ ,

有以下不等式成立：

${\phi }^{\prime }\left(g\left(y\right)-g\left(\overline{y}\right)\right)dist\left(0,\partial g\left(y\right)\right)\ge 1$ .

2) 若$g$ 在$dom\partial g$ 上处处都满足KL性质，则称$g$ 是一个KL函数。

性质2 ([14]，引理8.4) (一致KL性质) 设$\Omega$ 为紧集，$g:R^{s_2}\to R\cup \left\{+\infty \right\}$ 为适当下半连续函数，在$\Omega$ 上为常数且在$\Omega$ 的每个点处都满足KL性质，则存在$\epsilon >0,\eta >0,\phi \in {\Phi }_{\eta }$ ，使得对任意$\overline{y}\in \Omega$ 和所有如下集合中的$y$ ：

$y\in$ $\left\{y\in R^{s_2}:dist\left(y,\Omega \right)<\epsilon \right\}\cap \left[g\left(\overline{y}\right)<g<g\left(\overline{y}\right)+\eta \right]$ ,

有

${\phi }^{\prime }\left(g\left(y\right)-g\left(\overline{y}\right)\right)dist\left(0,\partial g\left(y\right)\right)\ge 1$ .

性质3 ([16]，引理A.2) 设$A\in R^{m\times s_1}$ 是一个非零矩阵，${\mu }_{A^{\text{T}}}$ 表示$A^{\text{T}}A$ 的最小正特征值，${{\rm P}}_A$ 是到$\mathrm{Im}\left(A\right)=\left\{y|y=Ax,x\in R^{s_1}\right\}$ 的欧几里得投影，则有

$\Vert {{\rm P}}_A\left(u\right)\Vert \le \frac{1}{\sqrt{{\mu }_{A^{\text{T}}}}}\Vert A^{\text{T}}u\Vert ,\forall u\in R^{s_1}$ .

2.2. 主要结论与论文结构

本文主要贡献集中在第3部分和第4部分，分别给出新的算法及其收敛性证明和数值实验。

第3部分提出求解非凸优化问题的带惯性项Majorized Bregman ADMM (IMBADMM)算法，针对两个子问题，在每一步迭代中引入惯性力，在保证算法收敛性的前提下，有效地提高了算法的运算速度。在较弱的条件下，证明了算法的全局收敛性。

第4部分我们将IMBADMM算法应用到稀疏逻辑回归问题中，并分别与MBADMM、ADMM、SGD和LBADMM算法进行比较，数值实验都表明了算法的有效性。

最后，在第5部分给出本文总结。

3. 求解非凸优化问题的带惯性Majorized Bregman ADMM算法

对优化问题(1)，我们先给出带惯性项的Majorized Bregman ADMM算法，再讨论该算法的收敛性。

3.1. IMBADMM算法描述

算法1：带惯性项的Majorized Bregman ADMM(IMBADMM)算法

输入：$A\in R^{m\times s_1},B\in R^{m\times s_2},\lambda >0$ ，${\rho }_0>0,{\theta }_0>0,\rho >0,\theta >0$ ，$eps>0$ ， $\text{maxiter}>0$ ，选取合适的凸可微函数$T_1,T_2$ 用于构造Bregman距离； 初始化：$x^{-1}=x^0=zeros\left(n,1\right),y^{-1}=y^0=zeros\left(n,1\right),{\lambda }^0=zeros\left(n,1\right)$ ；令$k:=0$ 。 步1：更新参数，选取适当${\rho }_k$ 和${\theta }_k$ 满足$0\le {\rho }_k\le \rho ,0\le {\theta }_k\le \theta$ ； 步2：计算 $y^{k+1}\in \underset{y}{\arg \min }\left\{{\widehat{L}}_{\beta }\left(x^k,y,{\lambda }^k,x^k\right)+D_{T_1}\left(y,y^k\right)+{\rho }_k\langle y,y^{k-1}-y^k\rangle \right\};$ (5a) 步3：固定其他，计算 $x^{k+1}=\underset{x}{\arg \min }\left\{{\widehat{L}}_{\beta }\left(x,y^{k+1},{\lambda }^k,x^k\right)+D_{T_2}\left(x,x^k\right)+{\theta }_k\langle x,x^{k-1}-x^k\rangle \right\};$ (5b) 步4：更新乘子 ${\lambda }^{k+1}={\lambda }^k+\beta \left(A{x}^{k+1}-B{y}^{k+1}\right);$ (5c) 步5：若$\frac{\Vert x^{k+1}-x^k\Vert }{\max \left\{\Vert x^k\Vert ,1\right\}}\le eps$ ，则停止迭代，令$y=y^{k+1},x=x^{k+1},\lambda ={\lambda }^{k+1}$ ，输出$y,x$ ， $\lambda$ ；否则令$k：=k+1$ ，转步1。

其中$T_1$ ，$T_2$ 是两个可微凸函数，$D_{T_1}\left(y,y^k\right),D_{T_2}\left(x,x^k\right)$ 是Bregman距离，${\rho }_k\langle y,y^{k-1}-y^k\rangle$ ，${\theta }_k\langle x,x^{k-1}-x^k\rangle$ 为惯性项。

3.2. 收敛性分析

在分析收敛性之前，我们需要如下假设。

假设1 1) $A\ne 0,\mathrm{Im}B\subset \mathrm{Im}A$ ；

2) $f:R^{s_1}\to R$ 是连续可微凸函数，$\nabla f$ 是$l_f$ -Lipschitz连续的，且$\Vert {\nabla }^{2}f\left(x\right)\Vert$ 有界，$g:R^{s_2}\to R\cup \left(+\infty \right)$ 是适当下半连续函数；

3) 构造Bregman距离函数$T_i\left(i=1,2\right)$ 是${\mu }_i$ -强凸的，且$\nabla T_i$ 是$l_{T_i}$ -Lipschitz连续的，${\mu }_1-2\rho >0$ 且${\mu }_2>6\left(\frac{{\left(l_f+l_{T_2}+{\lambda }_{\max }+\theta \right)}^2+{\theta }^2+{\left(l_{T_2}+{\lambda }_{\max }\right)}^2}{\beta {\mu }_{A^{\text{T}}}}+\frac{\theta }{3}\right)+{\lambda }_{\max }+2l_f$ ，其中${\mu }_{A^{\text{T}}}$ 是矩阵$A^{T}A$ 的最小严格正特征值，${\lambda }_{\max }$ 是矩阵${\widehat{\sum }}_f$ 的最大特征值。

为了简化表达，记$z^k=\left(x^k,y^k,{\lambda }^k\right)$ ，${\widehat{L}}_{\beta }(\cdot )$ 的临界点$z^{\ast }=\left(x^{\ast },y^{\ast },{\lambda }^{\ast }\right)$ ，

$\Delta x^k=x^k-x^{k-1},\Delta y^k=y^k-y^{k-1},\Delta {\lambda }^k={\lambda }^k-{\lambda }^{k-1}$ ,

${\widehat{z}}^k=\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1},x^{k-1},x^{k-2}\right).$

引理1 若假设1成立，令$\left\{z^k\right\}$ 是由IMBADMM算法生成的序列，则对于所有$k\in N$ ，有

$\Vert \Delta {\lambda }^{k+1}\Vert \le \frac{1}{\sqrt{{\mu }_{A^T}}}\left(\left(l_f+l_{T_2}+{\lambda }_{\max }+{\theta }_k\right)\Vert \Delta x^k\Vert +\left(l_{T_2}+{\lambda }_{\max }\right)\Vert \Delta x^{k+1}\Vert +{\theta }_{k-1}\Vert \Delta x^{k-1}\Vert \right).$ (6)

对IMBADMM算法的收敛性分析，构造效益函数

$\widehat{L}\left(x,y,\lambda ,x^{\prime },\widehat{y},\widehat{x},\overline{x}\right)={\widehat{L}}_{\beta }\left(x,y,\lambda ,x^{\prime }\right)+\frac{\rho }{2}{\Vert y-\widehat{y}\Vert }^2+n_1{\Vert x-\widehat{x}\Vert }^2+n_2{\Vert \widehat{x}-\overline{x}\Vert }^2$ ,

$\widehat{L}\left({\widehat{z}}^k\right)={\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^{k-1}\right)+\frac{\rho }{2}{\Vert \Delta y^k\Vert }^2+n_1{\Vert \Delta x^k\Vert }^2+n_2{\Vert \Delta x^{k-1}\Vert }^2$ , (7)

其中$n_1=\frac{3{\left(l_f+l_{T_2}+{\lambda }_{\max }+\theta \right)}^2}{\beta {\mu }_{A^{\text{T}}}}+\frac{\theta +{\lambda }_{\max }+2l_f}{2}+\frac{3{\theta }^2}{\beta {\mu }_{A^{\text{T}}}},n_2=\frac{3{\theta }^2}{\beta {\mu }_{A^{\text{T}}}}$ 。

以下所述的充分下降性质将在我们的收敛性分析中占据关键地位，为了分析$\left\{\widehat{L}\left({\widehat{z}}^k\right)\right\}$ 的单调性，我们记

$\{\begin{array}{l}{\kappa }_1:={\kappa }_1\left({\mu }_1,\rho \right)=\frac{{\mu }_1-2\rho }{2}\underset{}{}\underset{}{}\underset{}{}\underset{}{}\underset{}{}\underset{}{}(8\text{a})\\ {\kappa }_2:={\kappa }_2\left({\mu }_2,\beta ,\theta \right)=\frac{{\mu }_2-{\lambda }_{\max }-2l_f}{2}-3\left(\frac{{\left(l_f+l_{T_2}+{\lambda }_{\max }+\theta \right)}^2+{\theta }^2+{\left(l_{T_2}+{\lambda }_{\max }\right)}^2}{\beta {\mu }_{A^{\text{T}}}}+\frac{\theta }{3}\right)\text{. }\underset{}{}\underset{}{}\underset{}{}\underset{}{}\underset{}{}\left(8\text{b}\right)\end{array}$

证明：因为${\lambda }^{k+1}-{\lambda }^k=\beta \left(A{x}^{k+1}-B{y}^{k+1}\right)\in \mathrm{Im}A$ ，所以$\Delta {\lambda }^{k+1}={{\rm P}}_A\left(\Delta {\lambda }^{k+1}\right)$ ，由性质3得

$\Vert {{\rm P}}_A\left(\Delta {\lambda }^{k+1}\right)\Vert \le \frac{1}{\sqrt{{\mu }_{A^T}}}\Vert A^{\text{T}}\Delta {\lambda }^{k+1}\Vert$ 。

根据(5b)式的最优性条件得

$0=\nabla f\left(x^k\right)+{\widehat{\sum }}_f\left(x^{k+1}-x^k\right)+A^{\text{T}}{\lambda }^{k+1}+\nabla T_2\left(x^{k+1}\right)-\nabla T_2\left(x^k\right)+{\theta }_k\left(x^{k-1}-x^k\right)，$ (9a)

(9a)式移项可得

$A^{\text{T}}{\lambda }^{k+1}=-\nabla f\left(x^{k+1}\right)-{\widehat{\sum }}_f\left(x^{k+1}-x^k\right)-\nabla T_2\left(x^{k+1}\right)+\nabla T_2\left(x^k\right)-{\theta }_k\left(x^{k-1}-x^k\right)$ (9b)

令$k=k-1$ ，有

$A^{\text{T}}{\lambda }^k=-\nabla f\left(x^k\right)-{\widehat{\sum }}_f\left(x^k-x^{k-1}\right)-\nabla T_2\left(x^k\right)+\nabla T_2\left(x^{k-1}\right)-{\theta }_k\left(x^{k-2}-x^{k-1}\right)$ (9c)

(9b)和(9c)式相减可得

$\begin{array}{l}{A}^{\text{T}}\left({\lambda }^{k+1}-{\lambda }^k\right)=-\left(\nabla f\left(x^k\right)-\nabla f\left(x^{k-1}\right)\right)-{\widehat{\sum }}_f\left[\left(x^{k+1}-x^k\right)-\left(x^k-x^{k-1}\right)\right]\\ -\left[\nabla T_2\left(x^{k+1}\right)-\nabla T_2\left(x^k\right)\right]+\left[\nabla T_2\left(x^k\right)-\nabla T_2\left(x^{k-1}\right)\right]\\ -{\theta }_k\left(x^{k-1}-x^k\right)+{\theta }_{k-1}\left(x^{k-2}-x^{k-1}\right)\end{array}$

由于$\nabla f$ 是$l_f$ -Lipschitz连续的，$\nabla T_2$ 是$l_{T_2}$ -Lipschitz连续的，且${\lambda }_{\max }$ 是矩阵${\widehat{\sum }}_f$ 的最大特征值，则

$\begin{array}{l}\Vert A^{\text{T}}\Delta {\lambda }^{k+1}\Vert \le l_f\Vert \Delta x^k\Vert +{\lambda }_{\max }\Vert \Delta x^{k+1}+\Delta x^k\Vert +l_{T_2}\Vert \Delta x^{k+1}\Vert +l_{T_2}\Vert \Delta x^k\Vert +{\theta }_k\Vert \Delta x^k\Vert +{\theta }_{k-1}\Vert \Delta x^{k-1}\Vert \\ =\left(l_f+l_{T_2}+{\lambda }_{\max }+{\theta }_k\right)\Vert \Delta x^k\Vert +\left(l_{T_2}+{\lambda }_{\max }\right)\Vert \Delta x^{k+1}\Vert +{\theta }_{k-1}\Vert \Delta x^{k-1}\Vert \end{array}$

上述不等式两边乘$\frac{1}{\sqrt{{\mu }_{A^T}}}$ 得

$\Vert {{\rm P}}_A\left(\Delta {\lambda }^{k+1}\right)\Vert =\Vert \Delta {\lambda }^{k+1}\Vert \le \frac{1}{\sqrt{{\mu }_{A^{\text{T}}}}}\left(\left(l_f+l_{T_2}+{\lambda }_{\max }+{\theta }_k\right)\Vert \Delta x^k\Vert +\left(l_{T_2}+{\lambda }_{\max }\right)\Vert \Delta x^{k+1}\Vert +{\theta }_{k-1}\Vert \Delta x^{k-1}\Vert \right).$

引理2 若假设1成立，令$\left\{z^k\right\}$ 是由IMBADMM算法生成的序列，那么以下结论成立：

1) 对于所有$k\in N$ ，有$\widehat{L}\left({\widehat{z}}^{k+1}\right)\le \widehat{L}\left({\widehat{z}}^k\right)-{\kappa }_1{\Vert \Delta y^{k+1}\Vert }^2-{\kappa }_2{\Vert \Delta x^{k+1}\Vert }^2$ ； (10)

2) 如果$\left\{z^k\right\}$ 是有界的，则${\displaystyle \sum _{k=0}^{+\infty }{\Vert z^{k+1}-z^k\Vert }^2}$ 。

证明：

1) (充分下降性质)

由于$y^{k+1}$ 是(5a)式的最优解，所以

$\begin{array}{l}{\widehat{L}}_{\beta }\left(x^k,y^{k+1},{\lambda }^k,x^k\right)-{\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^k\right)\\ \le -D_{T_1}\left(y^{k+1},y^k\right)+{\rho }_k\langle y^k-y^{k+1},y^{k-1}-y^k\rangle \\ \le \frac{{\rho }_k-{\mu }_1}{2}{\Vert \Delta y^{k+1}\Vert }^2+\frac{{\rho }_k}{2}{\Vert \Delta y^k\Vert }^2,\end{array}$ (11)

其中第2个不等式根据性质1的3)得出，由于$x^{k+1}$ 是(5b)式的最优解，故有

$\begin{array}{l}\widehat{f}\left(x^{k+1},x^k\right)+\langle {\lambda }^k,A{x}^{k+1}\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}-B{y}^{k+1}\Vert }^2+D_{T_2}\left(x^{k+1},x^k\right)+{\theta }_k\langle x^{k+1},x^{k-1}-x^k\rangle \\ \le \widehat{f}\left(x^k,x^k\right)+\langle {\lambda }^k,A{x}^k\rangle +\frac{\beta }{2}{\Vert A{x}^k-B{y}^{k+1}\Vert }^2+{\theta }_k\langle x^k,x^{k-1}-x^k\rangle ,\end{array}$

再利用${\Vert a-b\Vert }^2-{\Vert a\Vert }^2=-2\langle a,b\rangle +{\Vert b\Vert }^2$ 和性质1的3)，可推出

$\begin{array}{l}\widehat{f}\left(x^{k+1},x^k\right)-\widehat{f}\left(x^k,x^k\right)+\langle {\lambda }^k,A\Delta x^{k+1}\rangle \\ \le -\beta \langle A{x}^{k+1}-B{y}^{k+1},A\Delta x^{k+1}\rangle +\frac{\beta }{2}{\Vert A\Delta x^{k+1}\Vert }^2+\frac{{\theta }_k-{\mu }_2}{2}{\Vert \Delta x^{k+1}\Vert }^2+\frac{{\theta }_k}{2}{\Vert \Delta x^k\Vert }^2,\end{array}$ (12)

根据Majorized增广拉格朗日函数${\widehat{L}}_{\beta }(\cdot )$ 的定义得

${\widehat{L}}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k,x^k\right)-{\widehat{L}}_{\beta }\left(x^k,y^{k+1},{\lambda }^k,x^k\right)\stackrel{\left(12\right)}{\le }\frac{{\theta }_k}{2}{\Vert \Delta x^k\Vert }^2+\frac{{\theta }_k-{\mu }_2}{2}{\Vert \Delta x^{k+1}\Vert }^2,$ (13)

根据${\widehat{L}}_{\beta }(\cdot )$ 的定义及引理1，得

$\begin{array}{l}{\widehat{L}}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1},x^k\right)-{\widehat{L}}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k,x^k\right)\\ \le \frac{3}{\beta {\mu }_{A^T}}\left({\left(l_f+l_{T_2}+{\lambda }_{\max }+{\theta }_k\right)}^2{\Vert \Delta x^k\Vert }^2+{\left(l_{T_2}+{\lambda }_{\max }\right)}^2{\Vert \Delta x^{k+1}\Vert }^2+{\theta }_{k-1}^2{\Vert \Delta x^{k-1}\Vert }^2\right),\end{array}$ (14)

根据${\widehat{L}}_{\beta }(\cdot )$ 的定义及拉格朗日中值定理，得

${\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^k\right)-{\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^{k-1}\right)\le \left(l_f+\frac{{\lambda }_{\max }}{2}\right){\Vert \Delta x^k\Vert }^2,$ (15)

由(11)、(13)、(14)、(15)式相加可得

$\begin{array}{l}{\widehat{L}}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1},x^k\right)-{\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^{k-1}\right)\\ \le \frac{\rho -{\mu }_1}{2}{\Vert \Delta y^{k+1}\Vert }^2+\frac{\rho }{2}{\Vert \Delta y^k\Vert }^2+\left(\frac{3{\left(l_{T_2}+{\lambda }_{\max }\right)}^2}{\beta {\mu }_{A^{\text{T}}}}+\frac{\theta -{\mu }_2}{2}\right){\Vert \Delta x^{k+1}\Vert }^2\\ +\left(\frac{3{\left(l_f+l_{T_2}+{\lambda }_{\max }+\theta \right)}^2}{\beta {\mu }_{A^{\text{T}}}}+\frac{\theta +{\lambda }_{\max }+2l_f}{2}\right){\Vert \Delta x^k\Vert }^2+\frac{3{\theta }^2}{\beta {\mu }_{A^{\text{T}}}}{\Vert \Delta x^{k-1}\Vert }^2,\end{array}$ (16)

由算法过程可知$0\le {\rho }_k\le \rho$ 和$0\le {\theta }_k\le \theta$ ，其中最后一个不等式由此得出。

根据(16)式，得

$\begin{array}{l}{\widehat{L}}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1},x^k\right)+\frac{\rho }{2}{\Vert \Delta y^{k+1}\Vert }^2+n_1{\Vert \Delta x^{k+1}\Vert }^2+n_2{\Vert \Delta x^k\Vert }^2\\ \le {\widehat{L}}_{\beta }\left(x^k,y^k,{\lambda }^k,x^{k-1}\right)+\frac{\rho }{2}{\Vert \Delta y^k\Vert }^2+n_1{\Vert \Delta x^k\Vert }^2+n_2{\Vert \Delta x^{k-1}\Vert }^2-{\kappa }_1{\Vert \Delta y^{k+1}\Vert }^2-{\kappa }_2{\Vert \Delta x^{k+1}\Vert }^2,\end{array}$

则$\widehat{L}\left({\widehat{z}}^{k+1}\right)\le \widehat{L}\left({\widehat{z}}^k\right)-{\kappa }_1{\Vert \Delta y^{k+1}\Vert }^2-{\kappa }_2{\Vert \Delta x^{k+1}\Vert }^2$ 。

2) 由于$\left\{z^{{}_k}\right\}$ 有界，则$\left\{{\widehat{z}}^k\right\}$ 有界并且至少有一个聚点，即存在子序列$\left\{{\widehat{z}}^{k_j}\right\}$ ，使得$\underset{j\to \infty }{\lim }{\widehat{z}}^{k_j}={\widehat{z}}^{*}$ 。因为$f$ 是连续可微函数，$g$ 是下半连续函数，所以$\widehat{L}(\cdot )$ 为下半连续函数，因此，$\underset{j\to \infty }{\lim }\inf \widehat{L}\left({\widehat{z}}^{k_j}\right)\ge \widehat{L}\left({\widehat{z}}^{*}\right)$ ，$\widehat{L}\left({\widehat{z}}^{k_j}\right)$ 有下界。

根据假设1的3)知${\kappa }_i>0,i=1,2$ ，因此$\left\{\widehat{L}\left({\widehat{z}}^k\right)\right\}$ 单调非增，由于单调序列的子列收敛等价于全序列收敛，即有$\left\{\widehat{L}\left({\widehat{z}}^k\right)\right\}$ 收敛且$\widehat{L}\left({\widehat{z}}^{*}\right)\le \widehat{L}\left({\widehat{z}}^k\right)$ 。由(10)式，得

${\kappa }_1{\displaystyle \sum _{k=0}^{+\infty }{\Vert \Delta y^{k+1}\Vert }^2}+{\kappa }_2{\displaystyle \sum _{k=0}^{+\infty }{\Vert \Delta x^{k+1}\Vert }^2}\le \widehat{L}\left({\widehat{z}}^0\right)-\widehat{L}\left({\widehat{z}}^{*}\right)<\text{+}\infty$.

基于${\kappa }_i>0,i=1,2$ ，可推导出${\displaystyle \sum _{k=0}^{\infty }{\Vert \Delta y^{k+1}\Vert }^2}<\text{+}\infty$ 与${\displaystyle \sum _{k=0}^{\infty }{\Vert \Delta x^{k+1}\Vert }^2}<\text{+}\infty$ 。

进而由(6)式，可得${\displaystyle \sum _{k=0}^{\infty }{\Vert \Delta {\lambda }^{k+1}\Vert }^2}<\text{+}\infty$ 。因此${\displaystyle \sum _{k=0}^{\infty }{\Vert z^{k+1}-z^k\Vert }^2}<\text{+}\infty$ 。

注1 由引理2的1)可知，若${\kappa }_i>0,i=1,2$ ，则序列$\left\{\widehat{L}\left({\widehat{z}}^k\right)\right\}$ 是非增的。

下面的引理给出效益函数次梯度的上限估计。

引理3 若假设1成立，令$\left\{z^k\right\}$ 是由IMBADMM算法生成的序列，当它有界时，对于每一个$k\ge 0$ ，有

${\epsilon }^{k+1}={\left({\epsilon }_1^{k+1},{\epsilon }_2^{k+1},{\epsilon }_3^{k+1},{\epsilon }_4^{k+1},{\epsilon }_5^{k+1},{\epsilon }_6^{k+1},{\epsilon }_7^{k+1}\right)}^{\text{T}}\in \partial \widehat{L}\left({\widehat{z}}^{k+1}\right)$,

其中$\{\begin{array}{l}{\epsilon }_1^{k+1}=\nabla f\left(x^k\right)+{\widehat{\sum }}_f\left(x^{k+1}-x^k\right)+A^{\text{T}}{\lambda }^{k+1}+\beta A^{\text{T}}\left(A{x}^{k+1}-B{y}^{k+1}\right)+2n_1\Delta x^{k+1}\\ {\epsilon }_2^{k+1}\in \partial g\left(y^{k+1}\right)-B^{\text{T}}{\lambda }^{k+1}-\beta B^{\text{T}}\left(A{x}^{k+1}-B{y}^{k+1}\right)+\rho \Delta y^{k+1}\\ {\epsilon }_3^{k+1}=\Vert \Delta {\lambda }^{k+1}\Vert /\beta \\ {\epsilon }_4^{k+1}=\left({\nabla }^{2}f\left(x^k\right)-{\widehat{\sum }}_f\right)\Delta x^{k+1}\\ {\epsilon }_5^{k+1}=-\rho \Delta y^{k+1}\\ {\epsilon }_6^{k+1}=2n_2\Delta x^k-2n_1\Delta x^{k+1}\\ {\epsilon }_7^{k+1}=-2n_2\Delta x^k,\end{array}$。

且存在$\tau >0$ ，使得$d\left(0,\partial \widehat{L}\left({\widehat{z}}^{k+1}\right)\right)\le \Vert {\epsilon }^{k+1}\Vert \le \tau \left(\Vert \Delta y^k\Vert +\Vert \Delta y^{k+1}\Vert +\Vert \Delta x^{k-1}\Vert +\Vert \Delta x^k\Vert +\Vert \Delta x^{k+1}\Vert \right)$ 。

证明：根据(7)式效益函数的定义得

$\begin{array}{l}\widehat{L}\left({\widehat{z}}^{k+1}\right)=\widehat{f}\left(x^{k+1},x^k\right)+g\left(y^{k+1}\right)+\langle {\lambda }^{k+1},A{x}^{k+1}-B{y}^{k+1}\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}-B{y}^{k+1}\Vert }^2\\ \text{+}\frac{\rho }{2}{\Vert \Delta y^{k+1}\Vert }^2+n_1{\Vert \Delta x^{k+1}\Vert }^2+n_2{\Vert \Delta x^k\Vert }^2\end{array}$ (17)

对$\widehat{L}(\cdot )$ 各分量求偏导，${\epsilon }^{k+1}$ 可以表示为

$\{\begin{array}{l}{\epsilon }_1^{k+1}=\nabla f\left(x^k\right)+{\widehat{\sum }}_f\left(x^{k+1}-x^k\right)+A^{\text{T}}{\lambda }^{k+1}+\beta A^{\text{T}}\left(A{x}^{k+1}-B{y}^{k+1}\right)+2n_1\Delta x^{k+1}\text{ (18a)}\\ {\epsilon }_2^{k+1}\in \partial g\left(y^{k+1}\right)-B^{\text{T}}{\lambda }^{k+1}-\beta B^{\text{T}}\left(A{x}^{k+1}-B{y}^{k+1}\right)+\rho \Delta y^{k+1}\text{ (18b)}\\ {\epsilon }_3^{k+1}=A{x}^{k+1}-B{y}^{k+1}\text{ (18c)}\\ {\epsilon }_4^{k+1}=\left({\nabla }^{2}f\left(x^k\right)-{\widehat{\sum }}_f\right)\Delta x^{k+1}\text{ (18d) }\\ {\epsilon }_5^{k+1}=-\rho \Delta y^{k+1}\text{ (18e)}\\ {\epsilon }_6^{k+1}=2n_2\Delta x^k-2n_1\Delta x^{k+1}\text{ (18f)}\\ {\epsilon }_7^{k+1}=-2n_2\Delta x^k\text{. (18g)}\end{array}$

根据(5b)式的最优性条件得

$\nabla f\left(x^k\right)+{\widehat{\sum }}_f\left(x^{k+1}-x^k\right)=-A^{\text{T}}{\lambda }^k-\beta A^{\text{T}}\left(A{x}^{k+1}-B{y}^{k+1}\right)+\nabla T_2\left(x^k\right)-\nabla T_2\left(x^{k+1}\right)-{\theta }_k\left(x^{k-1}-x^k\right)$

代入(18a)式有

${\epsilon }_1{}^{k+1}=A^{\text{T}}\Delta {\lambda }^{k+1}+\nabla T_2\left(x^k\right)-\nabla T_2\left(x^{k+1}\right)-{\theta }_k\left(x^{k-1}-x^k\right)+2n_1\Delta x^{k+1}.$

由于$\nabla T_2$ 是$l_{T_2}$ -Lipschitz连续的，则

$\Vert {\epsilon }_1^{k+1}\Vert \le \Vert A\Vert \Vert \Delta {\lambda }^{k+1}\Vert +\left(l_{T_2}+2n_1\right)\Vert \Delta x^{k+1}\Vert +{\theta }_k\Vert \Delta x^k\Vert .$ (19)

根据(5a)式的最优性条件得

$\partial g\left(y^{k+1}\right)∍B^{\text{T}}{\lambda }^k+\beta B^{\text{T}}\left(A{x}^k-B{y}^{k+1}\right)+\nabla T_1\left(y^k\right)-\nabla T_1\left(y^{k+1}\right)-{\rho }_k\left(y^{k-1}-y^k\right)$

代入(18b)式有

${\epsilon }_2^{k+1}=-B^{\text{T}}\Delta {\lambda }^{k+1}-\beta B^{\text{T}}A\Delta x^{k+1}+\nabla T_1\left(y^k\right)-\nabla T_1\left(y^{k+1}\right)+{\rho }_k\Delta y^k+\rho \Delta y^{k+1}.$

由于$\nabla T_1$ 是$l_{T_1}$ -Lipschitz连续的，则

$\Vert {\epsilon }_2^{k+1}\Vert \le \Vert B\Vert \Vert \Delta {\lambda }^{k+1}\Vert +\beta \Vert B\Vert \Vert A\Vert \Vert \Delta x^{k+1}\Vert +\left(l_{T_1}+\rho \right)\Vert \Delta y^{k+1}\Vert +{\rho }_k\Vert \Delta y^k\Vert .$ (20)

根据(5c)式得$A{x}^{k+1}-B{y}^{k+1}=\frac{1}{\beta }\Delta {\lambda }^{k+1}$ ，则

$\Vert {\epsilon }_3^{k+1}\Vert =\frac{1}{\beta }\Vert \Delta {\lambda }^{k+1}\Vert$ . (21)

因此，${\epsilon }^{k+1}\in \partial \widehat{L}\left({\widehat{z}}^{k+1}\right)$ ，根据(18d~18g)式及(19~21)式，存在${\xi }_1>0$ 使得

$\Vert {\epsilon }^{k+1}\Vert \le {\xi }_1\left(\Vert \Delta x^k\Vert +\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^k\Vert +\Vert \Delta y^{k+1}\Vert +\Vert \Delta {\lambda }^{k+1}\Vert \right)$ .

根据引理1，存在${\xi }_2>0$ 使得$\Vert \Delta {\lambda }^{k+1}\Vert \le {\xi }_2\left(\Vert \Delta x^k\Vert +\Vert \Delta x^{k+1}\Vert +\Vert \Delta x^{k-1}\Vert \right)$ 。

综合上述两个不等式，当${\epsilon }^{k+1}\in \partial \widehat{L}\left({\widehat{z}}^{k+1}\right)$ 时，可得

$\begin{array}{l}d\left(0,\partial \widehat{L}\left({\widehat{z}}^{k+1}\right)\right)\le \Vert {\epsilon }^{k+1}\Vert \le {\xi }_1\left(1+{\xi }_2\right)\left(\Vert \Delta y^k\Vert +\Vert \Delta y^{k+1}\Vert +\Vert \Delta x^{k-1}\Vert +\Vert \Delta x^k\Vert +\Vert \Delta x^{k+1}\Vert \right)\\ =\tau \left(\Vert \Delta y^k\Vert +\Vert \Delta y^{k+1}\Vert +\Vert \Delta x^{k-1}\Vert +\Vert \Delta x^k\Vert +\Vert \Delta x^{k+1}\Vert \right),\end{array}$

其中$\tau ={\xi }_1\left(1+{\xi }_2\right)>0$ 。

定理1 (子序列收敛性) 若假设1成立，$\left\{z^k\right\}$ 为IMBADMM算法生成的序列，且假设$\left\{z^k\right\}$ 有界。令$\Omega$ 表示序列$\left\{z^k\right\}$ 的聚点集，$\widehat{\Omega }$ 表示序列$\left\{{\widehat{z}}^k\right\}$ 的聚点集，则以下结论成立：

1) $\Omega$ 是一个非空紧集，且当$k\to \infty$ 时，$d\left(z^k,\Omega \right)\to 0$ ；$\Omega$ 里面的点都是$L_{\beta }(\cdot )$ 的临界点；$\left(x^{\ast },y^{\ast },{\lambda }^{\ast },{x^{\prime }}^{\ast },{\widehat{y}}^{\ast },{\widehat{x}}^{\ast },{\overline{x}}^{\ast }\right)\in \widehat{\Omega }$ ，当且仅当$x^{\ast }={x^{\prime }}^{\ast }={\widehat{x}}^{\ast }={\overline{x}}^{\ast },$ $y^{\ast }={\widehat{y}}^{\ast }$ 且$\left(x^{\ast },y^{\ast },{\lambda }^{\ast }\right)\in \Omega$ ；

2) $\widehat{L}(\cdot )$ 是有限的且在$\widehat{\Omega }$ 上为常数，$\underset{k\in N}{\inf }\widehat{L}\left({\widehat{z}}^k\right)=\underset{k\to +\infty }{\lim }\widehat{L}\left({\widehat{z}}^k\right)$ 。

接下来的结果显示，当效益函数是KL函数时，序列$\left\{z^k\right\}$ 将收敛到优化问题(1)的临界点。

证明：

1) 因$\left\{z^k\right\}$ 有界，故$\left\{z^k\right\}$ 至少存在一个聚点，其聚点集$\Omega$ 非空且为紧集。

令$z^{\ast }\in \Omega$ ，那么存在$\left\{z^k\right\}$ 的一个子序列$\left\{z^{k_j}\right\}$ ，使得：$\underset{j\to \infty }{\lim }\left(z^{k_j}\right)=z^{\ast }$ 。

根据引理2的2)，有$\underset{j\to \infty }{\lim }\Vert z^{k_j+1}-z^{k_j}\Vert =0$ ，进而可得$\underset{j\to \infty }{\lim }\left(z^{k_j+1}\right)=z^{\ast }$ 。

由于${\lambda }^{k_j+1}={\lambda }^{k_j}+\beta \left(A{x}^{k_j+1}-B{y}^{{}^{k_j+1}}\right)$ 且$\beta >0$ ，从而$A{x}^{\ast }-B{y}^{\ast }=0$ 。

又由于$y^{k+1}$ 是(5a)的最优解，故有

$\begin{array}{l}\widehat{L}\left(x^k,y^{k+1},{\lambda }^k,x^k,y^k,x^{k-1},x^{k-2}\right)\le \widehat{L}\left(x^k,y^{\ast },{\lambda }^k,x^k,y^k,x^{k-1},x^{k-2}\right)\\ +D_{T_1}\left(y^{\ast },y^k\right)-D_{T_1}\left(y^{k+1},y^k\right)+\frac{\rho }{2}{\Vert y^{k+1}-y^k\Vert }^2-\frac{\rho }{2}{\Vert y^{\ast }-y^k\Vert }^2-{\rho }_k\langle y^{\ast }-y^{k+1},\Delta y^k\rangle .\end{array}$ (22)

因为效益函数$\widehat{L}\left(x,y,\lambda ,x^{\prime },\widehat{y},\widehat{x},\overline{x}\right)$ 关于变量$\left(x,\lambda ,x^{\prime },\widehat{y},\widehat{x},\overline{x}\right)$ 是连续的，所以

$\begin{array}{l}\underset{j\to \infty }{\lim }\sup \widehat{L}\left({\widehat{z}}^{k_j+1}\right)\stackrel{\left(22\right)}{\le }\underset{j\to \infty }{\lim }\sup \{\widehat{L}\left(x^{k_j},y^{\ast },{\lambda }^{k_j},x^{k_j},y^{k_j},x^{k_j-1},x^{k_j-2}\right)+{\Delta }_{T_1}\left(y^{\ast },y^{k_j}\right)-{\Delta }_{T_1}\left(y^{k_j+1},y^{k_j}\right)\\ +\frac{\rho }{2}{\Vert y^{k_j+1}-y^{k_j}\Vert }^2-\frac{\rho }{2}{\Vert y^{\ast }-y^{k_j}\Vert }^2-{\rho }_k\langle y^{\ast }-y^{k_j+1},\Delta y^{k_j}\rangle \}=\widehat{L}\left({\widehat{z}}^{\ast }\right).\end{array}$ (23)

由于$f$ 是连续函数且$g$ 是下半连续函数，则$\widehat{L}(\cdot )$ 是下半连续函数。因此，

$\widehat{L}\left({\widehat{z}}^{\ast }\right)\le \underset{j\to \infty }{\lim }\inf \widehat{L}\left({\widehat{z}}^{k_j+1}\right).$ (24)

根据(23)式和(24)式可得

$\underset{j\to \infty }{\lim }\widehat{L}\left({\widehat{z}}^{k_j+1}\right)=\widehat{L}\left({\widehat{z}}^{\ast }\right).$ (25)

由此可得$\underset{k_j\to \infty }{\lim }g\left(y^{k_j+1}\right)=g\left(y^{*}\right)$ 。利用$\nabla f$ 的连续性和$\partial g$ 的闭合性质，结合(5)式的最优性条件得$B^T{\lambda }^{\ast }\in \partial g\left(y^{\ast }\right),\nabla f\left(x^{\ast }\right)=-A^{\text{T}}{\lambda }^{\ast },A{x}^{\ast }-B{y}^{\ast }=0$ 。

这表明$z^{\ast }$ 是$L_{\beta }(\cdot )$ 的临界点。

2) 根据(25)式有$\underset{k\to \infty }{\lim }\inf \widehat{L}\left({\widehat{z}}^{k+1}\right)=\underset{j\to \infty }{\lim }\widehat{L}\left({\widehat{z}}^{k_j+1}\right)=\widehat{L}\left(z^{\ast }\right)=f\left(x^{\ast }\right)+g\left(y^{\ast }\right)=L_{\beta }\left(z^{\ast }\right)$ ，又由引理2，$\widehat{L}(\cdot )$ 是单调非增的，故有$\underset{k\in N}{\inf }\widehat{L}\left({\widehat{z}}^k\right)=\underset{k\to \infty }{\lim }\widehat{L}\left({\widehat{z}}^k\right)=\widehat{L}\left(z^{\ast }\right)$ 。

定理2 (全局收敛性) 若假设1成立，$\left\{z^k\right\}$ 是IMBADMM算法生成的序列，且假设$\left\{z^k\right\}$ 有界。设$\widehat{\Omega }$ 表示序列$\left\{{\widehat{z}}^k\right\}$ 的聚点集，如果$\widehat{L}(\cdot )$ 满足$\widehat{\Omega }$ 上的KL性质，则以下结论成立：

1) 序列$\left\{z^k\right\}$ 具有有限长度，即：${\displaystyle \sum _{k=0}^{+\infty }\Vert z^{k+1}-z^k\Vert }<+\infty$ 。

2) 序列$\left\{z^k\right\}$ 收敛到优化问题(1)的临界点。

证明：根据定理1的2)得$\underset{k\to \infty }{\lim }\widehat{L}\left({\widehat{z}}^k\right)=\widehat{L}\left({\widehat{z}}^{*}\right)$ ，对所有${\widehat{z}}^{*}\in \widehat{\Omega }$ ，我们考虑以下两种情况。

a) 假设存在$k_0\in N$ ，满足$\widehat{L}\left({\widehat{z}}^{k_0}\right)=\widehat{L}\left({\widehat{z}}^{*}\right)$ 。由引理2的1)知

当${\kappa }_1>0$ 且${\kappa }_2>0$ 时，不等式${\kappa }_1{\Vert \Delta y^{k+1}\Vert }^2+{\kappa }_2{\Vert \Delta x^{k+1}\Vert }^2\le \widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{k+1}\right)$ 成立。由于假设了$\widehat{L}\left({\widehat{z}}^{k_0}\right)=\widehat{L}\left({\widehat{z}}^{*}\right)$ ，则对于任意$k>k_0$ ，有$\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{k+1}\right)\le \widehat{L}\left({\widehat{z}}^{k_0}\right)-\widehat{L}\left({\widehat{z}}^{*}\right)=0$ 。结合${\kappa }_1>0$ 且${\kappa }_2>0$ ，可推出对任意$k>k_0$ ，有$x^{k+1}=x^k$ 且$y^{k+1}=y^k$ 。

再结合引理1，可知对任意$k>k_0$ ，${\lambda }^{k+1}={\lambda }^k$ ，综上有$z^{k+1}=z^k$ 。

b) 假设对于任意$k>1$ ，均有$\widehat{L}\left({\widehat{z}}^k\right)>\widehat{L}\left({\widehat{z}}^{*}\right)$ 。因为$d\left({\widehat{z}}^k,\widehat{\Omega }\right)\to 0$ ，对于给定$\epsilon >0$ ，存在$k_1>0$ ，当$k>k_1$ 时，有$d\left({\widehat{z}}^k,\widehat{\Omega }\right)<\epsilon$ 。又因为$\underset{k\to \infty }{\lim }\widehat{L}\left({\widehat{z}}^k\right)=\widehat{L}\left({\widehat{z}}^{\ast }\right)$ ，对于给定$\eta >0$ ，存在$k_2>0$ ，当$k>k_2$ 时，有$\widehat{L}\left({\widehat{z}}^k\right)<\widehat{L}\left({\widehat{z}}^{\ast }\right)+\eta$。如果$k>\tilde{k}=\text{max}\left\{k_1,k_2\right\}$，那么$d\left({\widehat{z}}^k,\widehat{\Omega }\right)<\epsilon$ ，$\widehat{L}\left({\widehat{z}}^{\ast }\right)<\widehat{L}\left({\widehat{z}}^k\right)<\widehat{L}\left({\widehat{z}}^{\ast }\right)+\eta$ 。根据性质2，对任意的$k>\tilde{k}$ ，存在可微凹函数$\phi \in {\Phi }_{\eta }$ ，有${\phi }^{\prime }\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)d\left(0,\partial \widehat{L}\left({\widehat{z}}^k\right)\right)\ge 1$ 。因为：${\phi }^{\prime }\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)>0$ ，所以

$\frac{1}{{\phi }^{\prime }\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)}\le d\left(0,\partial \widehat{L}\left({\widehat{z}}^k\right)\right).$ (26)

根据$\phi$ 的凹性得

$\phi \left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)-\phi \left(\widehat{L}\left({\widehat{z}}^{k+1}\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)\ge {\phi }^{\prime }\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{k+1}\right)\right)$

由此可推导出$0\le \widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{k+1}\right)\le \frac{\phi \left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)-\phi \left(\widehat{L}\left({\widehat{z}}^{k+1}\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)}{{\phi }^{\prime }\left(\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)}$ .

为了简化表达，定义${\Delta }_{p,q}:=\phi \left(\widehat{L}\left({\widehat{z}}^p\right)-\widehat{L}\left({\widehat{z}}^{*}\right)\right)-\phi \left(\widehat{L}\left({\widehat{z}}^q\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)$ ，以及

${\Gamma }_k=\Vert \Delta y^{k-1}\Vert +\Vert \Delta y^k\Vert +\Vert \Delta x^k\Vert +\Vert \Delta x^{k-1}\Vert +\Vert \Delta x^{k-2}\Vert$ .

由(26)式及引理3，对于任意$k\ge 1$ ，有

$\widehat{L}\left({\widehat{z}}^k\right)-\widehat{L}\left({\widehat{z}}^{k+1}\right)\stackrel{(26)}{\le }{\Delta }_{k，k+1}d\left(0,\partial \widehat{L}\left({\widehat{z}}^k\right)\right)\le \tau {\Delta }_{k，k+1}{\Gamma }_k$ .

根据引理2的1)及上述不等式，可知对任意$k>\tilde{k}$ ，有

${\kappa }_1{\Vert \Delta y^{k+1}\Vert }^2+{\kappa }_2{\Vert \Delta x^{k+1}\Vert }^2\le \tau {\Delta }_{k,k+1}{\Gamma }_k$ .

上述分析表明，存在$\xi =\min \left\{{\kappa }_1,{\kappa }_2\right\}>0$ ，使得

${\Vert \Delta x^{k+1}\Vert }^2+{\Vert \Delta y^{k+1}\Vert }^2\le \frac{\tau }{\xi }{\Delta }_{k,k+1}{\Gamma }_k$ .

利用不等式$2ab\le a^2+b^2$ ，有

${\left(\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert \right)}^2\le 2\left({\Vert \Delta x^{k+1}\Vert }^2+{\Vert \Delta y^{k+1}\Vert }^2\right)\le 2\frac{\tau }{\xi }{\Delta }_{k,k+1}{\Gamma }_k$ .

可推出

$4\left(\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert \right)\le {\Gamma }_k+\frac{8\tau }{\xi }{\Delta }_{k,k+1}\le {\Gamma }_k+\Vert \Delta y^{k-2}\Vert +\frac{8\tau }{\xi }{\Delta }_{k,k+1}$ .

由于$2{\Gamma }_k^{\frac{1}{2}}\left(2\sqrt{\frac{2\tau }{\xi }}{\Delta }_{k,k+1}^{\frac{1}{2}}\right)\le {\Gamma }_k+\frac{8\tau }{\xi }{\Delta }_{k,k+1}$ ，

根据上述公式得

$4{\displaystyle \sum _{k=\tilde{k}+1}^m\left(\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert \right)}\le {\displaystyle \sum _{k=\tilde{k}+1}^m\left({\Gamma }_k+\Vert \Delta y^{k-2}\Vert \right)}+\frac{8\tau }{\xi }{\Delta }_{\tilde{k}+1,m+1}$ .

两边取极限$m\to +\infty$ ，得

$\begin{array}{l}{\displaystyle \sum _{k=\tilde{k}+1}^{+\infty }\left(\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert \right)}\le {\displaystyle \sum _{k=\tilde{k}+1}^{+\infty }\left(\Vert \Delta y^{k-1}\Vert +\Vert \Delta y^k\Vert +\Vert \Delta x^k\Vert +\Vert \Delta x^{k-1}\Vert +\Vert \Delta x^{k-2}\Vert +\Vert \Delta y^{k-2}\Vert \right)+\frac{8\tau }{\xi }{\Delta }_{\tilde{k}+1,m+1}}\\ \le \left(3\Vert \Delta y^{\tilde{k}+1}\Vert +2\Vert \Delta y^{\tilde{k}}\Vert +\Vert \Delta y^{\tilde{k}-1}\Vert +3\Vert \Delta x^{\tilde{k}+1}\Vert +2\Vert \Delta x^{\tilde{k}}\Vert +\Vert \Delta x^{\tilde{k}-1}\Vert \right)\text{+}\frac{8\tau }{\xi }\phi \left(\widehat{L}\left({\widehat{z}}^{\tilde{k}+1}\right)-\widehat{L}\left({\widehat{z}}^{\ast }\right)\right)。\end{array}$

因此，${\displaystyle \sum _{k=\tilde{k}+1}^{\infty }\left(\Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert \right)}<+\infty$ 。

根据引理1及$0\le {\theta }_k\le \theta$ ，我们推导出${\displaystyle \sum _{k=1}^{\infty }\left(\Vert \Delta {\lambda }^{k+1}\Vert \right)}<+\infty$ 。

进一步观察到$\Vert z^{k+1}\Vert ={\left({\Vert \Delta x^{k+1}\Vert }^2+{\Vert \Delta y^{k+1}\Vert }^2+{\Vert \Delta {\lambda }^{k+1}\Vert }^2\right)}^{\frac{1}{2}}\le \Vert \Delta x^{k+1}\Vert +\Vert \Delta y^{k+1}\Vert +\Vert \Delta {\lambda }^{k+1}\Vert$ 。

由此可得${\displaystyle \sum _{k=1}^{\infty }\Vert \Delta z^{k+1}\Vert }<+\infty$ ，这表明$\left\{z^k\right\}$ 是一个柯西序列，从而$\left\{z^k\right\}$ 收敛。

从定理1，我们知$\left\{z^k\right\}$ 收敛到$L_{\beta }(\cdot )$ 的临界点。

4. 数值实验

下面通过数值实验对比IMBADMM、MBADMM [8]、ADMM [17]、SGD [18]与LBADMM [19]算法的性能。所有实验均在配备16 GB内存、3.20 GHz、AMD Ryzen 7 6800H with Radeon Graphics CPU的联想电脑上进行，操作系统为Windows 11，使用Matlab R2023a版本进行编码和执行。

针对问题(1)考虑稀疏逻辑回归问题，基本模型如下：

$\underset{x}{\min }{\displaystyle \sum _{i=1}^n\log \left(1+\exp \left(-b_i{a}_i^{\text{T}}x\right)\right)}+n\rho {\Vert x\Vert }_q。$ (27)

其中：$a_i\in R^d$ 是样本$i\left(i=1,2,\cdots ,n\right)$ 的特征向量，$b_i\in \left\{1,-1\right\}$ 是相应的二分类，$\rho$ 是一个正则化参数，${\Vert .\Vert }_q$

是$l_q$ 范数，对任意的$x\in R^d$ 有${\Vert x\Vert }_q={\left({\displaystyle \sum _{i=1}^n{\left|x_i\right|}^q}\right)}^{1/q}$ ，$q\in \left(0,1\right]$ 。令$A={\left(a_1,a_2,\cdots ,a_n\right)}^{\text{T}}\in R^{n\times d}$ ，

$b={\left(b_1,b_2,\cdots ,b_n\right)}^{\text{T}}\in R^n$ ，则$\left(a_i,b_i\right)$ $\left(i\in \left\{i=1,2,\cdots ,n\right\}\right)$ 是训练集$\left(a,b\right)$ 的一个样本。该问题有$n$ 个样本，维数为$d$ 。

在实际应用中，我们将(27)式转化为：

$\underset{x}{\min }{\displaystyle \sum _{i=1}^n\log \left(1+\exp \left(-b_i{a}_i^{\text{T}}x\right)\right)}+n\rho {\Vert y\Vert }_q,s.t.x-y=0.$ (28)

于是(28)式即为优化问题(1)的形式，其中$f\left(x\right)={\displaystyle \sum _{i=1}^n\log \left(1+\exp \left(-b_i{a}_i^{\text{T}}x\right)\right)}$ ，$g\left(y\right)=n\rho {\Vert y\Vert }_q$ 。易知：$\nabla f$ 是Lipschitz连续的，其Lipschitz连续常数$L=\frac{1}{4}{\Vert A\Vert }^2$ 。所以存在一个半正定矩阵${\widehat{\sum }}_f$ 使得对任意给定的$x^{\prime }\in R^d$ ，有：

$f\left(x\right)\le \widehat{f}\left(x,x^{\prime }\right):=f\left(x^{\prime }\right)+\langle \nabla f\left(x^{\prime }\right),x-x^{\prime }\rangle +\frac{1}{2}{\Vert x-x^{\prime }\Vert }_{{\widehat{\sum }}_f}^2$ ,

令$C_i^T=-b_i{a}_i^{\text{T}}$ ，经计算有：

$\nabla f\left(x\right)={\displaystyle \sum _{i=1}^n\frac{C_i{\text{e}}^{C_{i}x}}{1+{\text{e}}^{C_{i}x}}},{\nabla }^{2}f\left(x\right)=C_i{C}_i^{\text{T}}{\displaystyle \sum _{i=1}^n\frac{C_i{\text{e}}^{C_{i}x}}{{\left(1+{\text{e}}^{C_{i}x}\right)}^2}}\underset{\_}{\prec }\frac{1}{4}{\displaystyle \sum _{i=1}^n{C}_i{C}_i^{\text{T}}}$ ，因此，${\widehat{\sum }}_f$ 的近似项可以选择为：${\widehat{\sum }}_f=\frac{1}{4}C{C}_{}^{\text{T}}$，其中$C=\left[C_1,\cdots ,C_n\right]\in R^{d\times n}$ 。对五种算法最大迭代次数设为5000，取${\rho }_k=0.01,{\theta }_k=0.01$ 。

本实验数据来源于LIBSVM数据库(https://www.csie.ntu.edu.tw/cjlin/libsvmtools/)提供的a2000a数据集进行了数值实验。分别取不同的范数正则项q = 1和q = 1/2，表1展示了IMBADMM、MBADMM、ADMM、SGD以及LBADMM算法在处理稀疏逻辑回归问题(28)时的数值结果比较。观察表1中的数据，在计算效率方面，IMBADMM仅需0.07秒即可完成优化，相比MBADMM提速25~30倍；在收敛速度方面，IMBADMM所需迭代次数最少，相比ADMM减少约50%~65%的迭代次数；特别值得注意的是，在保持计算精度的前提下(q = 1时目标函数值616.01 vs MBADMM的616.02)，IMBADMM实现了计算效率的显著提升。对于非光滑情况(q = 1/2)，IMBADMM同样展现出强大优势，相比LBADMM将计算时间从11.37秒降至0.07秒，提速162倍，同时迭代次数从2326次减少至57次。这些实验结果充分证明了IMBADMM算法在处理大规模优化问题的卓越性能。与随机梯度下降(SGD)算法的对比显示：虽然SGD在计算时间上略有优势(0.02 s vs 0.07 s)，但IMBADMM在优化质量和收敛性方面表现出优势。为了直观分析算法的收敛性能，我们分别绘制了IMBADMM、MBADMM和ADMM算法在参数取值为q = 1和q = 1/2时的收敛曲线。其中，图1展示了IMBADMM算法的误差随迭代次数的演化过程，图2则呈现了三种算法的目标函数值随迭代次数的收敛特性。通过图2可知，IMBADMM算法展现出最平滑的收敛轨迹，算法更具有稳定性且收敛速度快。

Table 1. Comparison of numerical results of the five algorithms

表1. 五个算法的数值结果对比

算法	维度大小	数据来源	迭代次数	计算时间/s	目标函数值
IMBADMM (q = 1)	999 × 60	a2000a	55	0.07	616.01
MBADMM (q = 1)	999 × 60	a2000a	55	1.82	616.02
ADMM (q = 1)	999 × 60	a2000a	119	1.76	613.91
SGD (q = 1)	999 × 60	a2000a	150	0.02	962.71
LBADMM (q = 1)	999 × 60	a2000a	3006	1.18	620.00
IMBADMM (q = 1/2)	999 × 60	a2000a	57	0.07	672.07
MBADMM (q = 1/2)	999 × 60	a2000a	57	2.07	672.07
ADMM (q = 1/2)	999 × 60	a2000a	166	1.96	670.5
SGD (q = 1/2)	999 × 60	a2000a	150	0.02	1395.03
LBADMM (q = 1/2)	999 × 60	a2000a	2326	11.37	692.45

Figure 1. Evolution curve of the error with number of iterations when q = 1 and q = 1/2

图1. 当q = 1和q = 1/2时，误差随迭代次数的演化曲线

Figure 2. Evolution curve of the objective function value with the number of iterations when q = 1 and q = 1/2

图2. 当q = 1和q = 1/2时，目标函数值随迭代次数的演化曲线

5. 结论

本文针对非凸两分块优化问题，提出了一种带惯性项的Majorized Bregman交替方向乘子法(简称IMBADMM)，新算法结合了Majorized Bregman ADMM和惯性Bregman generalized ADMM的基本思想。 在适当的条件下，我们建立了算法的子序列收敛性和全局收敛性。最后，初步数值实验结果表明IMBADMM算法的有效性和可靠性。

基金项目

广西自然科学基金(2022GXNSFAA035618)。

NOTES

^*第一作者。

^#通讯作者。