基于随机镜像下降对称交替方向乘子法的非凸优化问题研究

The Research on Nonconvex Optimization Problems Based on Stochastic Mirror Descent Symmetric Alternating Direction Method of Multipliers

摘要: 本文考虑求解一类可分的带有等式约束的非凸非光滑优化问题，其目标函数是由有限个光滑函数的加权平均与适当下半连续函数的和函数组成。交替方向乘子法能够充分利用模型的特点，是目前求解该类问题有效方法之一，但由于数据规模大，传统的交替方向乘子法效率低下。本文提出“随机镜像下降对称交替方向乘子法”，该算法引入随机方差缩减算子，通过随机选取梯度信息减少梯度计算量，从而提高算法效率；同时使用布雷格曼(Bregman)距离以保证子问题具有显示解，此外算法的对偶变量以对称形式进行更新，提高了算法的高效性和稳定性。理论结果表明，在目标函数满足半代数性质时，该算法生成的迭代序列全局收敛到原问题的驻点。同时数值实验结果验证了算法的有效性。

Abstract: This paper considers solving a class of separable nonconvex and nonsmooth optimization problems with equality constraints, where the objective function is composed of the weighted average of a finite number of smooth functions and the sum of another proper lower semicontinuous function. The Alternating Direction Method of Multipliers (ADMM) effectively leverages the characteristics of the model and is one of the popular and efficient methods for solving such problems. However, due to the large data scale, traditional ADMM suffers from low efficiency. This paper proposes the “Stochastic Mirror Descent Symmetric Alternating Direction Method of Multipliers”, introduces a stochastic variance reduction operator, which reduces the gradient computation by randomly selecting gradient information, thereby improving the efficiency of the algorithm. Additionally, it uses the Bregman distance to ensure well-posed subproblems. Furthermore, the dual variables of the algorithm are updated symmetrically, which not only extends the applicability of the algorithm but also enhances its efficiency and stability. Theoretical results show that when the objective function satisfies the semi-algebraic property, the iterative sequence generated by the algorithm globally converges to a stationary point of the original problem. Numerical experiments further validate the effectiveness of the algorithm.

1. 引言

本文考虑一类具有等式约束的有限和形式的非凸非光滑优化问题，在机器学习中被广泛应用，具体模型如下：

$\underset{{}_{x\in {ℝ}^{d_1},y\in {ℝ}^{d_2}}}{\min }f\left(x\right)+g\left(y\right),\text{s}\text{.t}.Ax+By=b,$ (1)

其中$f:{ℝ}^{d_1}\to ℝ\cup \left\{+\infty \right\}$ 是适当下半连续函数，$g\left(y\right)=\frac{1}{m}{\displaystyle \sum _{i=1}^m{g}_i}\left(y\right)$ 其中每个分量函数$g_i:{ℝ}^{d_2}\to ℝ$ 是光滑函数，$A\in {ℝ}^{d\times d_1}$ ，$B\in {ℝ}^{d\times d_2}$ ，$b\in {ℝ}^d$ 。

模型(1)广泛应用于统计学习[1]、计算机视觉[2]、3D CT图像重建[3]等领域。给定一组训练样本$\left(a_i,b_i\right)$ ，其中$i=1,\cdots ,n$ ，$a_i$ 是输入数据，对应的标签$b_i\in \left\{-1,1\right\}$ 。此时二分类任务[4]可以表示为：

$\underset{y}{\min }\frac{1}{m}{\displaystyle \sum _{i=1}^m{g}_i}\left(y\right)+{\lambda }_1{\Vert By\Vert }_1,$

其中取$g_i$ 为非凸sigmoid函数：$g_i\left(y\right)=\frac{1}{1+\exp \left(b_i{a}_i^{\text{T}}y\right)}$ 。B为给定的矩阵，引入变量x，可将问题重新表述为(1)的形式，即$\underset{x,y}{\min }f\left(x\right)+g\left(y\right)$ ，s.t. $x-By=0$ ，其中$g\left(y\right)=1/m{\displaystyle {\sum }_{i=1}^m{g}_i}\left(y\right)$ ，$f\left(x\right)={\lambda }_1{\Vert x\Vert }_1$ 。

近年来，交替方向乘子法(ADMM)在非凸和随机优化中得到了广泛的研究。文献[5] [6]中，研究了非凸Bregman ADMM的收敛性。文献[7]中研究了对称形式ADMM的收敛性，然而在标准的凸性假设下并不收敛，但此文献验证了在确保其全局收敛的条件下对称ADMM比一般形式ADMM收敛更快，鉴于此，He等人在文献[8]中提出了一种严格收缩的Peaceman Rachford分裂方法。需要指出的是，这些研究均基于确定性ADMM方法，即不涉及任何随机性。在处理g为有限求和的情况时，计算全梯度$\nabla g$ 往往会非常耗时，导致方法效率降低。为了解决这一问题，研究者通过使用$\nabla g$ 的随机估计来代替全梯度的计算，从而衍生出多个随机版本的ADMM。随着大规模优化问题的出现随机梯度算法如SAGA [9]、SVRG [10]和SARAH [11]等推动了ADMM的进一步发展。在文献[12]中，作者将ADMM与SAG梯度估计算子进行结合，ADMM与SVRG的结合可参考文献[13] [14]等。所有这些研究均在凸优化框架下对随机ADMM进行了分析。在[15]中，研究者探讨了使用三种不同梯度估计(SGD、SVRG、SAGA)的随机ADMM方法来解决非凸非光滑优化问题，随之，文章[16]中提出了框架形式的随机ADMM算法，对大规模非凸优化问题进行研究。

本文提出了“随机镜像下降对称交替方向乘子法(SMD-SADMM)”。首先，该算法通过引入随机方差缩减算子，通过随机选择梯度信息，有效地减少了计算全梯度的需求，特别对于处理大规模数据的优化问题，显著提高了算法的运行效率；其次，算法利用布雷格曼(Bregman)距离定义的邻近项取代二范数，这确保了子问题具有显示解，进而提高了算法的效率；最后，SMD-SADMM采用了对偶变量的对称更新策略，有助于提升算法的收敛性，使得算法在处理非凸优化问题时表现出了更好的稳定性，从而为求解大规模非凸优化问题提供了一种稳健的解决方案。总体来说，SMD-SADMM算法结合Bregman距离定义的邻近项、对偶变量以对称形式进行更新的迭代形式、方差缩减的随机技巧为解决现代大规模非凸优化问题提供了有力的工具。

2. 基本定义

2.1. 布雷格曼距离与勒让德函数

定义2.1 [17] 设$\Omega \subset {ℝ}^d$ 为一个非空开凸集，函数$h:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ 如果满足以下性质：

(i) h是适当下半连续凸函数，且$dom h\subset \overline{\Omega }$ ，

(ii) h在$intdomh=\Omega$ 上是连续可微的，且$dom \partial h=\Omega$ ，则称h为勒让德函数。

定义2.2 [18] 设h为勒让德函数，定义与h相关的布雷格曼距离为$D_h:domh\times intdomh\to {ℝ}_{+}$ ，

$D_h\left(x,y\right)=h\left(x\right)-h\left(y\right)-\langle \nabla h\left(y\right),x-y\rangle .$ .

2.2. Kurdyka-Lojasiewicz (KL)性质

定义2.4 [19] 令$f:{ℝ}^d\to ℝ\cup \left\{+\infty \right\}$ 是一个适当下半连续函数，如果存在$\eta \in \left(0,+\infty \right]$ ，$\overline{x}\in dom\partial f$的邻域U，$\phi :\left[0,\eta \right)\to {ℝ}_{+}$ 使得

