随机邻近牛顿型交替极小化算法

Stochastic Proximity Newtonian Alternating Miniaturization Algorithm

摘要: 本文研究一类大规模有限和形式的非凸非光滑复合优化问题，其目标函数为适当下半连续凸函数与连续可微函数(有限和形式)之和。邻近交替线性极小化算法在求解这类问题上有显著优势，但考虑到针对大规模优化问题，该算法需在每一迭代计算全梯度，成本较高，故本文将目标函数光滑部分的随机梯度引入到已有算法，以降低算法的计算成本。此外，考虑到一阶算法在求解病态问题时速度较慢，故本文在算法中引入目标函数的二阶信息，提出了一种随机邻近牛顿型交替极小化算法。在适当的步长边界的基础上，我们建立了算法在期望意义下的全局收敛性。本文提出的随机邻近牛顿型交替极小化算法，不仅提升了算法在机器学习、统计学和图像处理等领域实际应用中的效率和实用性，也为非凸非光滑优化领域的理论发展提供了新的理论基础和算法框架。

Abstract: This article investigates a class of large-scale finite and structured nonconvex nonsmooth composite optimization problems, where the objective function is the sum of an appropriately lower semicontinuous convex function and a continuous differentiable function (finite and structured). The alternating linear minimization algorithm has significant advantages in solving such problems. However, considering the large-scale optimization problems, this algorithm requires computing the full gradient at each iteration, which is costly. Therefore, this article introduces the stochastic gradient of the smooth part of the objective function into the existing algorithm to reduce the computational cost. Additionally, considering that first-order algorithms are slow in solving ill-conditioned problems, this article incorporates the second-order information of the objective function into the algorithm and proposes a stochastic proximal Newton-type alternating minimization algorithm. Based on appropriate step size bounds, we establish the global convergence of the algorithm in the expected sense. The stochastic neighborhood Newton-type alternating minimization algorithm proposed in this paper not only improves the efficiency and practicability of the algorithm in practical applications in the fields of machine learning, statistics and image processing, but also provides a new theoretical foundation and algorithmic framework for the theoretical development in the field of nonconvex nonsmooth optimization.

1. 引言

1.1. 研究背景及意义

随着信息技术的高速发展，许多学科领域涌现出了许多大规模优化问题，因此对于优化问题的高效求解，是当今研究的热点问题之一。本文研究的是一类具有有限和形式的非凸非光滑复合优化问题，该问题的具体格式如下：

$\min \psi \left(x,y\right)=f\left(x\right)+g\left(y\right)+H\left(x,y\right),$ (1.1)

其中$f\left(x\right)$ 和$g\left(y\right)$ 是适当下半连续凸函数，$H\left(x,y\right)={\displaystyle \sum h_i}\left(x,y\right)\text{, }i=1,2,\cdots ,n$ 是连续可微函数。这类模型在许多领域都有应用，包括机器学习、统计学和图像处理等。典型的例子包括非负或稀疏矩阵分解[1]、稀疏(PCA) [2] [3]、鲁棒PCA [4]、最小二乘[5]和盲图像反卷积[6]等。下面我们给出稀疏非负矩阵分解(sparse-NMF)模型，该模型的具体形式为

$\min {\Vert A-XY\Vert }_F^2,X,Y\ge 0,{\Vert X_i\Vert }_0\le s,i=1,\cdots ,r,$

其中$X_i$ 表示X的第i列。在字典学习和稀疏编码中，X被称为系数为Y的学习字典。在该模型中，X上的稀疏性使用非凸$l_0$ 约束。模型可以表述为问题(1.1)的形式，具体地，我们假设$f\left(x\right)={\delta }_{{\Omega }_1}\left(X\right)$ ，${\Omega }_1=\left\{X\ge 0,{\Vert X_j\Vert }_0\le s,j=1,\cdots ,r\right\}$ ，$g\left(Y\right)={\delta }_{{\Omega }_2}\left(Y\right)$ ，${\Omega }_2=\left\{Y\ge 0\right\}$ ， $H\left(X,Y\right)={\displaystyle \sum h_i\left(X,Y\right)}={\displaystyle \sum {\left(e_p^{\text{T}}\left(A-XY\right)e_q\right)}^2}$ ，其中$e_j$ 是第j个元素为1，其他元素均为0的向量。形如问题(1.1)的有限和形式的非凸非光滑复合优化问题在机器学习，图像处理和计算机视觉等领域中存在广泛应用，因此研究计算成本低、收敛速度快的算法是很有必要的。

1.2. 研究现状

针对非凸非光滑复合优化问题(1.1)，一个经典的求解算法是交替极小化算法(alternating minimization, AM) [7]，当函数凸且连续可微时，若其中一个参数固定时，关于另外一个参数它是严格凸的，那么用这种方法生成的序列的每一个极限点都是的极小点。AM算法为一系列研究此问题的算法提供了理论或实践上的支撑。然而在许多实际问题中，目标函数通常不满足上述较为严格的条件。为克服收敛性条件较强的缺陷，一些学者通过在AM算法的子问题中引入邻近项，提出了PAM算法[8]，在非凸情形下，当目标函数满足KL性质时，该算法的收敛性分析已被建立。然而，PAM算法涉及两个函数和的邻近算子的计算，这通常是难以求解的。Bolte等人[9]通过将目标函数中的光滑部分进行线性化处理，提出了邻近交替线性极小化算法(Proximal alternating linearized minimization, PALM)，其具体迭代格式如下所示：

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

$y^{k+1}\in \arg \min \left\{g\left(y\right)+\langle {\nabla }_{y}H\left(x^{k+1},y^k\right),y-y^k\rangle +\frac{d_k}{2{\Vert y-y^k\Vert }^2}\right\}.$

需要说明的是，PALM算法中子问题通常有显式解或易于求解。在非凸情形下，Bolte等人在KL框架下证明了PALM算法的全局收敛性。本文正是围绕PALM算法的改进展开的。Bolte等人的工作为本文的研究提供了算法设计的灵感，展示了如何通过交替优化策略来处理非凸非光滑问题，而且他们的全局收敛性证明为本文的算法分析提供了理论基础。

针对非凸非光滑复合优化问题(1.1)，当n很大的时候，PALM算法在每次迭代计算成本将非常昂

贵，因为它需要涉及到对全梯度$\nabla H\left(x,y\right):=\frac{1}{n}{\displaystyle \sum _{i=1}^n\nabla h_i\left(x,y\right)}$ 的计算，这将导致较大的计算成本。为了克服这个问题，针对$f=g=0$ ，仅涉及变量x的情形，随机梯度算法(SGD) [10]被提出，但是SGD要求步长随迭代进程不断衰减到0以弥补随机梯度带来的方差。为提高SGD算法的求解效率，一系列方差缩减的随机梯度算法被提出，包括SVRG [11]，SAGA [12]，SARAH [13]等。随机梯度也被引入到邻近梯度算法，用以邻近梯度算法的降低计算成本，包括prox-SGD，prox-SVRG，prox-SAGA [14]和prox-SARAH [15]等。本文在处理大规模优化问题时，在设计算法的迭代步骤时引入随机梯度，大大降低计算成本。