(i) $\phi \left(0\right)=0$ ，$\phi$ 在$\left(0,\eta \right)$ 上是连续可微函数使得${\phi }^{\prime }>0$ ；

(ii) 对于任意$x\in U\cap \left[x\in {ℝ}^d:f\left(\overline{x}\right)<f\left(x\right)<f\left(\overline{x}\right)+\eta \right]$ ，下列KL不等式成立：

${\phi }^{\prime }\left(f\left(x\right)-f\left(\overline{x}\right)\right)dist\left(0,\partial f\left(x\right)\right)\ge 1$ ,

则称函数f称为在$\overline{x}\in dom\partial f$上具有KL性质。

注释2.5 [19] 如下为定义2.4的相关说明：

(i) 定义2.4中的函数$\phi$ 称为f的去奇异化函数；

(ii) 在$dom\partial f$ 的每个点上满足KL不等式的适当下半连续函数称为KL函数；

(iii) 半代数函数满足KL不等式，其去奇异化函数的形式为$\phi \left(s\right)=a{s}^{1-\theta }$ ，其中$a>0$ ，$\theta \in \left[0,1\right)$ 称为该函数的KL指数。

3. 随机镜像下降对称交替方向乘子法及其收敛性

在本节中，我们首先给出随机镜像下降对称交替方向乘子法，然后对其进行收敛性分析，首先我们给出以下假设。

假设3.1

(i) $\inf \left\{f\left(x\right)+g\left(y\right):x\in {ℝ}^{d_1},y\in {ℝ}^{d_2}\right\}=\underset{\_}{\Phi }>-\infty$ ；

(ii) $f:{ℝ}^{d_1}\to ℝ\cup \{+\infty \}$ 是适当的下半连续函数，且$g:{ℝ}^{d_2}\to ℝ$ 是一个$L_g$ 光滑函数，矩阵B是列满秩的；

(iii) h在任意有界区间上是${\mu }_h$ 强凸的。

3.1. 随机镜像下降对称交替方向乘子法算法

算法1：随机镜像下降对称交替方向乘子法。

1. 输入$\beta >\frac{-2r+L_g+\frac{V_{\Upsilon }}{\rho }+V_1+2+\frac{8}{s+1}\sqrt{\frac{V_{\Upsilon }}{\rho }+V_1}}{\left(\frac{2}{s+1}-1\right){\lambda }_{\text{min}}\left(B^{\text{T}}B\right)}$ 。$s,r\in \left(0,1\right),\mu >0$ ，并初始化$x^0,y^0,{\lambda }^0$ ；

2. 当初始条件满足执行：

$x^{k+1}=\arg \underset{x}{\min }\left\{f\left(x\right)+{\left({\lambda }^k\right)}^{\text{T}}\left(Ax+B{y}^k-b\right)+\frac{\beta }{2}{\Vert Ax+B{y}^k-b\Vert }^2+\mu D_h\left(x,x^k\right)\right\},$ (2)

${\lambda }^{k+\frac{1}{2}}={\lambda }^k+s\beta \left(A{x}^{k+1}+B{y}^k-b\right),$ (3)

$y^{k+1}=\arg \underset{y}{\min }\left\{\langle \tilde{\nabla }g\left(y^k\right),y-y^k\rangle +{\left({\lambda }^{k+\frac{1}{2}}\right)}^{\text{T}}\left(A{x}^{k+1}+By-b\right)+\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b\Vert }^2+\frac{r}{2}{\Vert y-y^k\Vert }^2\right\},$ (4)

${\lambda }^{k+1}={\lambda }^{k+\frac{1}{2}}+\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right),$ (5)

3. 当终止条件满足，执行$x^{K+1}$ ，$y^{K+1}$ 。

注：$\tilde{\nabla }$ 是具有方差缩减的随机梯度估计算子(见定义3.1)。

定义3.1 方差缩减的随机梯度估计算子

记${\mathbb{E}}_k$ 为算法1中随机变量前k次迭代的条件期望，对于常数$V_1,V_2,V_{\Upsilon }\ge 0$ 以及$\rho \in \left(0,1\right]$ ，若下述条件成立，则称梯度估计$\tilde{\nabla }$ 为方差缩减随机梯度估计算子：

(1) (均方误差有界)存在随机变量序列${\left\{{\Upsilon }_k\right\}}_{k\ge 1}$ 以及随机向量$v_k^i$ ，其中${\Upsilon }_k={\displaystyle \sum _{i=1}^s{\Vert v_k^i\Vert }^2}$ 使得

${\mathbb{E}}_k{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2\le {\Upsilon }_k+V_1\left({\mathbb{E}}_k{\Vert y^{k+1}-y^k\Vert }^2+{\Vert y^k-y^{k-1}\Vert }^2\right)$ ，

以及存在${\Gamma }_k={\displaystyle \sum _{i=1}^s\Vert v_k^i\Vert }$ 使得${\mathbb{E}}_k\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert \le {\Gamma }_k+V_2\left({\mathbb{E}}_k\Vert y^{k+1}-y^k\Vert +\Vert y^k-y^{k-1}\Vert \right)$ 成立。

(2) (几何迭代) ${\mathbb{E}}_k{\Upsilon }_{k+1}\le \left(1-\rho \right){\Upsilon }_k+V_{\Upsilon }\left({\mathbb{E}}_k{\Vert y^{k+1}-y^k\Vert }^2+{\Vert y^k-y^{k-1}\Vert }^2\right)$ ；

(3) (估计量的收敛性)如果${\left\{y^k\right\}}_{k\in N}$ 满足$\underset{k\to +\infty }{\lim }\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2=0$ 则有$\mathbb{E}{\Upsilon }_k\to 0$ 且$\mathbb{E}{\Gamma }_k\to 0$ 。

注释3.2 SAGA与SARAH方差缩减随机梯度估计参数取值情况[16] [20]：

SAGA梯度估计作为一个有效的方差缩减随机梯度估计算子，其表达式如下：

${\tilde{\nabla }}_{\text{SAGA}}g\left(y^k\right)=\frac{1}{b}{\displaystyle \sum _{j\in B_k}\left(\nabla g_j\left(y^k\right)-\nabla g_j\left({\phi }_k^j\right)\right)}+\frac{1}{m}{\displaystyle \sum _{i=1}^m\nabla }{g}_i\left({\phi }_k^i\right),$

其中B_k是从所有包含b个元素的子集中均匀随机选择的小批量集合，子集的元素包含在$\left\{1,2,\cdots ,m\right\}$ 中。根据定义3.1计算可知SAGA相应参数为$V_1=V_2=0$ ，$\rho =\frac{b}{2m}$ 以及$V_{\Upsilon }=\left(1+\frac{2m}{b}\right)L_g^2$ 。

另一个常见的随机梯度估计为SARAH随机梯度估计，

${\tilde{\nabla }}_{\text{SARAH}}g\left(y^k\right)=\{\begin{array}{ll}\nabla g\left(y^k\right),\hfill & 以概率\frac{1}{p},\hfill \\ \frac{1}{b}{\displaystyle \sum _{j\in B_k}\left(\nabla g_j\left(y^k\right)-\nabla g_j\left(y^{k-1}\right)\right)}+{\tilde{\nabla }}_{\text{SARAH}}g\left(y^{k-1}\right),\hfill & 否则.\hfill \end{array}$

SARAH梯度估计相应参数取值为$V_1=V_{\Upsilon }=L_g^2$ ，$V_2=L_g$ ，$\rho =\frac{1}{p}$ 。

3.2. 随机镜像下降对称交替方向乘子法算法的全局收敛性分析

定理3.1 [21] [上鞅收敛定理] 设${\mathbb{E}}_k$ 为随机镜像下降对称交替方向乘子法算法前k次迭代的条件期望。设$b\in ℝ$ ，$\left\{U_k\right\}$ 和$\left\{V_k\right\}$ 分别为取值于$\left[b,+\infty \right)$ 和$\left[0,+\infty \right)$ 的随机变量序列，且$U_k$ 和$V_k$ 仅依赖于算法的前k次迭代。若对于所有$k\in \mathbb{N}$ ，

${\mathbb{E}}_k{U}_{k+1}+V_k\le U_k$

成立，则几乎必然有${\displaystyle \sum _{k=0}^{+\infty }{V}_k}<+\infty$ ，并且$U_k$ 几乎必然收敛到$\left[b,+\infty \right)$ 上的一个随机变量。

定义第$k\in \mathbb{N}$ 次迭代的李雅普诺夫函数如下：

$\begin{array}{l}{\Psi }_k\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)\\ ={\Phi }_k\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right){\Upsilon }_{k+1}\\ +\frac{4}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}{\Vert \tilde{\nabla }g\left(y^k\right)-g\left(y^k\right)\Vert }^2,\end{array}$

其中${\Upsilon }_k,V_1,V_2,V_r,\rho$ 是方差缩减梯度估计算子相应的随机变量和常数(参考定义3.1)，李雅普诺夫函数中具体参数以及函数表示如下：

${\Phi }_k\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)={ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2+G{\Vert y^k-y^{k-1}\Vert }^2,t_1=\frac{1}{\frac{V_{\Upsilon }}{\rho }+V_1},$

$\begin{array}{c}G=-\frac{4r^2}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }-\frac{L_g}{2}+r-\frac{1}{2t_1}+\left(-\frac{1}{2}\beta +\frac{\beta }{s+1}\right){\lambda }_{\min }\left(B^{\text{T}}B\right)\\ -\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right)\left(\frac{V_{\Upsilon }}{\rho }+V_1\right),\end{array}$

${ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)=f\left(x^k\right)+g\left(y^k\right)+{\left({\lambda }^k\right)}^{\text{T}}\left(A{x}^k+B{y}^k-b\right)+\frac{\beta }{2}{\Vert A{x}^k+B{y}^k-b\Vert }^2.$

为了便于叙述将李雅普诺夫函数${\Psi }_k\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)$ 记为${\Psi }_k$ ，${\Phi }_k\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)$ 记为$\Phi \left(X^k\right)$ 并将${\left\{\left(x^k,y^k,{\lambda }^k,x^{k-1},y^{k-1}\right)\right\}}_{k\in N}$ 记为${\left\{X^k\right\}}_{k\in N}$ 。

定理3.2 设假设3.1成立。令${\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}}_{k\in \mathbb{N}}$ 是由随机镜像下降对称交替方向乘子法算法生成的序列，并假设该序列是有界的。那么：

(i) 序列${\left\{{\Psi }_k\right\}}_{k\in \mathbb{N}}$ 在期望意义下是单调非增的。特别地，对于任意$k\in \mathbb{N}$ ，$t_1>0$ ，

$\tilde{\eta }=G-\frac{4{\left(L_g+r\right)}^2}{{\lambda }_{\text{min}}\left(B^{\text{T}}B\right)\left(s+1\right)\beta }-\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\text{min}}\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right)\left(\frac{V_{\Upsilon }}{\rho }+V_1\right)>0,$

成立：

${\mathbb{E}}_k{\Psi }_{k+1}\le {\Psi }_k-\tilde{\eta }{\mathbb{E}}_k{\Vert y^k-y^{k-1}\Vert }^2+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2$ ，

(ii) 迭代点间距平方的期望是可和的，即，${\displaystyle \sum _{k=0}^{+\infty }\mathbb{E}}{\Vert x^k-x^{k-1}\Vert }^2<+\infty$ ，${\displaystyle \sum _{k=0}^{+\infty }\mathbb{E}}{\Vert y^k-y^{k-1}\Vert }^2<+\infty$ 。此外，当$k\to +\infty$ 时，有$\mathbb{E}\Vert x^k-x^{k-1}\Vert \to 0$ ，$\mathbb{E}\Vert y^k-y^{k-1}\Vert \to 0$ 且$\mathbb{E}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert \to 0$ 。

(iii) ${\displaystyle \sum _{k=1}^{+\infty }{\Vert x^k-x^{k-1}\Vert }^2}<+\infty ,\Vert x^k-x^{k-1}\Vert \to 0,{\displaystyle \sum _{k=1}^{+\infty }{\Vert y^k-y^{k-1}\Vert }^2}<+\infty ,\Vert y^k-y^{k-1}\Vert \to 0$ 成立，并有${\Phi }^{*}$ 取值于$\left[\underset{\_}{\Phi },\infty \right)$ 使得$\underset{k\to +\infty }{\lim }\mathbb{E}{\Psi }_k=\underset{k\to +\infty }{\lim }\mathbb{E}\Phi \left(X^k\right)={\Phi }^{*}$ 。

证明：(i) 结合迭代(3)和(5)，有：

$A{x}^{k+1}+B{y}^k-b=\frac{1}{\left(s+1\right)\beta }\left({\lambda }^{k+1}-{\lambda }^k\right)-\frac{1}{s+1}\left(B{y}^{k+1}-B{y}^k\right),$ (6)

$A{x}^{k+1}+B{y}^{k+1}-b=\frac{1}{\left(s+1\right)\beta }\left({\lambda }^{k+1}-{\lambda }^k\right)+\frac{s}{s+1}\left(B{y}^{k+1}-B{y}^k\right).$ (7)

基于迭代(2)，

${ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)+\mu D_h\left(x^{k+1},x^k\right)\le {ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right).$ (8)

又g是$L_g$ 梯度利普希茨连续的，从而有

$\begin{array}{l}g\left(y^{k+1}\right)\le g\left(y^k\right)+\langle \nabla g\left(y^k\right),y^{k+1}-y^k\rangle +\frac{L_g}{2}{\Vert y^k-y^{k+1}\Vert }^2\\ =g\left(y^k\right)+\langle \nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right),y^{k+1}-y^k\rangle +\langle \tilde{\nabla }g\left(y^k\right),y^{k+1}-y^k\rangle +\frac{L_g}{2}{\Vert y^k-y^{k+1}\Vert }^2.\end{array}$ (9)

显然，

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)={ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)+g\left(y^k\right)-g\left(y^{k+1}\right)+\langle {\lambda }^k,B{y}^k-B{y}^{k+1}\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^k-b\Vert }^2-\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2,\end{array}$

结合公式(9)，可以得到：

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)\ge {ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)+\langle \nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right),y^k-y^{k+1}\rangle \\ -\frac{L_g}{2}{\Vert y^k-y^{k+1}\Vert }^2+\langle \tilde{\nabla }g\left(y^k\right),y^k-y^{k+1}\rangle +\langle {\lambda }^k,B{y}^k-B{y}^{k+1}\rangle \\ +\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^k-b\Vert }^2-\frac{\beta }{2}{\Vert A{x}^{k+1}+B{y}^{k+1}-b\Vert }^2.\end{array}$ (10)

利用迭代(4)的最优性条件：

$0\in \tilde{\nabla }g\left(y^k\right)+B^{\text{T}}{\lambda }^{k+\frac{1}{2}}+\beta B^{\text{T}}\left(A{x}^{k+1}+B{y}^{k+1}-b\right)+r\left(y^{k+1}-y^k\right),$

可得