近年来，针对非凸非光滑复合优化问题(1.1)，已有学者将随机梯度策略引入到PALM算法中，提出了一系列随机的PALM算法。具体的，Xu和Yin [16]首先将简单随机梯度下降法(SGD)与PALM相结合，提出了块随机梯度法(BSG)并在对目标函数$\psi$ 的一些较为苛刻的假设条件下，证明了BSG方法的收敛性。基于此，Driggs等人[17]提出了一种随机邻近交替线性极小化(SPRING)的方法，其中他们使用了方差减少的随机梯度算法，而不是BSG方法中使用的简单的SGD算法。数值实验表明，SPRING的收敛速度比BSG方法快。值得注意的是，与Xu和Yin的先前工作相比，SPRING的收敛性是在对目标函数更弱的假设下建立的。

然而，针对病态问题，上述一阶算法存在收敛速度较慢的问题。一个自然的想法是在算法中引入目标函数的二阶信息，以提升算法的求解速度。针对邻近梯度算法，Yang等人[18]提出了一个随机外推拟牛顿算法(stochastic extra-step quasi-Newton method)，并证明了该算法在期望意义下的次线性收敛率。本文受到了他们方法的启发，在算法中通过残差方程引入目标函数的二阶信息，这些策略有助于提高算法的收敛速度。

本文扩展了PALM算法，通过引入随机梯度和二阶信息，提出了随机邻近牛顿型交替极小化算法。在计算效率和收敛速度上都有显著提升，这对于解决大规模优化问题尤为重要。

1.3. 本文的动机与贡献

考虑到一阶算法在处理病态问题时，收敛速度较慢，甚至有时不收敛。针对非凸非光滑复合优化问题(1.1)，我们希望引入高阶信息以提升一阶算法的收敛速度，此外引入随机梯度算法以实现计算量的降低。具体的，本文将随机邻近牛顿型算法与邻近交替线性极小化算法相结合，提出了随机邻近牛顿型交替极小化算法，并对该算法的收敛性分析进行了证明。

1.4. 文章框架

本文框架如下，在第二节中，给出了本文所需要用到的基本符号、定义以及相关引理。在第三节中，我们给出了随机邻近牛顿型交替极小化算法的具体迭代格式，并给出算法在基本假设下的收敛性分析。在第四节，我们进行了总结。

2. 预备知识

纸型

为便于下文研究本文所提出算法的收敛性，本节将介绍文中涉及到的符号、定义以及相关引理。首先，我们对文中所涉及到的符号做出如下定义：用$\langle \cdot ,\cdot \rangle$ 和$\Vert \cdot \Vert :={\Vert \cdot \Vert }_2$ 表示标准欧几里得内积和范数。对称正定$n\times n$ 矩阵的集合用$S_{++}^n$ 表示。对于给定矩阵$\Lambda \in S_{++}^n$ ，我们定义内积${\langle x,y\rangle }_{\Lambda }:=\langle x,\Lambda y\rangle =\langle \Lambda x,y\rangle$ ，${\Vert x\Vert }_{\Lambda }:=\sqrt{{\langle x,x\rangle }_{\Lambda }}$ 。对于任意$n\in \mathbb{N}$ ，我们令$\left[n\right]:=\left\{1,\cdots ,n\right\}$ ，${\left[n\right]}_0=\left\{0\right\}\cup \left[n\right]$ 。设$\left(\Omega ,\text{F},\text{P}\right)$ 为概率空间。我们将使用大写字母来描述随机变量$X:\Omega \to {ℝ}^n$ 和$Y:\Omega \to {ℝ}^n$ 。而小写字母通常保留给随机变量$x:\Omega \to {ℝ}^n$ 和$y:\Omega \to {ℝ}^n$ 。我们用$L^p\left(\Omega \right):=L^p\left(\Omega ,{\rm P}\right)$ ，$p\in \left[1,\infty \right]$ 来表示Ω上的标准$L^p$ 空间。我们用$X\in \text{F}$ 表示X是可测量的。此外，$\sigma \left(X^1,\cdots ,X^k\right)$ 表示由随机变量族$X^1,\cdots ,X^k$ 生成。对于随机变量$X\in L^1\left(\Omega \right)$ 和子$\sigma$ 代数$\text{H}\subseteq \text{F}$ ，给定H的X的条件期望记为${\rm E}\left[X|\text{H}\right]$ 。我们使用缩写“a.e.”和“a.s.”，分别代表“几乎处处”和“几乎一定”。

定义2.1 (凸函数的次微分) 设$f:{ℝ}^n\to ℝ\cup \left\{+\infty \right\}$ 为适当下半连续凸函数，对$x\in \mathrm{dom}f$ ，函数f在点x处的次微分记作$\partial f\left(x\right)$ ，定义为所有满足下述条件的$u\in {ℝ}^n$ 所构成的集合：

$f\left(y\right)\ge f\left(x\right)+\langle u,y-x\rangle ,\forall y\in {ℝ}^n.$

若$x\notin \mathrm{dom}f$ ，定义f在该点的次微分$\partial f\left(x\right)=\varnothing$ 。

定义2.2 (L-光滑) 对于可微函数$f:{ℝ}^n\to ℝ$ ，若存在常数$L>0$ ，使其满足下列不等式

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in {ℝ}^n.$

则称函数f是梯度Lipschitz连续的，其中L为Lipschitz常数。

引理2.1 (下降引理) 函数$f:{ℝ}^n\to ℝ$ 是可微的且L-光滑(L > 0)，则它满足下列不等式：

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

3. 随机邻近牛顿型交替极小化算法及其收敛性分析

针对大规模非凸非光滑复合优化问题(1.1)，许多确定型一阶算法已被设计用以对其进行求解。但确定型算法由于计算量较大导致计算成本昂贵，如PALM算法在处理有限和形式的非凸非光滑复合优化问题时，需计算光滑部分函数的所有梯度，这将导致较大的计算成本。此外，由于一阶算法在求解病态问题时，求解速度较慢，甚至不收敛，因此将二阶信息引入到算法中，以实现算法的快速高效求解，也是本文需要考虑的一点。

具体的，在算法设计方面，为降低计算成本，提高算法的求解速度，本文将提出一种新颖的算法，即将随机梯度思想引入到PALM算法中，并借助广义残差方程引入目标函数的二阶信息，从而设计出随机邻近牛顿型交替极小化算法。在理论分析方面，本文在非凸情形下建立目标函数在期望意义下的下降性分析，进而证明出该算法收敛性。

3.1. 随机邻近牛顿型交替极小化算法

在这一小节，我们给出本文所提算法的具体结构。为更好的描述算法，我们首先给出相关符号解释。

首先，问题(1.1)最优性条件可以等价地改写为一个不动点方程，即点$x,y\in dom\psi$ 是(1.1)的稳定点当且仅当