$\langle \tilde{\nabla }g\left(y^k\right),y^k-y^{k+1}\rangle =\langle {\lambda }^{k+\frac{1}{2}},B{y}^{k+1}-B{y}^k\rangle +r{\Vert y^{k+1}-y^k\Vert }^2+\beta \langle A{x}^{k+1}+B{y}^{k+1}-b,B{y}^{k+1}-B{y}^k\rangle ,$ (11)

代入公式(10)，

$\begin{array}{l}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)\\ \ge {ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)+\langle \nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right),y^k-y^{k+1}\rangle +\left(r-\frac{L_g}{2}\right){\Vert y^k-y^{k+1}\Vert }^2\\ +\langle B{y}^k-B{y}^{k+1},{\lambda }^k-{\lambda }^{k+\frac{1}{2}}+\beta \left(A{x}^{k+1}-b\right)+\frac{\beta }{2}\left(B{y}^{k+1}+B{y}^k\right)-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right)\rangle ,\end{array}$

同时由于

${ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)={ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)+\langle {\lambda }^k-{\lambda }^{k+1},A{x}^{k+1}+B{y}^{k+1}-b\rangle .$ (12)

将公式(8) (11) (12)相加，并由h是${\mu }_h$ 强凸可得：

$\begin{array}{l}{ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)\\ \le {ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)-\frac{\mu {\mu }_h}{2}\Vert x^{k+1}-x^k\Vert +\langle \nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right),y^{k+1}-y^k\rangle \\ +\left(\frac{L_g}{2}-r\right){\Vert y^{k+1}-y^k\Vert }^2+\frac{1}{\left(s+1\right)\beta }{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2+\left(\frac{\beta }{2}-\frac{\beta }{s+1}\right){\Vert B{y}^{k+1}-B{y}^k\Vert }^2.\end{array}$ (13)

将迭代(5)代入迭代(4)，并取一阶最优性条件得到$0=\tilde{\nabla }g\left(y^k\right)+B^{\text{T}}{\lambda }^{k+1}+r\left(y^{k+1}-y^k\right)$。

由此可得

$\begin{array}{l}\Vert {\lambda }^{k+1}-{\lambda }^k\Vert \le \frac{1}{\sqrt{{\lambda }_{\min }\left(B^{\text{T}}B\right)}}\Vert B^{\text{T}}\left({\lambda }^{k+1}-{\lambda }^k\right)\Vert \\ \le \frac{1}{\sqrt{{\lambda }_{\min }\left(B^{\text{T}}B\right)}}[\Vert \tilde{\nabla }g\left(y^{k-1}\right)-\nabla g\left(y^{k-1}\right)\Vert +\Vert \nabla g\left(y^{k-1}\right)-\nabla g\left(y^k\right)\Vert \\ +\Vert \nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right)\Vert +r\Vert y^k-y^{k-1}\Vert +r\Vert y^{k+1}-y^k\Vert ].\end{array}$ (14)

利用g是$L_g$ 光滑的，从而有：

$\begin{array}{l}{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2\le \frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)}[{\Vert \tilde{\nabla }g\left(y^{k-1}\right)-\nabla g\left(y^{k-1}\right)\Vert }^2+{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2\\ +{\left(L_g+r\right)}^2{\Vert y^k-y^{k-1}\Vert }^2+r^2{\Vert y^k-y^{k+1}\Vert }^2].\end{array}$ (15)

将公式(15)代入公式(13)并结合对于任意$t_1>0$ ，可得

$\begin{array}{l}{ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)\\ \le {ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)-\frac{\mu {\mu }_h}{2}{\Vert x^{k+1}-x^k\Vert }^2+G_1{\Vert y^{k+1}-y^k\Vert }^2+\frac{4{\left(L_g+r\right)}^2}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }{\Vert y^k-y^{k-1}\Vert }^2\\ +\left[\frac{t_1}{2}+\frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right]{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2+\frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }{\Vert \tilde{\nabla }g\left(y^{k-1}\right)-\nabla g\left(y^{k-1}\right)\Vert }^2.\end{array}$(16)

其中，$G_1=\frac{4r^2}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }+\frac{L_g}{2}-r+\frac{1}{2t_1}-\left(-\frac{1}{2}\beta +\frac{\beta }{s+1}\right){\lambda }_{\min }\left(B^{\text{T}}B\right)$ 。结合定义3.1中的均方误差有界性：

$\begin{array}{l}{\mathbb{E}}_k{ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)+\frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }{\mathbb{E}}_k{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2+\frac{\mu {\mu }_h}{2}{\mathbb{E}}_k{\Vert x^{k+1}-x^k\Vert }^2\\ +G{\mathbb{E}}_k{\Vert y^{k+1}-y^k\Vert }^2+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right){\mathbb{E}}_k{\Upsilon }_{k+1}\\ \le {ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)+\frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }{\Vert \tilde{\nabla }g\left(y^{k-1}\right)-\nabla g\left(y^{k-1}\right)\Vert }^2+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2\\ +G{\Vert y^k-y^{k-1}\Vert }^2+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right){\Upsilon }_k-\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2\\ -\left[G-\frac{4{\left(L_g+r\right)}^2}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }-\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right)\left(\frac{V_{\Upsilon }}{\rho }+V_1\right)\right]{\Vert y^k-y^{k-1}\Vert }^2,\end{array}$(17)

结合

$\begin{array}{l}{\Psi }_k={ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)+\frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }{\Vert \tilde{\nabla }g\left(y^{k-1}\right)-\nabla g\left(y^{k-1}\right)\Vert }^2+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2\\ +G{\Vert y^k-y^{k-1}\Vert }^2+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{{\lambda }_{\min }\left(B^{\text{T}}B\right)\left(s+1\right)\beta }\right){\Upsilon }_k,\end{array}$(18)

有以下不等式成立：

${\mathbb{E}}_k\left[{\Psi }_{k+1}+\tilde{\eta }{\Vert y^k-y^{k-1}\Vert }^2+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2\right]\le {\Psi }_k.$ (19)

(ii) 对公式(19)两边取期望，得到

$\mathbb{E}{\Psi }_{k+1}\le \mathbb{E}{\Psi }_k-\tilde{\eta }\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2-\frac{\mu {\mu }_h}{2}\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2.$

将上述不等式中k从零到T − 1求和，由于$\underset{\_}{\Phi }=\inf \left\{f\left(x\right)+g\left(y\right)\right\}>-\infty$ ，从而有$\underset{\_}{\Phi }=\inf \left\{\Phi \left(X^k\right)\right\}>-\infty$ ，

$\frac{\mu {\mu }_h}{2}{\displaystyle \sum _{k=0}^{T-1}\mathbb{E}}{\Vert x^k-x^{k-1}\Vert }^2+\tilde{\eta }{\displaystyle \sum _{k=0}^{T-1}\mathbb{E}}{\Vert y^k-y^{k-1}\Vert }^2\le \mathbb{E}{\Psi }_0-\mathbb{E}{\Psi }_T\le {\Psi }_0-\underset{\_}{\Phi }<+\infty ,$

令$T\to +\infty$ ，可得序列$\mathbb{E}{\Vert x^k-x^{k+1}\Vert }^2$ 和$\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2$ 均为可和的，且

$\underset{k\to \infty }{\lim }\mathbb{E}\Vert x^k-x^{k-1}\Vert =0,\underset{k\to \infty }{\lim }\mathbb{E}\Vert y^k-y^{k-1}\Vert =0.$

从关系式(15)与方差缩减算子中的均方误差有界性可得

$\begin{array}{l}\mathbb{E}{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2\le \frac{4}{{\lambda }_{\min }\left(B^{\text{T}}B\right)}\mathbb{E}[{\Upsilon }_{k-1}+2V_1{\Vert y^k-y^{k-1}\Vert }^2+V_1{\Vert y^{k-1}-y^{k-2}\Vert }^2\\ +V_1{\Vert y^{k+1}-y^k\Vert }^2+{\left(L_g+r\right)}^2{\Vert y^k-y^{k-1}\Vert }^2+r^2{\Vert y^k-y^{k+1}\Vert }^2].\end{array}$

因此有$\underset{k\to \infty }{\lim }\mathbb{E}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert =0$ 。

(iii) 由(i)可得

${\mathbb{E}}_k\left[{\Psi }_{k+1}+\tilde{\eta }{\Vert y^k-y^{k-1}\Vert }^2+\frac{\mu {\mu }_h}{2}{\Vert x^k-x^{k-1}\Vert }^2\right]\le {\Psi }_k.$

上鞅收敛定理表明${\displaystyle \sum _{k=1}^{+\infty }{\Vert x^k-x^{k-1}\Vert }^2}<+\infty ,{\displaystyle \sum _{k=1}^{+\infty }{\Vert y^k-y^{k-1}\Vert }^2}<+\infty$ 几乎必然成立。因此$\underset{k\to \infty }{\lim }\Vert x^k-x^{k-1}\Vert =0,\underset{k\to \infty }{\lim }\Vert y^k-y^{k-1}\Vert =0$ 几乎必然成立。上鞅收敛定理还保证了${\Psi }_k$ 几乎必然收敛到一个有限值${\Phi }^{*}$ ，并有$\underset{k\to \infty }{\lim }\mathbb{E}{\Psi }_k=\underset{k\to \infty }{\lim }\mathbb{E}\Phi \left(X^k\right)={\Phi }^{*}\in \left[\underset{\_}{\Phi },\infty \right)$ 成立。 £

命题3.3 设假设3.1成立。令${\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}}_{k\in \mathbb{N}}$ 为随机镜像下降对称交替方向乘子法算法生成的序列，且假设该序列有界。对于所有$k\ge 0$ ，定义如下向量：

${\zeta }_x^k=A^{\text{T}}\left({\lambda }^k-{\lambda }^{k-1}\right)+\beta A^{\text{T}}\left(B{y}^k-B{y}^{k-1}\right)+\mu {\mu }_h\left(x^k-x^{k-1}\right)-\mu \left(\nabla h\left(x^k\right)-\nabla h\left(x^{k-1}\right)\right),$ (20)

$\begin{array}{l}{\zeta }_y^k=\left(\nabla g\left(y^k\right)-\tilde{\nabla }g\left(y^k\right)\right)-\left(B^{\text{T}}{\lambda }^{k+1}-B^{\text{T}}{\lambda }^k\right)+\frac{1}{s+1}\left(B^{\text{T}}{\lambda }^k-B^{\text{T}}{\lambda }^{k-1}\right)\\ +\frac{\left(s+1\right)\beta -\beta }{s+1}\left(B^{\text{T}}B{y}^k-B^{\text{T}}B{y}^{k-1}\right)+2G\left(y^k-y^{k-1}\right)-r\left(y^{k+1}-y^k\right),\end{array}$(21)

${\zeta }_{\lambda }^k=\frac{1}{\left(s+1\right)\beta }\left({\lambda }^k-{\lambda }^{k-1}\right)+\frac{s}{s+1}\left(B{y}^k-B{y}^{k-1}\right),{\zeta }_{x^{\prime }}^k=-\mu {\mu }_h\left(x^k-x^{k-1}\right),{\zeta }_{y^{\prime }}^k=-2G\left(y^k-y^{k-1}\right),$ (22)