$\{\begin{array}{l}{R}^{{\alpha }_x}\left(x\right)=x-pro{x}_{{\alpha }_{x}f}\left(x-{\alpha }_x{\nabla }_{x}H\left(x,y\right)\right)=0,{\alpha }_x\in R^{+},\\ R^{{\alpha }_y}\left(y\right)=y-pro{x}_{{\alpha }_{y}g}\left(y-{\alpha }_y{\nabla }_{y}H\left(x,y\right)\right)=0,{\alpha }_y\in R^{+}.\end{array}$

邻近算子是稳定非扩张的，即它是一个常数为1的全局Lipschitz连续函数，且满足：

$\{\begin{array}{l}{\Vert pro{x}_{{\alpha }_{x}f}\left(x_1\right)-pro{x}_{{\alpha }_{x}f}\left(x_2\right)\Vert }^2\le \langle x_1-x_2,pro{x}_{{\alpha }_{x}f}\left(x_1\right)-pro{x}_{{\alpha }_{x}f}\left(x_2\right)\rangle ,\forall x_1,x_2;\\ {\Vert pro{x}_{{\alpha }_{y}g}\left(y_1\right)-pro{x}_{{\alpha }_{y}g}\left(y_2\right)\Vert }^2\le \langle y_1-y_2,pro{x}_{{\alpha }_{y}g}\left(y_1\right)-pro{x}_{{\alpha }_{y}g}\left(y_2\right)\rangle ,\forall y_1,y_2.\end{array}$

给定随机方向$v_x,v_y\in {ℝ}^n$ ，我们考虑不动点方程的变体

$\{\begin{array}{l}{R}_{v_x}^{{\alpha }_x}\left(x\right)=x-pro{x}_{{\alpha }_{x}f}\left(x-{\alpha }_x{v}_x\right);\\ R_{v_y}^{{\alpha }_y}\left(y\right)=y-pro{x}_{{\alpha }_{y}g}\left(y-{\alpha }_y{v}_y\right).\end{array}$

我们用

$\{\begin{array}{l}{p}_{v_x}^{{\alpha }_x}\left(x\right)=pro{x}_{{\alpha }_{x}f}\left(x-{\alpha }_x{v}_x\right)\\ p_{v_y}^{{\alpha }_y}\left(y\right)=pro{x}_{{\alpha }_{y}g}\left(y-{\alpha }_y{v}_y\right)\end{array}$

分别表示关于$x,y$ 的随机邻近梯度步。当$v_x={\nabla }_{x}H\left(x,y\right),v_y={\nabla }_{y}H\left(x,y\right)$ 时，用$p^{{\alpha }_x}\left(x\right),p^{{\alpha }_y}\left(y\right)$ 分别表示关于$x,y$ 的邻近梯度步。

下面给出算法的具体框架和步骤。

算法1 随机邻近牛顿型交替极小化算法 初始化：选择正的步长${\left\{{\alpha }_x^k\right\}}_k$ ，${\left\{{\alpha }_{x,+}^k\right\}}_k$ ，${\left\{{\lambda }_x^k\right\}}_k$ ，${\left\{{\beta }_x^k\right\}}_k$ ，点$\left(x^0,y^0\right)\in dom\psi$ 。 For $k=0,1,\cdots$ do 计算随机梯度$v_x^k\approx {\nabla }_{x}H\left(x^k,y^k\right)$ ，残差 $R_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)=x^k-pro{x}_{{\alpha }_x^{k}f}\left(x^k-{\alpha }_x^k{v}_x^k\right).$ (3.1) 以及方向$d_x^k=-W_x^k{R}_{v_x^k}^{{\alpha }_x^k}$ 。计算${\overline{x}}^k=x^k+{\beta }_x^k{d}_x^k$ 及随机梯度$v_{x,+}^k\approx {\nabla }_{x}H\left({\overline{x}}^k,y^k\right)$ ，并执行更新 $x^{k+1}=pro{x}_{{\alpha }_{x,+}^{k}f}\left(x^k+{\lambda }_x^k{d}_x^k-{\alpha }_{x,+}^k{v}_{x,+}^k\right).$ (3.2) 计算随机梯度$v_y^k\approx {\nabla }_{y}H\left(x^{k+1},y^k\right)$ ，以及残差 $R_{v_y^k}^{{\alpha }_y^k}\left(y^k\right)=y^k-pro{x}_{{\alpha }_y^{k}g}\left(y^k-{\alpha }_y^k{v}_y^k\right).$ (3.3) 和方向$d_y^k=-W_y^k{R}_{v_y^k}^{{\alpha }_y^k}$ 。计算${\overline{y}}^k=y^k+{\beta }_y^k{d}_y^k$ 及随机梯度$v_{y,+}^k\approx {\nabla }_{y}H\left(x^{k+1},{\overline{y}}^k\right)$ ，并执行更新 $y^{k+1}=pro{x}_{{\alpha }_{y,+}^{k}g}\left(y^k+{\lambda }_y^k{d}_y^k-{\alpha }_{y,+}^k{v}_{y,+}^k\right).$ (3.4)

本文算法根据残差方程的随机变体生成方向$d_x$ 和$d_y$ ，基于此在算法中引入了目标函数的二阶信息。具体来说，本文考虑下述形式的方向

$\{\begin{array}{l}{d}_x=-W_x{R}_{v_x}^{{\alpha }_x}\left(x\right);\\ d_y=-W_y{R}_{v_y}^{{\alpha }_y}\left(y\right).\end{array}$

其中矩阵$W_x,W_y\in {ℝ}^{n\times n}$ 用以对基本随机邻近梯度方向$-R_{v_x}^{{\alpha }_x}\left(x\right),-R_{v_y}^{{\alpha }_y}\left(y\right)$ 进行细化和改进，$v_x\approx {\nabla }_{x}H\left(x,y\right)$ 是对${\nabla }_{x}H\left(x,y\right)$ 的随机近似，$v_y\approx {\nabla }_{y}H\left(x,y\right)$ 是对${\nabla }_{y}H\left(x,y\right)$ 的随机近似。针对每一迭代步x的更新，我们首先通过$\overline{x}=x+\beta d$ 计算一个新的点，然后执行额外的邻近梯度步骤，以获得下一个迭代点$x_{+}$ ：

$[\begin{array}{l}\overline{x}=x+{\beta }_x{d}_x\\ x_{+}=pro{x}_{{\alpha }_{x,+}f}\left(x+{\lambda }_x{d}_x-{\alpha }_{x,+}{v}_{x,+}\right).\end{array}$

其中${\lambda }_x,{\beta }_x\ge 0,{\alpha }_x,{\alpha }_{x,+}\in {ℝ}^{+}$ 是合适的步长参数，$v_{x,+}\in {ℝ}^n$ 是梯度${\nabla }_{x}H\left(x,y\right)$ 的随机近似。y的更新过程与x的更新类似，这里不再赘述。

3.2. 基本假设

为了分析随机邻近牛顿型交替极小化算法的收敛性及收敛率分析，在这一小节我们首先给出保障算法收敛性的相关假设，具体如下。

假设1 给定函数$H\left(x,y\right):{ℝ}^n\times {ℝ}^n\to ℝ$ ，设

(A.1) $H\left(x,y\right)$ 关于$x,y$ 都连续可微，且梯度映射${\nabla }_{x}H\left(x,y\right)$ 和${\nabla }_{y}H\left(x,y\right)$ 在${ℝ}^n$ 上是Lipschitz连续的，模$L_x,L_y\ge 1$ 。

(A.2) 目标函数$\psi$ 在$domf\times domg$ 上下有界。

本文假设随机近似$v_x^k$ 和$v_{x,+}^k$ 对应于随机向量$V_x^k:\Omega \to {ℝ}^n$ 和$V_{x,+}^k:\Omega \to {ℝ}^n$ 的实现，$v_y^k$ 和$v_{y,+}^k$ 对应于随机向量$V_{\text{y}}^k:\Omega \to {ℝ}^n$ 和$V_{y,+}^k:\Omega \to {ℝ}^n$ 的实现。此外，我们假设概率空间$\left(\Omega ,\text{F},\text{P}\right)$ 足够丰富，允许我们以统一的方式建模所涉及的随机过程。我们现在定义滤流

${\text{F}}^k:=\sigma \left(V_x^0,V_{x,+}^0,\cdots ,V_x^k,V_y^0,V_{y,+}^0,\cdots ,V_y^k\right),{\text{ F}}_{+}^k:=\sigma \left({\text{F}}_x^k\cup \sigma \left(V_{x,+}^k\right)\cup {\text{F}}_y^k\cup \sigma \left(V_{y,+}^k\right)\right).$

用${\left\{D_x^k\right\}}_k$ 表示与算法中选择的方向${\left\{d_x^k\right\}}_k$ 相关的随机过程，${\left\{d_y^k\right\}}_k$ 表示与算法中选择的方向${\left\{d_y^k\right\}}_k$ 相关的随机过程。我们给出一下随机假设。

假设2 (B.1) 映射$D_x^k:\Omega \to {ℝ}^n$ 和$D_y^k:\Omega \to {ℝ}^n$ 对于所有k是可测的。

(B.2) 存在$v_k>0$ ，使得对于所有$k\in \mathbb{N}$ ，都有

$\text{E}\left[{\Vert D_y^k\Vert }^2|{\text{F}}_{+}^{k-1}\right]\le v_k^2\cdot \text{E}\left[{\Vert R_{V_y^k}^{{\lambda }_k}\left(Y^k\right)\Vert }^2|{\text{F}}_{+}^{k-1}\right]$ a.e.

(B.3) 对于所有$k\in \mathbb{N}$ ，$\text{E}\left[V_x^k|{\text{F}}_{+}^{k-1}\right]={\nabla }_{x}H\left(X^k,Y^k\right)$ ，$\text{E}\left[V_{x,+}^k|{\text{F}}^k\right]={\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)$， $\text{E}\left[V_y^k|{\text{F}}_{+}^{k-1}\right]={\nabla }_{y}H\left(X^{k+1},Y^k\right)$ 与$\text{E}\left[V_{y,+}^k|{\text{F}}^k\right]={\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)$ a.e.，且存在${\sigma }_k,{\sigma }_{k,+}>0$ ，使得

$\text{E}\left[{\Vert {\nabla }_{x}H\left(X^k,Y^k\right)-V^k\Vert }^2|{\text{F}}_{+}^{k-1}\right]\le {\sigma }_k^2$ 和$\text{E}\left[{\Vert {\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)-V_{+}^k\Vert }^2|{\text{F}}^k\right]\le {\sigma }_{k,+}^2$ a.e，

$\text{E}\left[{\Vert {\nabla }_{y}H\left(X^{k+1},Y^k\right)-V^k\Vert }^2|{\text{F}}_{+}^{k-1}\right]\le {\sigma }_k^2$ 和$\text{E}\left[{\Vert {\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)-V_{+}^k\Vert }^2|{\text{F}}^k\right]\le {\sigma }_{k,+}^2$ a.e。

假设2 (B.3)中$V_x^k$ 和$V_{x,+}^k$ ，$V_y^k$ 和$V_{y,+}^k$ 的条件在随机优化中很常见[19]。第二个假设要求所选方向${\left\{d_x^k\right\}}_k$ 和随机过程${\left\{D_x^k\right\}}_k$ 与随机非光滑残差$R_{v_x^k}^{{\lambda }_k}\left(X^k\right)$ ，$k\in \mathbb{N}$ 有关，并且所选方向${\left\{d_y^k\right\}}_k$ 和随机过程${\left\{D_y^k\right\}}_k$ 与随机非光滑残差$R_{v_y^k}^{{\lambda }_k}\left(Y^k\right)$ ，$k\in \mathbb{N}$ 相关。在假设(B.1)下，算法的设计意味着${\left\{\left(X^k,Y^k\right)\right\}}_k$ 和${\left\{\left(X^{k+1},Y^k\right)\right\}}_k$ 适用于滤流${\text{F}}^k$ ，${\left\{\left({\overline{X}}^k,Y^k\right)\right\}}_k$ 和${\left\{\left(X^{k+1},{\overline{Y}}^k\right)\right\}}_k$ 适用于滤流${\text{F}}_{+}^k$ 。即我们有

${\left\{\left({\overline{X}}^k,Y^k\right)\right\}}_k,{\left\{\left(X^{k+1},{\overline{Y}}^k\right)\right\}}_k\in {\text{F}}^k$并且${\left\{\left(X^{k+1},Y^{k+1}\right)\right\}}_k,{\left\{\left(X^{k+2},Y^{k+1}\right)\right\}}_k\in {\text{F}}_{+}^k$ ，$\forall k\ge 0$ 。

3.3. 算法的收敛性分析

本节对提出的算法的收敛性展开分析，首先给出4个辅助引理以建立目标函数$\psi$ 的近似下降性，最后在定理1中证明了算法的收敛性。下面首先给出引理1，在该引理中给出了目标函数f的近似下降性。

引理1：假设1成立，${\left\{\left(x^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 为随机邻近牛顿型交替极小化算法生成的序列，则有

$\begin{array}{l}f\left(x^{k+1}\right)-f\left(x^k\right)\le \langle \frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\langle v_x^k,p^{{\alpha }_x^k}\left(x^k\right)-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle \\ +\langle {\nabla }_{x}H\left(x^k,y^k\right),x^k-p^{{\alpha }_x^k}\left(x^k\right)\rangle +\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\end{array}$ (3.5)

证明：由迭代$x^{k+1}=pro{x}_{{\alpha }_{x,+}^{k}f}\left(x^k+{\lambda }_x^k{d}_x^k-{\alpha }_{x,+}^k{v}_{x,+}^k\right)$ 的最优性条件可得

$0\in \partial f\left(x^{k+1}\right)+v_{x,+}^k+\frac{1}{{\alpha }_{x,+}^k}\left(x^{k+1}-x^k-{\lambda }_x^k{d}_x^k\right),$

进一步有

$\frac{1}{{\alpha }_{x,+}^k}\left(x^k+{\lambda }_x^k{d}_x^k-x^{k+1}-{\alpha }_{x,+}^k{v}_{x,+}^k\right)\in \partial f\left(x^{k+1}\right).$ (3.6)

利用函数f的凸性可知，

$f\left(x^{k+1}\right)-f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right)\le \langle \partial f\left(x^{k+1}\right),x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle .$ (3.7)

结合公式(3.5)和(3.6)可得：

$\begin{array}{l}f\left(x^{k+1}\right)-f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right)\le \langle \frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\frac{1}{{\alpha }_{x,+}^k}\langle x^k-x^{k+1},x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle \\ =\langle \frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\end{array}$ (3.8)

其中等式是由$\langle a-b,c-d\rangle =\frac{1}{2}\left({\Vert a-b\Vert }^2-{\Vert a-c\Vert }^2+{\Vert b-c\Vert }^2-{\Vert b-d\Vert }^2\right)$ 得到的。

由$p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)=pro{x}_{{\alpha }_x^{k}f}\left(x^k-{\alpha }_x^k{v}_x^k\right)$ 可得，

$\frac{1}{{\alpha }_x^k}\left(x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right)-v_x^k\in \partial f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right),$ (3.9)

又由函数f的凸性可知

$f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right)-f\left(p^{{\alpha }_x^k}\left(x^k\right)\right)\le \langle \partial f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right),p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x^k}\left(x^k\right)\rangle .$ (3.10)

因此

$\begin{array}{l}f\left(p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\right)-f\left(p^{{\alpha }_x^k}\left(x^k\right)\right)\le \langle v_x^k,p^{{\alpha }_x^k}\left(x^k\right)-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\frac{1}{2{\alpha }_x^k}{\Vert x^k-p^{{\alpha }_x}\left(x^k\right)\Vert }^2\\ -\frac{1}{2{\alpha }_x^k}{\Vert p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x}\left(x^k\right)\Vert }^2.\end{array}$ (3.11)

由$p^{{\alpha }_x^k}\left(x^k\right)$ 的定义可得

$\frac{1}{{\alpha }_x^k}\left(x^k-p^{{\alpha }_x^k}\left(x^k\right)\right)-{\nabla }_{x}H\left(x^k,y^k\right)\in \partial f\left(p^{{\alpha }_x^k}\left(x^k\right)\right),$ (3.12)

又由函数f的凸性可知

$f\left(p^{{\alpha }_x^k}\left(x^k\right)\right)-f\left(x^k\right)\le \langle \partial f\left(p^{{\alpha }_x^k}\left(x^k\right)\right),p^{{\alpha }_x^k}\left(x^k\right)-x^k\rangle ,$ (3.13)

由(3.11)、(3.12)得

$\begin{array}{l}f\left(p^{{\alpha }_x^k}\left(x^k\right)\right)-f\left(x^k\right)\le \langle {\nabla }_{x}H\left(x^k,y^k\right),x^k-p^{{\alpha }_x^k}\left(x^k\right)\rangle +\frac{1}{2{\alpha }_x^k}{\Vert x^k-x^k\Vert }^2\\ -\frac{1}{2{\alpha }_x^k}{\Vert p^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert p^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2.\end{array}$ (3.14)

结合公式(3.7)，(3.10)和(3.13)可得(3.14)。

类似的，对于变量y，有以下结论。

引理2：假设1成立，${\left\{\left(x^k,y^k\right)\right\}}_{k\in \mathbb{N}}$ 为随机邻近牛顿型交替极小化算法生成的序列，则有

$\begin{array}{l}g\left(y^{k+1}\right)-g\left(y^k\right)\le \langle \frac{{\lambda }_y^k}{{\alpha }_{y,+}^k}{d}_y^k-v_{y,+}^k,y^{k+1}-p_{v_y^k}^{{\alpha }_y^k}\left(y^k\right)\rangle +\langle v_y^k,p^{{\alpha }_y^k}\left(y^k\right)-p_{v_y^k}^{{\alpha }_y^k}\left(y^k\right)\rangle \\ +\langle {\nabla }_{y}H\left(x^{k+1},y^k\right),y^k-p^{{\alpha }_y^k}\left(y^k\right)\rangle +\frac{1}{2{\alpha }_{y,+}^k}{\Vert y^k-p_{v_y^k}^{{\alpha }_y^k}\left(y^k\right)\Vert }^2\end{array}$ (3.15)

基于引理1和引理2，可以建立$\psi$ 的近似下降性。首先，由$\psi$ 定义可得

$\begin{array}{l}\psi \left(x^{k+1},y^{k+1}\right)-\psi \left(x^k,y^k\right)\\ =f\left(x^{k+1}\right)+g\left(y^{k+1}\right)+H\left(x^{k+1},y^{k+1}\right)-f\left(x^k\right)-g\left(y^k\right)-H\left(x^k,y^k\right)\\ =f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)\\ +g\left(y^{k+1}\right)+H\left(x^{k+1},y^{k+1}\right)-\left(g\left(y^k\right)+H\left(x^{k+1},y^k\right)\right),\end{array}$ (3.16)