对于$\left({\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\right)$ ，有以下性质成立：

(i) $\left({\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\right)\in \partial \Phi \left(X^k\right)$ ，存在正常数P，使得对于任意$k\ge 1$ ，有：

$\begin{array}{l}{\mathbb{E}}_k\Vert \left({\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\right)\Vert \le P{\mathbb{E}}_k(\Vert y^{k+1}-y^k\Vert +\Vert y^k-y^{k-1}\Vert +\Vert {\lambda }^{k+1}-{\lambda }^k\Vert \\ +\Vert {\lambda }^k-{\lambda }^{k-1}\Vert +\Vert x^k-x^{k-1}\Vert )+{\Gamma }_k,\end{array}$

(ii) $\mathbb{E}\text{dist}\left(0,\partial \Phi \left(X^k\right)\right)\to 0$ 。

证明：(i) 由$\Phi$ 的定义，对于任意$k\ge 1$ 有：

${\partial }_x{\Phi }^k=\partial f\left(x^k\right)+A^{\text{T}}{\lambda }^k+\beta A^{\text{T}}\left(A{x}^k+B{y}^k-b\right)+\mu {\mu }_h\left(x^k-x^{k-1}\right),$ (23)

${\partial }_y{\Phi }^k=\nabla g\left(y^k\right)+B^{\text{T}}{\lambda }^k+\beta B^{\text{T}}\left(A{x}^k+B{y}^k-b\right)+2G\left(y^k-y^{k-1}\right),$ (24)

${\partial }_{\lambda }{\Phi }^k=A{x}^k+B{y}^k-b,{\partial }_{x^{\prime }}{\Phi }^k=-\mu {\mu }_h\left(x^k-x^{k-1}\right),{\partial }_{y^{\prime }}{\Phi }^k=-2G\left(y^k-y^{k-1}\right).$ (25)

由(2)的一阶最优性条件可得$-A^{\text{T}}{\lambda }^{k-1}-\beta A^{\text{T}}\left(A{x}^k+B{y}^{k-1}-b\right)-\mu \left(\nabla h\left(x^k\right)-\nabla h\left(x^{k-1}\right)\right)\in \partial f\left(x^k\right)$ ，将其代入公式(23)可得${\zeta }_x^k\in {\partial }_x\Phi \left(X^k\right)$ 。同样，结合$0=\tilde{\nabla }g\left(y^k\right)+B^{\text{T}}{\lambda }^{k+1}+r\left(y^{k+1}-y^k\right)$和公式，可以得到${\zeta }_y^k\in {\partial }_y\Phi \left(X^k\right)$ 。通过(6)，也可以得到${\zeta }_{\lambda }^k\in {\partial }_{\lambda }\Phi \left(X^k\right)$ ，从而有$\left({\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\right)\in \partial \Phi \left(X^k\right)$ 。

根据h是$L_h$ 光滑的，结合定义3.1中的均方误差(MSE)有界以及等式(23)~(25)，我们可以推导出以下式子成立：

${\mathbb{E}}_k\Vert {\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\Vert \le P{\mathbb{E}}_k\left(\Vert {\lambda }^{k+1}-{\lambda }^k\Vert +\Vert {\lambda }^k-{\lambda }^{k-1}\Vert +\Vert y^{k+1}-y^k\Vert +\Vert y^k-y^{k-1}\Vert +\Vert x^k-x^{k-1}\Vert \right),$

其中

$P=\max \left\{\Vert B\Vert ,2\mu {\mu }_h+{\mu }_h{L}_h,V_2+r,\Vert A\Vert +\frac{\Vert B\Vert }{s+1}+\frac{1}{\left(s+1\right)\beta },\Vert \beta A^{\text{T}}B\Vert +\frac{s\beta }{s+1}\Vert B^{\text{T}}B\Vert +4\Vert G\Vert +\frac{s}{s+1}\Vert B\Vert +V_2\right\}.$

(ii) 由于

${\mathbb{E}}_k\Vert {\zeta }_x^k,{\zeta }_y^k,{\zeta }_{\lambda }^k,{\zeta }_{x^{\prime }}^k,{\zeta }_{y^{\prime }}^k\Vert \le P{\mathbb{E}}_k\left(\Vert {\lambda }^{k+1}-{\lambda }^k\Vert +\Vert {\lambda }^k-{\lambda }^{k-1}\Vert +\Vert y^{k+1}-y^k\Vert +\Vert y^k-y^{k-1}\Vert +\Vert x^k-x^{k-1}\Vert \right).$

由引理3.2，得$\mathbb{E}\Vert x^k-x^{k-1}\Vert \to 0$ ，$\mathbb{E}\Vert y^k-y^{k-1}\Vert \to 0$ ，$\mathbb{E}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert \to 0$ ，因此结论成立。 £

记由随机镜像下降对称交替方向乘子法算法生成的序列${\left\{X^k\right\}}_{k\in \mathbb{N}}$ 的极限点集合为${\Omega }^{*}$ ，即：

${\Omega }^{*}=\left\{X^{*}:存在�增的整�序列{\left\{k_q\right\}}_{q\in \mathbb{N}},q\to +\infty �X^{k_q}\to X^{*}\right\}$

定理3.4 设假设3.1成立。令${\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}}_{k\in \mathbb{N}}$ 为随机镜像下降对称交替方向乘子法算法生成的序列，且假设该序列有界。则以下结论成立：

(i) ${\Omega }^{*}$ 非空，几乎必然是紧的且连通的。此外，$\text{dist}\left(X^k,{\Omega }^{*}\right)\to 0$ 几乎必然成立；

(ii) 对于所有$X^{*}\in {\Omega }^{*}$ ，有，并且$\mathbb{E}\Phi \left(X^{*}\right)={\Phi }^{*}$ 。

证明：(i) 详细证明参考文献[22]。

(ii) 取任意点$X^{*}\in {\Omega }^{*}$ ，存在子序列${\left\{X^{k_q}\right\}}_{q\in \mathbb{N}}$ 满足：当$q\to +\infty$ 时，$X^{k_q}\to X^{*}$ 。由于f是适当下半连续函数，因此：

$\underset{q\to +\infty }{\lim \inf }f\left(x^{k_q}\right)\ge f\left(x^{*}\right).$

将$x=x^{*}$ 代入迭代公式(2)，结合等式(6)和$\Vert {\lambda }^{k_q}-{\lambda }^{k_q-1}\Vert \to 0$ ，可以得到$A{x}^{k_q}+B{y}^{k_q-1}-b\to 0$ 。令$k=k_q-1$ ，并取极限$q\to +\infty$ 可得$\underset{q\to +\infty }{\lim \sup }f\left(x^{k_q}\right)\le f\left(x^{*}\right)$ 。结合$\underset{q\to +\infty }{\lim \inf }f\left(x^{k_q}\right)\ge f\left(x^{*}\right)$ 可得当$q\to +\infty$ 时$f\left(x^{k_q}\right)\to f\left(x^{*}\right)$ 。又g是连续函数，得${\lim }_{q\to +\infty }\Phi \left(X^{k_q}\right)=\Phi \left(X^{*}\right)$ 。由命题3.3和$\partial \Phi$ 的闭性，可以得到：。

最后，证明$\Phi$ 在${\Omega }^{*}$ 上具有常数期望值。取任意点$X^{*}\in {\Omega }^{*}$ ，存在子序列${\left\{X^{k_q}\right\}}_{q\in \mathbb{N}}$ 满足当$q\to +\infty$ 时$X^{k_q}\to X^{*}$ 。根据引理3.2，$\underset{k\to +\infty }{\lim }\mathbb{E}\Phi \left(X^k\right)={\Phi }^{*}$ ，这意味着$\underset{q\to +\infty }{\lim }\mathbb{E}\Phi \left(X^{k_q}\right)={\Phi }^{*}$ 。结合$q\to +\infty$ 时$\Phi \left(X^{k_q}\right)\to \Phi \left(X^{*}\right)$ ，对于任意$X^{*}\in {\Omega }^{*}$ ，有$\mathbb{E}\Phi \left(X^{*}\right)={\Phi }^{*}$ 。 £

定理3.5 设假设3.1成立。令${\{(x^k,y^k,{\lambda }^k)\}}_{k\in \mathbb{N}}$ 为随机镜像下降对称交替方向乘子法算法生成的序列，且假设该序列有界。设$\Phi$ 为一个半代数函数，则存在常数$k_1$ ，$a>0$ ，$\theta \in \left[0,1\right)$ 和一个去奇异化函数${\varphi }_0=a{r}^{1-\theta }$ 使得以下不等式成立：

${{\varphi }^{\prime }}_0\left(\mathbb{E}\left[\Phi \left(X^k\right)-{\Phi }_k^{*}\right]\right)\mathbb{E}\text{dist}\left(0,\partial \Phi \left(X^k\right)\right)\ge 1,\forall k\ge k_1,$

其中${\Phi }_k^{*}$ 是一个单调递增的序列，收敛于某个$\mathbb{E}\Phi \left(X^{*}\right)$ ，其中$X^{*}\in {\Omega }^{*}$ 。

定理3.6 设假设3.1成立。令${\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}}_{k\in \mathbb{N}}$ 为随机镜像下降对称交替方向乘子法算法生成的序列，且假设该序列有界。设$\Phi$ 为一个半代数函数，则有

${\displaystyle \sum _{k=0}^{+\infty }\mathbb{E}}\Vert x^{k+1}-x^k\Vert <+\infty ,{\displaystyle \sum _{k=0}^{+\infty }\mathbb{E}}\Vert y^{k+1}-y^k\Vert <+\infty ,{\displaystyle \sum _{k=l}^{+\infty }\mathbb{E}}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert <+\infty .$

证明：根据引理3.2，$\underset{k\to +\infty }{\lim }\mathbb{E}{\Psi }_k=\underset{k\to +\infty }{\lim }\mathbb{E}\Phi \left(X^k\right)={\Phi }^{*}$ 成立。因此，我们需要考虑以下两种情况。

第一种情况，即存在整数$\overline{k}$ ，使得对于任意$k\ge \overline{k}$ ，有$\mathbb{E}{\Psi }_k={\Phi }^{*}$ 成立。因此，对于任意$k\ge \overline{k}$ ，由詹森不等式可得

$\mathbb{E}\Vert x^k-x^{k+1}\Vert \le \sqrt{\mathbb{E}{\Vert x^k-x^{k+1}\Vert }^2}=0,\mathbb{E}\Vert y^k-y^{k+1}\Vert \le \sqrt{\mathbb{E}{\Vert y^k-y^{k+1}\Vert }^2}=0,\mathbb{E}\Vert {\lambda }^k-{\lambda }^{k+1}\Vert \le \sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2}=0.$

此时结论自然成立。

另一种情况，即对于所有$k\ge 0$ ，都有$\mathbb{E}{\Psi }_k>{\Phi }^{*}$ 。命题3.3给出了的一个上界：

(26)

其中，最后一个不等式是由$\mathbb{E}{\Gamma }_k=\mathbb{E}{\displaystyle \sum _{i=1}^s\Vert v_k^i\Vert }\le \mathbb{E}\sqrt{s{\displaystyle \sum _{i=1}^s{\Vert v_k^i\Vert }^2}}\le \sqrt{s\mathbb{E}{\Upsilon }_k}$ 得到的。下面基于${\Upsilon }_{k-1}\ge 0$ ，$V_{\Upsilon }\ge 0$ ，以及$\rho \in \left(0,1\right]$ ，$\sqrt{1-\rho }=1-\frac{\rho }{2}-{\displaystyle \sum _{k=2}^{+\infty }\frac{\left(2k-3\right)!!}{\left(2k\right)!!}}{\rho }^k$ 以及估计量的几何衰减性质对$\sqrt{\mathbb{E}{\Upsilon }_k}$ 进行更精确的估计，

$\begin{array}{l}\sqrt{\mathbb{E}{\Upsilon }_k}\le \sqrt{\left(1-\rho \right)\mathbb{E}{\Upsilon }_{k-1}+V_{\Upsilon }\mathbb{E}\left[{\Vert y^k-y^{k-1}\Vert }^2+{\Vert y^{k-1}-y^{k-2}\Vert }^2\right]}\\ \le \left(1-\frac{\rho }{2}\right)\sqrt{\mathbb{E}{\Upsilon }_{k-1}}+\sqrt{V_{\Upsilon }}\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}+\sqrt{V_{\Upsilon }}\sqrt{\mathbb{E}{\Vert y^{k-1}-y^{k-2}\Vert }^2},\end{array}$

进而$\sqrt{\mathbb{E}{\Upsilon }_k}\le \frac{2}{\rho }\left(\sqrt{\mathbb{E}{\Upsilon }_k}-\sqrt{\mathbb{E}{\Upsilon }_{k+1}}\right)+\frac{2\sqrt{V_{\Upsilon }}}{\rho }\left(\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}\right)$ 。