下面首先给出$f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)$ 的近似下降性。

引理3：假设1成立，${\left\{\left(x^k,y^k\right)\right\}}_{k\in N}$ 为随机邻近牛顿型交替极小化算法生成的序列，则有

$\begin{array}{l}f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)\\ \le \frac{{\alpha }_{x,+}^k}{2}{\left(L_x{\beta }_x^k+\frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}\right)}^2{\Vert d_x^k\Vert }^2+\frac{{\alpha }_{x,+}^k}{2}{\Vert {\nabla }_{x}H\left({\overline{x}}^k,y^k\right)-v_{x,+}^k\Vert }^2\\ +\langle {\nabla }_{x}H\left({\overline{x}}^k,y^k\right)-v_{x,+}^k,{\alpha }_{x,+}^k\left({\nabla }_{x}H\left(x^k,y^k\right)-{\nabla }_{x}H\left({\overline{x}}^k,y^k\right)\right)+{\lambda }_x^k{d}_x^k\rangle \\ +\frac{{\alpha }_x^k}{2}{\Vert {\nabla }_{x}H\left(x^k,y^k\right)-v_x^k\Vert }^2+\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ \text{ +}\left(\frac{L_x}{2}-\frac{1}{2{\alpha }_{x,+}^k}\right)\Vert x^{k+1}-x^k{}^2\Vert -\frac{1}{2{\alpha }_x^k}{\Vert x^k-p^{{\alpha }_x^k}\left(x^k\right)\Vert }^2.\end{array}$ (3.17)

证明：关于H的部分我们使用下降引理可得

$H\left(x^{k+1},y^k\right)\le H\left(x^k,y^k\right)+\langle {\nabla }_{x}H\left(x^k,y^k\right),x^{k+1}-x^k\rangle +\frac{L_x}{2}{\Vert x^{k+1}-x^k\Vert }^2,$ (3.18)

则由(3.5)和(3.18)可得：

$\begin{array}{l}f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)\\ \le \langle \frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\langle v_x^k,p^{{\alpha }_x^k}\left(x^k\right)-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle \\ +\langle {\nabla }_{x}H\left(x^k,y^k\right),x^k-p^{{\alpha }_x^k}\left(x^k\right)\rangle +\langle {\nabla }_{x}H\left(x^k,y^k\right),x^{k+1}-x^k\rangle \\ +\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2-\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^k-x^{k+1}\Vert }^2-\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ -\frac{1}{2{\alpha }_x^k}{\Vert p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x}\left(x^k\right)\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert p^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2+\frac{Lx}{2}{\Vert x^{k+1}-x^k\Vert }^2,\end{array}$

整理可得

$\begin{array}{l}f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)\\ \le \langle \frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle +\langle v_x^k,p^{{\alpha }_x^k}\left(x^k\right)-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle \\ +\langle {\nabla }_{x}H\left(x^k,y^k\right),x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)+p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x^k}\left(x^k\right)\rangle \\ +\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2-\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^k-x^{k+1}\Vert }^2-\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ -\frac{1}{2{\alpha }_x^k}{\Vert p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x}\left(x^k\right)\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert p^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2+\frac{Lx}{2}{\Vert x^{k+1}-x^k\Vert }^2\\ \le \langle {\nabla }_{x}H\left(x^k,y^k\right)+\frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k,x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\rangle \\ +\langle {\nabla }_{x}H\left(x^k,y^k\right)-v_x^k,p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x^k}\left(x^k\right)\rangle +\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ \text{ +}\left(\frac{L_x}{2}-\frac{1}{2{\alpha }_{x,+}^k}\right){\Vert x^{k+1}-x^k\Vert }^2-\frac{1}{2{\alpha }_{x,+}^k}{\Vert x^{k+1}-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ -\frac{1}{2{\alpha }_x^k}{\Vert p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)-p^{{\alpha }_x}\left(x^k\right)\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert p^{{\alpha }_x^k}\left(x^k\right)-x^k\Vert }^2.\end{array}$ (3.19)

利用公式(3.18)和不等式$2\langle a,b\rangle \le {\alpha }_x^k{\Vert a\Vert }^2+\frac{1}{{\alpha }_x^k}{\Vert b\Vert }^2$ 可得

$\begin{array}{l}f\left(x^{k+1}\right)+H\left(x^{k+1},y^k\right)-\left(f\left(x^k\right)+H\left(x^k,y^k\right)\right)\\ \le \frac{{\alpha }_{x,+}^k}{2}{\Vert {\nabla }_{x}H\left(x^k,y^k\right)+\frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k-v_{x,+}^k\Vert }^2+\frac{{\alpha }_x^k}{2}{\Vert {\nabla }_{x}H\left(x^k,y^k\right)-v_x^k\Vert }^2\\ +\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\text{+}\left(\frac{L_x}{2}-\frac{1}{2{\alpha }_{x,+}^k}\right){\Vert x^{k+1}-x^k\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert x^k-p^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\end{array}$

$\begin{array}{l}\le \frac{{\alpha }_{x,+}^k}{2}{\Vert {\nabla }_{x}H\left(x^k,y^k\right)-{\nabla }_{x}H\left({\overline{x}}^k,y^k\right)+\frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}{d}_x^k\Vert }^2+\frac{{\alpha }_{x,+}^k}{2}{\Vert {\nabla }_{x}H\left({\overline{x}}^k,y^k\right)-v_{x,+}^k\Vert }^2\\ +\langle {\nabla }_{x}H\left({\overline{x}}^k,y^k\right)-v_{x,+}^k,{\alpha }_{x,+}^k\left({\nabla }_{x}H\left(x^k,y^k\right)-{\nabla }_{x}H\left({\overline{x}}^k,y^k\right)\right)+{\lambda }_x^k{d}_x^k\rangle \\ +\frac{{\alpha }_x^k}{2}{\Vert {\nabla }_{x}H\left(x^k,y^k\right)-v_x^k\Vert }^2+\left(\frac{1}{2{\alpha }_{x,+}^k}-\frac{1}{2{\alpha }_x^k}\right){\Vert x^k-p_{v_x^k}^{{\alpha }_x^k}\left(x^k\right)\Vert }^2\\ \text{ +}\left(\frac{L_x}{2}-\frac{1}{2{\alpha }_{x,+}^k}\right){\Vert x^{k+1}-x^k\Vert }^2-\frac{1}{2{\alpha }_x^k}{\Vert x^k-p^{{\alpha }_x^k}\left(x^k\right)\Vert }^2,\end{array}$

其中第二个不等式利用了${\Vert a+b\Vert }^2\le 2{\Vert a\Vert }^2+2{\Vert b\Vert }^2$ 。进一步，根据$H\left(x,y\right)$ 关于变量x连续可微且${\overline{x}}^k=x^k+{\beta }_x^k{d}_x^k$ 可得(3.17)。

类似地，我们可以建立$g\left(y^{k+1}\right)+H\left(x^{k+1},y^{k+1}\right)-\left(g\left(y^k\right)+H\left(x^{k+1},y^k\right)\right)$ 的近似下降性。

引理4：假设1成立，${\left\{\left(x^k,y^k\right)\right\}}_{k\in N}$ 为随机邻近牛顿型交替极小化算法生成的序列，则有

$\begin{array}{l}g\left(y^{k+1}\right)+H\left(x^{k+1},y^{k+1}\right)-\left(g\left(y^k\right)+H\left(x^{k+1},y^k\right)\right)\\ \le \frac{{\alpha }_{y,+}^k}{2}{\left(L_y{\beta }_y^k+\frac{{\lambda }_y^k}{{\alpha }_{y,+}^k}\right)}^2{\Vert d_y^k\Vert }^2+\frac{{\alpha }_{y,+}^k}{2}{\Vert {\nabla }_{y}H\left(x^{k+1},{\overline{y}}^k\right)-v_{y,+}^k\Vert }^2\\ +\langle {\nabla }_{y}H\left(x^{k+1},{\overline{y}}^k\right)-v_{y,+}^k,{\alpha }_{y,+}^k\left({\nabla }_{y}H\left(x^{k+1},y^k\right)-{\nabla }_{y}H\left(x^{k+1},{\overline{y}}^k\right)\right)+{\lambda }_y^k{d}_y^k\rangle \\ +\frac{{\alpha }_y^k}{2}{\Vert {\nabla }_{y}H\left(x^{k+1},y^k\right)-v_y^k\Vert }^2+\left(\frac{1}{2{\alpha }_{y,+}^k}-\frac{1}{2{\alpha }_y^k}\right){\Vert y^k-p_{v_y^k}^{{\alpha }_y^k}\left(y^k\right)\Vert }^2\\ \text{ +}\left(\frac{L_y}{2}-\frac{1}{2{\alpha }_{y,+}^k}\right){\Vert y^{k+1}-y^k\Vert }^2-\frac{1}{2{\alpha }_y^k}{\Vert y^k-p^{{\alpha }_y^k}\left(y^k\right)\Vert }^2.\end{array}$ (3.20)

基于引理1~4，下面给出算法的收敛性分析。

定理1：令随机过程${\left\{\left(X^k,Y^k\right)\right\}}_k$ 为算法生成的序列。假设1和假设2成立，且步长${\left\{{\alpha }_x^k\right\}}_k,{\left\{{\alpha }_{{}_{x,+}}^k\right\}}_k,{\left\{{\lambda }_x^k\right\}}_k,{\left\{{\beta }_x^k\right\}}_k$ 以及${\left\{{\alpha }_y^k\right\}}_k,{\left\{{\alpha }_{{}_{y,+}}^k\right\}}_k,{\left\{{\lambda }_y^k\right\}}_k,{\left\{{\beta }_y^k\right\}}_k$ 满足对于所有的$k\in \mathbb{N}$ 和某个$\overline{\rho }\in \left(0,1\right)$ 有以下式子成立

$\begin{array}{l}{\alpha }_{x,+}^k\le \frac{1}{L_x},{\alpha }_{{}_x}^k\le \frac{\left(1-\overline{\rho }\right){\alpha }_{x,+}^k}{1+{\left(v_x^k\right)}^2{\left({\alpha }_x^k+L_x{\beta }_x^k{\alpha }_{x,+}^k\right)}^2};\\ {\alpha }_{y,+}^k\le \frac{1}{L_y},{\alpha }_y^k\le \frac{\left(1-\overline{\rho }\right){\alpha }_{y,+}^k}{1+{\left(v_y^k\right)}^2{\left({\alpha }_y^k+L_y{\beta }_y^k{\alpha }_{y,+}^k\right)}^2}.\end{array}$ (3.21)