将公式$\sqrt{\mathbb{E}{\Upsilon }_k}\le \frac{2}{\rho }\left(\sqrt{\mathbb{E}{\Upsilon }_k}-\sqrt{\mathbb{E}{\Upsilon }_{k+1}}\right)+\frac{2\sqrt{V_{\Upsilon }}}{\rho }\left(\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}\right)$ 代入公式(32)中，得到：

令

$\begin{array}{l}{K}_1=P+\frac{2\sqrt{s{V}_{\Upsilon }}}{\rho },\\ C_k=\frac{2\sqrt{s}}{\rho }\left(\sqrt{\mathbb{E}{\Upsilon }_k}-\sqrt{\mathbb{E}{\Upsilon }_{k+1}}\right)+K_1(\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}\\ +\sqrt{\mathbb{E}{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2}+\sqrt{\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2}),\end{array}$

可得存在一个正常数$P_1$ ，使得对于任意$k\ge k_0$ ，

$C_k\le P_1\left(\sqrt{\mathbb{E}{\Upsilon }_k}-\sqrt{\mathbb{E}{\Upsilon }_{k+1}}\right)+P_1\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+P_1\sqrt{\mathbb{E}{\Vert x^{k+1}-y^{k+1}\Vert }^2}-2P_1\sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2},$

此外可以得到。

根据引理3.5，对于任意$k\ge k_1$ ，${{\varphi }^{\prime }}_0\left(\mathbb{E}\left[\Phi \left(X^k\right)-{\Phi }_k^{*}\right]\right)C_k\ge 1$ ，根据$C_k$ 的定义有：

$\begin{array}{l}{C}_k\ge c_1(\sqrt{\mathbb{E}{\Upsilon }_k}+\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}+\sqrt{\mathbb{E}{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2}\\ +\sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2}+\sqrt{\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2})\\ \ge c_1\left(\sqrt{\mathbb{E}{\Upsilon }_k}+\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}\right),\end{array}$

其中$c_1>0$ 。结合$\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2\to 0$ ，$\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2\to 0$ ，$\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2\to 0$ 且$\theta \in \left[0,1\right)$ ，可知存在正常数$k_2$ 和正常数$c_2,c_3$ 使得对于所有$k\ge k_2$ ，有：

$\begin{array}{l}{\left(\mathbb{E}\left[\frac{4}{\left(s+1\right)\beta {\lambda }_{\min }}{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right){\Upsilon }_{k+1}\right]\right)}^{\theta }\\ \le {\left(\mathbb{E}\left[\frac{4}{\left(s+1\right)\beta {\lambda }_{\min }}{\Upsilon }_k+\frac{4V_1}{\left(s+1\right)\beta {\lambda }_{\min }}\left({\Vert y^{k+1}-y^k\Vert }^2+{\Vert y^k-y^{k-1}\Vert }^2\right)+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right){\Upsilon }_{k+1}\right]\right)}^{\theta }\\ \le (\mathbb{E}[\left(\frac{4}{\left(s+1\right)\beta {\lambda }_{\min }}+\frac{1-\rho }{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right)\right){\Upsilon }_k\\ +{\left(\frac{4V_1}{\left(s+1\right)\beta {\lambda }_{\min }}+\frac{V_{\Upsilon }}{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right)\right)\left({\Vert y^{k+1}-y^k\Vert }^2+{\Vert y^k-y^{k-1}\Vert }^2\right)])}^{\theta }\\ \le c_2{\left(\sqrt{\mathbb{E}{{\rm Y}}_k}+\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}+\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}\right)}^{\theta }\le \frac{c_2{c}_3}{c_1^{\theta }}{C}_k,\end{array}$

定义${\overline{C}}_k=\frac{4}{\left(s+1\right)\beta {\lambda }_{\min }}{\Vert \tilde{\nabla }g\left(y^k\right)-\nabla g\left(y^k\right)\Vert }^2+\frac{1}{\rho }\left(\frac{t_1}{2}+\frac{8}{\left(s+1\right)\beta {\lambda }_{\min }\left(B^{\text{T}}B\right)}\right){\Upsilon }_{k+1}$，由于${\left(\mathbb{E}{\overline{C}}_k\right)}^{\theta }$ 比$C_k$ 小，从而存在常数$\widehat{c}<\frac{c_2{c}_3}{c_1^{\theta }}$ 使得$\frac{\widehat{c}a\left(1-\theta \right)C_k}{{\left(\mathbb{E}\left[\Phi \left(X^k\right)-{\Phi }_k^{*}\right]\right)}^{\theta }+{\left(\mathbb{E}{\overline{C}}_k\right)}^{\theta }}\ge 1$ ，已知对任意的$a,b>0$ ，$\theta \in \left[0,1\right)$ ，有${\left(a+b\right)}^{\theta }\le a^{\theta }+b^{\theta }$ 成立，且$\frac{\widehat{c}a\left(1-\theta \right)C_k}{{\left(\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}\right]\right)}^{\theta }}=\frac{\widehat{c}a\left(1-\theta \right)C_k}{{\left(\mathbb{E}\left[\Phi \left(X^k\right)-{\Phi }_k^{*}+{\overline{C}}_k\right]\right)}^{\theta }}\ge \frac{\widehat{c}a\left(1-\theta \right)C_k}{{\left(\mathbb{E}\left[\Phi \left(X^k\right)-{\Phi }_k^{*}\right]\right)}^{\theta }+{\left(\mathbb{E}{\overline{C}}_k\right)}^{\theta }}\ge 1$ ，因此存在$\varphi =\widehat{c}a{r}^{1-\theta }$ 与$l=\max \left\{k_0,k_1,k_2\right\}$ ，使得

${\varphi }^{\prime }\left(\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}\right]\right)C_k\ge 1,\forall k\ge l.$ (27)

结合$\varphi$ 的凹性，以及${\Phi }_k^{*}$ 是单调递增的，

$\begin{array}{l}\varphi \left(\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}\right]\right)-\varphi \left(\mathbb{E}\left[{\Psi }_{k+1}-{\Phi }_{k+1}^{*}\right]\right)\\ \ge {\varphi }^{\prime }\left(\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}\right]\right)\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}+{\Phi }_{k+1}^{*}-{\Psi }_{k+1}\right]\\ \ge {\varphi }^{\prime }\left(\mathbb{E}\left[{\Psi }_k-{\Phi }_k^{*}\right]\right)\mathbb{E}\left[{\Psi }_k-{\Psi }_{k+1}\right],\end{array}$ (28)