则若${\displaystyle \sum {\alpha }_x^k}=\infty$ ，${\displaystyle \sum {\alpha }_x^k{\left({\sigma }_x^k\right)}^2}<\infty$ ，${\displaystyle \sum {\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2}<\infty$ ，${\displaystyle \sum {\alpha }_y^k}=\infty$ ，${\displaystyle \sum {\alpha }_y^k{\left({\sigma }_y^k\right)}^2}<\infty$ ，有

$\lim {\inf }_{k\to \infty }E\left[{\Vert F^1\left(X^k\right)\Vert }^2\right]=0$ ，$\lim {\inf }_{k\to \infty }E\left[{\Vert F^1\left(Y^k\right)\Vert }^2\right]=0$ ，$\lim {\inf }_{k\to \infty }\Vert F^1\left(X^k\right)\Vert =0$ ，

$\lim {\inf }_{k\to \infty }\Vert F^1\left(Y^k\right)\Vert =0$ a.s.，并且$\underset{k\to \infty }{\lim }E\Vert X^{k+1}-X^k\Vert =0$ ，$\underset{k\to \infty }{\lim }E\Vert Y^{k+1}-Y^k\Vert =0$ 。

证明：由${\text{F}}_{+}^{k-1}\subset {\text{F}}^k$ 与$X^k,D_x^k,{\overline{X}}^k,Y^k,D_y^k,{\overline{Y}}^k\in {\text{F}}^k$可得下述结果几乎处处成立

$\begin{array}{l}E\left[\langle {\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)-V_{x,+}^k,{\alpha }_{x,+}^k\left({\nabla }_{x}H\left(X^k,Y^k\right)-{\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)\right)+{\lambda }_x^k{D}_x^k\rangle |{�}_{+}^{k-1}\right]\\ =E\left[\langle E\left[{\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)-V_{x,+}^k|{�}^k\right],{\alpha }_{x,+}^k\left({\nabla }_{x}H\left(X^k,Y^k\right)-{\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)\right)+{\lambda }_x^k{D}_x^k\rangle |{�}_{+}^{k-1}\right]\\ =0,\end{array}$

$\begin{array}{l}E\left[\langle {\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)-V_{y,+}^k,{\alpha }_{y,+}^k\left({\nabla }_{y}H\left(X^{k+1},Y^k\right)-{\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)\right)+{\lambda }_y^k{D}_y^k\rangle |{�}_{+}^{k-1}\right]\\ =E\left[\langle E\left[{\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)-V_{y,+}^k|{�}^k\right],{\alpha }_{y,+}^k\left({\nabla }_{y}H\left(X^{k+1},Y^k\right)-{\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)\right)+{\lambda }_y^k{D}_y^k\rangle |{�}_{+}^{k-1}\right]\\ =0,\end{array}$

其中我们用到了$V_{x,+}^k$ 与$V_{y,+}^k$ 分别是${\nabla }_{x}H\left({\overline{X}}^k,Y^k\right)$ 与${\nabla }_{y}H\left(X^{k+1},{\overline{Y}}^k\right)$ 的无偏估计。基于此，将公式(3.17)与公式(3.20)相加，求条件期望，并利用假设2可得以下结果几乎处处成立：

$\begin{array}{l}E\left[\psi \left(X^{k+1},Y^{k+1}\right)|{�}_{+}^{k-1}-\psi \left(X^k,Y^k\right)\right]\\ \le \frac{{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2}{2}+\frac{1}{2}\left(L_x-\frac{1}{{\alpha }_{x,+}^k}\right)E\left[{\Vert X^{k+1}-X^k\Vert }^2|{�}_{+}^{k-1}\right]-\frac{1}{2{\alpha }_x^k}{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2\\ +\frac{{\alpha }_x^k{\left({\sigma }_x^k\right)}^2}{2}+\frac{1}{2}\left[\frac{1}{{\alpha }_{x,+}^k}-\frac{1}{{\alpha }_x^k}+{\left(v_x^k\right)}^2{\alpha }_{x,+}^k{\left(L_x{\beta }_x^k+\frac{{\lambda }_x^k}{{\alpha }_{x,+}^k}\right)}^2\right]E\left[{\Vert F_{V_x^k}^{{\alpha }_x^k}\left(X^k\right)\Vert }^2|{�}_{+}^{k-1}\right]\\ +\frac{{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2}{2}+\frac{1}{2}\left(L_y-\frac{1}{{\alpha }_{y,+}^k}\right)E\left[{\Vert Y^{k+1}-Y^k\Vert }^2|{�}_{+}^{k-1}\right]-\frac{1}{2{\alpha }_y^k}{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2\\ +\frac{{\alpha }_y^k{\left({\sigma }_y^k\right)}^2}{2}+\frac{1}{2}\left[\frac{1}{{\alpha }_{y,+}^k}-\frac{1}{{\alpha }_y^k}+{\left(v_y^k\right)}^2{\alpha }_{y,+}^k{\left(L_y{\beta }_y^k+\frac{{\lambda }_y^k}{{\alpha }_{y,+}^k}\right)}^2\right]E\left[{\Vert F_{V_y^k}^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2|{�}_{+}^{k-1}\right].\end{array}$ (3.23)

结合公式(3.21)与(3.23)可得

$\begin{array}{l}E\left[\psi \left(X^{k+1},Y^{k+1}\right)|{�}_{+}^{k-1}\right]-\psi \left(X^k,Y^k\right)\\ \le \frac{{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2}{2}+\frac{{\alpha }_x^k{\left({\sigma }_x^k\right)}^2}{2}-\frac{1}{2{\alpha }_x^k}{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2-\frac{\overline{\rho }}{2{\alpha }_x^k}E\left[{\Vert F_{V_x^k}^{{\alpha }_x^k}\left(X^k\right)\Vert }^2|{�}_{+}^{k-1}\right]\\ +\frac{{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2}{2}+\frac{{\alpha }_y^k{\left({\sigma }_y^k\right)}^2}{2}-\frac{1}{2{\alpha }_y^k}{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2-\frac{\overline{\rho }}{2{\alpha }_y^k}E\left[{\Vert F_{V_y^k}^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2|{�}_{+}^{k-1}\right].\end{array}$

由假设1可知存在${\psi }^{*}\in ℝ$ 满足$\psi \left(x,y\right)\ge {\psi }^{*}$ 对于所有的$\left(x,y\right)\in {ℝ}^n\times {ℝ}^n$ 。对上式左右两边求全期望并移项可得

$\begin{array}{l}\frac{E\left[{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2+\overline{\rho }{\Vert F_{V_x^k}^{{\alpha }_x^k}\left(X^k\right)\Vert }^2\right]}{{\alpha }_x^k}+\frac{E\left[{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2+\overline{\rho }{\Vert F_{V_y^k}^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2\right]}{{\alpha }_y^k}\\ \le 2\left[\psi \left(x^k,y^k\right)-\psi \left(x^{k+1},y^{k+1}\right)\right]+{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2+{\alpha }_x^k{\left({\sigma }_x^k\right)}^2+{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2+{\alpha }_y^k{\left({\sigma }_y^k\right)}^2.\end{array}$

对上式左右两边同时累和可得对于所有的$K\in \mathbb{N}$ 有

$\begin{array}{l}{\displaystyle \sum _{k=0}^K\frac{E\left[{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2+\overline{\rho }{\Vert F_{V_x^k}^{{\alpha }_x^k}\left(X^k\right)\Vert }^2\right]}{{\alpha }_x^k}+\frac{E\left[{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2+\overline{\rho }{\Vert F_{V_y^k}^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2\right]}{{\alpha }_y^k}}\\ \le 2\left[\psi \left(x^0,y^0\right)-{\psi }^{*}\right]+{\displaystyle \sum _{k=0}^K\left[{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2+{\alpha }_x^k{\left({\sigma }_x^k\right)}^2+{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2+{\alpha }_y^k{\left({\sigma }_y^k\right)}^2\right]}.\end{array}$

因为$L_x,L_y\ge 1$ ，则${\alpha }_{x,+}^k\le 1,{\alpha }_x^k\le 1$ 并且${\alpha }_{y,+}^k\le 1,{\alpha }_y^k\le 1$ 。又映射$\delta \mapsto {\delta }^{-1}\Vert F^{\frac{1}{\delta }}\left(x\right)\Vert$ 是一个关于$\delta$ 的递减函数[20]，因此，对于所有的$k\in \mathbb{N}$ ，有

$E\left[{\Vert F^1\left(X^k\right)\Vert }^2\right]\le {\left({\alpha }_x^k\right)}^{-2}E\left[{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2\right],E\left[{\Vert F^1\left(Y^k\right)\Vert }^2\right]\le {\left({\alpha }_y^k\right)}^{-2}E\left[{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2\right],$

进而我们可以得到${\displaystyle \sum {\alpha }_x^k}E\left[{\Vert F^1\left(X^k\right)\Vert }^2\right]<\infty$ ，${\displaystyle \sum {\alpha }_y^k}E\left[{\Vert F^1\left(Y^k\right)\Vert }^2\right]<\infty$ 。又因为${\displaystyle \sum {\alpha }_x^k}=\infty$ ，${\displaystyle \sum {\alpha }_y^k=\infty }$ ，因此$\lim {\inf }_{k\to \infty }E\left[{\Vert F^1\left(X^k\right)\Vert }^2\right]=0$ ，$\lim {\inf }_{k\to \infty }E\left[{\Vert F^1\left(Y^k\right)\Vert }^2\right]=0$ 。又根据Borel-Cantelli引理[21]可知：当${\displaystyle \sum {\alpha }_x^k}E\left[{\Vert F^1\left(X^k\right)\Vert }^2\right]<\infty$ 与${\displaystyle \sum {\alpha }_y^k}E\left[{\Vert F^1\left(Y^k\right)\Vert }^2\right]<\infty$ 几乎处处成立时，可以推出$\lim {\inf }_{k\to \infty }\Vert F^1\left(X^k\right)\Vert =0$ ，$\lim {\inf }_{k\to \infty }\Vert F^1\left(Y^k\right)\Vert =0$ 必定成立。

由公式(3.21)和(3.23)可得

$\begin{array}{l}\frac{1}{2}\left(\frac{1}{{\alpha }_{x,+}^k}-L_x\right)E\left[{\Vert X^{k+1}-X^k\Vert }^2|{�}_{+}^{k-1}\right]+\frac{1}{2}\left(\frac{1}{{\alpha }_{y,+}^k}-L_y\right)E\left[{\Vert Y^{k+1}-Y^k\Vert }^2|{�}_{+}^{k-1}\right]\\ \le \psi \left(X^k,Y^k\right)-E\left[\psi \left(X^{k+1},Y^{k+1}\right)|{�}_{+}^{k-1}\right]\\ +\frac{{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2}{2}+\frac{{\alpha }_x^k{\left({\sigma }_x^k\right)}^2}{2}-\frac{1}{2{\alpha }_x^k}{\Vert F^{{\alpha }_x^k}\left(X^k\right)\Vert }^2-\frac{\overline{\rho }}{2{\alpha }_x^k}E\left[{\Vert F_{V_x^k}^{{\alpha }_x^k}\left(X^k\right)\Vert }^2|{�}_{+}^{k-1}\right]\\ +\frac{{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2}{2}+\frac{{\alpha }_y^k{\left({\sigma }_y^k\right)}^2}{2}-\frac{1}{2{\alpha }_y^k}{\Vert F^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2-\frac{\overline{\rho }}{2{\alpha }_y^k}E\left[{\Vert F_{V_y^k}^{{\alpha }_y^k}\left(Y^k\right)\Vert }^2|{�}_{+}^{k-1}\right]\\ \le \psi \left(X^k,Y^k\right)-E\left[\psi \left(X^{k+1},Y^{k+1}\right)|{�}_{+}^{k-1}\right]\\ +\frac{{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2}{2}+\frac{{\alpha }_x^k{\left({\sigma }_x^k\right)}^2}{2}+\frac{{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2}{2}+\frac{{\alpha }_y^k{\left({\sigma }_y^k\right)}^2}{2}.\end{array}$

记$M=\min \left\{\frac{1}{2}\left(\frac{1}{{\alpha }_{x,+}^k}-L_x\right),\frac{1}{2}\left(\frac{1}{{\alpha }_{y,+}^k}-L_y\right)\right\}$ ，由上式可得

$\begin{array}{l}E\left[{\Vert X^{k+1}-X^k\Vert }^2|{�}_{+}^{k-1}\right]+E\left[{\Vert Y^{k+1}-Y^k\Vert }^2|{�}_{+}^{k-1}\right]\\ \le \frac{1}{M}\left[\psi \left(X^k,Y^k\right)-E\left[\psi \left(X^{k+1},Y^{k+1}\right)|{�}_{+}^{k-1}\right]\right]\\ +\frac{1}{2M}\left[{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2+{\alpha }_x^k{\left({\sigma }_x^k\right)}^2+{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2+{\alpha }_y^k{\left({\sigma }_y^k\right)}^2\right].\end{array}$

对上式左右两边求全期望并累和可得

$\begin{array}{l}{\displaystyle \sum _{k=0}^{\infty }E{\Vert X^{k+1}-X^k\Vert }^2+{\displaystyle \sum _{k=0}^{\infty }E{\Vert Y^{k+1}-Y^k\Vert }^2}}\\ \le \frac{1}{M}\left[\psi \left(X^0,Y^0\right)-{\psi }^{*}\right]\\ +\frac{1}{2M}{\displaystyle \sum _{k=0}^{\infty }\left[{\alpha }_{x,+}^k{\left({\sigma }_{x,+}^k\right)}^2+{\alpha }_x^k{\left({\sigma }_x^k\right)}^2+{\alpha }_{y,+}^k{\left({\sigma }_{y,+}^k\right)}^2+{\alpha }_y^k{\left({\sigma }_y^k\right)}^2\right]}\\ <\infty ,\end{array}$

由此我们可以得到$\underset{k\to \infty }{\lim }E{\Vert X^{k+1}-X^k\Vert }^2=0$ ，$\underset{k\to \infty }{\lim }E{\Vert Y^{k+1}-Y^k\Vert }^2=0$ 。进一步可以得到$\underset{k\to \infty }{\lim }E\Vert X^{k+1}-X^k\Vert =0$ ，$\underset{k\to \infty }{\lim }E\Vert Y^{k+1}-Y^k\Vert =0$ 。

4. 总结

本文提出一种随机邻近牛顿型交替极小化算法用以求解大规模有限和形式的非凸非光滑复合优化问题，相较于邻近交替线性极小化算法PALM，本文采用的随机梯度算法可大大降低计算成本。此外，本文通过残差方程引入目标函数的二阶信息以提升算法的收敛速度。在目标函数非凸的情形下，本文给出了算法的收敛性分析，建立了随机邻近牛顿型交替极小化算法在期望意义下的收敛性。