令${\Delta }_{p,q}=\varphi \left(\mathbb{E}\left[{\Psi }_p-{\Phi }_p^{*}\right]\right)-\varphi \left(\mathbb{E}\left[{\Psi }_q-{\Phi }_q^{*}\right]\right)$ ，结合公式(19) (27)和(28)，

${\Delta }_{k,k+1}{C}_k\ge \tilde{\eta }\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2+\frac{\mu {\mu }_h}{2}\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2\ge \tilde{K}\left(\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2+\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2\right),$

其中$\tilde{K}=\min \left\{\tilde{\eta },\frac{\mu {\mu }_h}{2}\right\}$ 。因此，

$2\sqrt{\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2+\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}\le 2\sqrt{\frac{1}{\tilde{K}}{\Delta }_{k,k+1}{C}_k}\le \frac{C_k}{2P_1}+\frac{2P_1{\Delta }_{k,k+1}}{\tilde{K}}.$ (29)

将不等式(29)中k从l到K进行求和得到：

$\begin{array}{l}2{\displaystyle \sum _{k=l}^K\sqrt{\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2}}+2{\displaystyle \sum _{k=l}^K\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}}\\ \le {\displaystyle \sum _{k=l}^K\left(\frac{1}{2}\sqrt{\mathbb{E}{\Vert y^{k+1}-y^k\Vert }^2}+\frac{1}{2}\sqrt{\mathbb{E}{\Vert x^{k+1}-x^k\Vert }^2}-\sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2}\right)}\\ +\frac{1}{2}\left(\sqrt{\mathbb{E}{\Upsilon }_l}-\sqrt{\mathbb{E}{\Upsilon }_{K+1}}\right)+\frac{2P_1}{\tilde{K}}\varphi \left(\mathbb{E}\left[{\Psi }_l-{\Phi }_l^{*}\right]\right).\end{array}$

因此，

$\begin{array}{l}{\displaystyle \sum _{k=l}^K\mathbb{E}}\Vert x^k-x^{k-1}\Vert +{\displaystyle \sum _{k=l}^K\mathbb{E}}\Vert y^k-y^{k-1}\Vert +{\displaystyle \sum _{k=l}^K\mathbb{E}}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert \\ \le {\displaystyle \sum _{k=l}^K\sqrt{\mathbb{E}{\Vert x^k-x^{k-1}\Vert }^2}}+{\displaystyle \sum _{k=l}^K\sqrt{\mathbb{E}{\Vert y^k-y^{k-1}\Vert }^2}}+{\displaystyle \sum _{k=l}^K\sqrt{\mathbb{E}{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2}}\\ \le \frac{1}{2}\sqrt{\mathbb{E}{\Vert y^{K+1}-y^K\Vert }^2}-\frac{1}{2}\sqrt{\mathbb{E}{\Vert y^l-y^{l-1}\Vert }^2}+\frac{1}{2}\sqrt{\mathbb{E}{\Vert x^{K+1}-x^K\Vert }^2}\\ -\frac{1}{2}\sqrt{\mathbb{E}{\Vert x^l-x^{l-1}\Vert }^2}+\frac{1}{2}\left(\sqrt{\mathbb{E}{\Upsilon }_l}-\sqrt{\mathbb{E}{\Upsilon }_{K+1}}\right)+\frac{2P_1}{\tilde{K}}\varphi \left(\mathbb{E}\left[{\Psi }_l-{\Phi }_l^{*}\right]\right),\end{array}$ (30)

公式(30)中第一个不等式由詹森不等式得出。令$K\to +\infty$ ，

${\displaystyle \sum _{k=l}^{+\infty }\mathbb{E}}\Vert x^k-x^{k-1}\Vert <+\infty ,{\displaystyle \sum _{k=l}^{+\infty }\mathbb{E}}\Vert y^k-y^{k-1}\Vert <+\infty ,{\displaystyle \sum _{k=l}^{+\infty }\mathbb{E}}\Vert {\lambda }^k-{\lambda }^{k-1}\Vert <+\infty .$ £

4. 数值实验

本节中，我们研究算法1在图引导融合lasso问题上的数值性能。数值实验在MATLAB R2017a环境下，配置Intel Core i7-13700H处理器(2.40 GHz)和16 GB内存的64位电脑上进行。确定性对称ADMM记为SADMM，并分别将使用SGD、SARAH、SAGA、SVRG方差缩减随机梯度估计算子的SADMM分别记为SGD-SADMM、SARAH-SADMM、SAGA-SADMM、SVRG-SADMM。

给定一组训练样本${\left\{\left(a_i,b_i\right)\right\}}_{i=1}^n$ ，其中$a_i\in {ℝ}^m$ ，$b_i\in \left\{-1,+1\right\}$ ，$i\in \left\{1,2,\cdots ,n\right\}$ ，图引导的融合lasso如下：${\min }_y\frac{1}{n}{\displaystyle \sum _{i=1}^n{g}_i}\left(y\right)+{\lambda }_1{\Vert By\Vert }_1$ ，其中：$g_i\left(y\right)=\frac{1}{1+\exp \left(b_i{a}_i^{\top }y\right)}$ 是非凸非光滑的sigmoid损失函数，${\lambda }_1$ 是正则化参数。矩阵B的形式为$B=\left[G;I\right]$ ，其中G是通过稀疏逆协方差矩阵估计得到的[4]。在实验中，设定$g\left(y\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{g}_i}\left(y\right)$ ，$f\left(By\right)={\lambda }_1{\Vert By\Vert }_1$ 。令$n=1000$ ,$s=0.95$ ，$\beta =1$ ，$\mu =r=0.05$ ，${\lambda }_1=1\text{e}-5$ 。使用两个公开数据集[3]，如表1所示。并在图1、图2分别给出了损失函数随迭代次数与迭代时间变化关系图。

Table 1. Datasets for graph-guided fused lasso

表1. Graph-guided fused lasso数据集

数据集	训练集	测试集	分类
a8a	11,348	11,348	2
Ijcnn1	17,500	17,500	2

(a) ijcnn1 (b) a8a

Figure 1. Relationship between iteration number and loss function variation

图1. 迭代次数与损失函数变化关系图

(a) ijcnn1 (b) a8a

Figure 2. Relationship between CPU-time and loss function variation

图2. 迭代时间与损失函数变化关系图

在图1中，我们给出了不同方法在前40次迭代下损失函数的测试结果，结果显示在相同迭代次数下SARAH-ADMM算法损失函数的下降量最大。图2展示了SADMM与几种随机算法在相同时间内损失函数变化情况，我们可以观察到：SARAH-SADMM、SVRG-SADMM在相同时间内损失函数下降最大，而SAGA-SADMM、SGD-SADMM的表现相似，且都比SADMM效果显著。从而可得随机形式SADMM在图lasso问题上效果明显优于确定形式的SADMM。至此实验阐述了不同类型的方差缩减算子与对称ADMM在四个公开数据集上的数值表现，并且基于问题的特殊性将Bregman距离选取为二范数形式即可得到问题的显示解，相比于其他类型legendre函数选取的方式简单高效。

5. 结论

本文提出的“随机镜像下降对称交替方向乘子法”为求解带有等式约束的非凸非光滑优化问题提供了一种高效稳定的方案。理论分析表明，在目标函数满足半代数性质的条件下，算法生成的迭代序列全局收敛到原问题的驻点。数值实验进一步验证了该算法在实际应用中的高效性与稳定性。在之后的研究中考虑将广义惯性步加入文中的算法中，观察不同惯性步参数对数值效果的影响，进而与文中算法的数值效果进行对比。