有向网络中基于动量方法的加速行随机优化

Accelerated Row-Stochastic Optimization over Directed Networks Based on Momentum Methods

摘要: 本文研究了有向网络下的分布式凸优化问题，并在现有分布式算法的基础上提出了一种新颖的分布式动量加速算法，叫做ARNH。该算法采用行随机矩阵和异构步长，有效克服网络不平衡性的同时提高了网络灵活性。此外，为了实现更快的收敛速率，ARNH采用Nesterov梯度法和Heavy-Ball法相结合的双加速机制。在局部目标函数可微且强凸的假设下，本文证明通过选取合适的步长和动量参数，算法可使节点状态渐近收敛到全局最优解。最后，在仿真实验中将ARNH与相关算法进行性能比较，验证了新算法的优越性。

Abstract: In this paper, we study the distributed convex optimization problems over directed networks, and propose a novel distributed momentum acceleration algorithm called ARNH based on the existing distributed algorithms. ARNH uses row-stochastic matrix and heterogeneous step size, which effec-tively overcomes the network imbalance and improves the network flexibility. Furthermore, in or-der to achieve faster convergence, ARNH employs a double acceleration mechanism combining Nesterov gradient method and heavy-ball method. Under the assumption that the local objective function is differentiable and strongly convex, it is proved that the node state can be asymptotically converged to the global optimal solution by choosing appropriate step-sizes and momentum pa-rameters. Finally, the superiority of the new algorithm is verified by comparing the performance of ARNH with related algorithms in simulation experiments.

1. 引言

近年来，分布式优化受到了越来越多的关注，与传统的集中控制优化策略不同，分布式优化不需要集中的数据控制，可以有效减轻通信负担，节省通信成本，增强网络可扩展性。得益于上述优势，分布式优化算法被广泛应用于统计估计 [1] 、机器学习 [2] [3] [4] 、能源调度 [5] [6] 、网络化多智能体系统的控制 [7] 等领域。

分布式优化的研究早期是在无向网络上进行的，Nedić等在文献 [8] 中为解决分布式无约束优化问题突破性地提出了分布式次梯度算法(DGD)，但该算法受衰减步长影响存在收敛速度较慢的缺陷。为了达到更快的收敛速度，Shi等在文献 [9] 中通过对前一次迭代信息的再次使用提出了即使采用固定步长也可实现线性收敛的EXTRA算法。随后，Qu等人通过结合梯度追踪技术和不精确梯度法，在文献 [10] 中提出了适用于时变通信网络的DIGing算法，当局部目标函数强凸且光滑，该算法可使节点渐近收敛到全局最优解。此后，Jakovetić等在文献 [11] 中揭示了EXTRA和DIGing之间的差异在于原始误差对对偶误差的影响不同，并通过推导出一种新的方法对上述两种方法进行统一。

上述算法要求节点间的信息传输是对称且双向的，这在实际网络系统中很难实现，因此研究有向网更具有实用性。针对有向网络下的分布式无约束凸优化问题，Xi等通过运用push-sum协议 [12] 设计了一种基于广播通信的次梯度下降算法 [13] ，该算法采用列随机权重矩阵和衰减步长，虽然有效克服了有向网络的不平衡性，但只能达到次线性收敛。为解决收敛速度过慢的问题，Kempe等通过将push-sum协议与EXTRA算法相结合，在文献 [14] 中提出了可以实现线性收敛的DEXTRA算法。进一步地，文献 [15] 考虑了更一般的时变网络，提出了一种带有异构步长的有向图算法(push-DIGing)，该算法不仅为步长提供较广阔的选择范围，而且能实现更快收敛。此外，文献 [16] [17] 提出一类算法可同时使用了行和列随机权重矩阵来实现在强连通有向图中的线性收敛。

上述方法虽能有效应用于有向网络，但列随机矩阵的使用需要节点知道其自身出度，这在基于广播通信的网络中是不符合实际的。为了突破这一严苛条件，文献 [18] [19] 中提出了一类只使用行随机权重矩阵的分布式算法，此类算法通过引入辅助变量来消除网络不平衡性，当目标函数强凸且具有Lipschitz连续梯度时，可实现线性收敛。在此基础上，Xin等人在文献 [20] 中进一步放宽了对步长的限制，设计出采用异构步长的行随机优化算法(FROST)。随后，文献 [21] 基于Nesterov加速机制提出了FROST算法的加速版本，文献 [22] 将FROST与heavy-ball和Nesterov动量项相结合，以实现更快收敛。除此之外，还有一些单使用行随权重机矩阵的原始对偶算法 [23] [24] ，与现有的有向网络下的分布式算法相比，此类方法在没有显式使用梯度跟踪技术(GT)的情况下也具有线性收敛性。

基于上述研究，本文在文献 [11] 的基础上，结合Push-sum协议提出了一种可适用于有向网络的加速行随机分布式优化算法(ARNH)，并通过采用异构步长和双加速机制，在提高网络灵活性和保证节点隐私性的同时加快了收敛速度。后续证明在一定的假设条件下，ARNH可以实现线性收敛，最后，根据数值实验结果验证了该算法相较于现有的有向图算法有更好的收敛性能。

2. 预备知识

2.1. 问题描述

在一个由n个节点组成的网络系统中，节点间的信息交换可用图 $\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$ 进行描述，其中 $\mathcal{V}=\left\{1,\cdots ,\text{n}\right\}$ 是有限的非空点集合， $\mathcal{E}=\left\{\left(i,j\right):i,j\in \mathcal{V}\right\}$ 为边集合。若有 $\left(i,j\right)\in \mathcal{E}$ ，那么称节点j是节点i的邻居，对节点i，我们将其入度邻居定义为 $N_i^{in}=\left\{j\in \mathcal{V}|\left(j,i\right)\in \mathcal{E}\right\}$ ，相应的其出度邻居用 $N_i^{out}=\left\{j\in \mathcal{V}|\left(i,j\right)\in \mathcal{E}\right\}$ 表示，其中出度邻居的个数被定义为节点i的出度。若对任意边 $\left(i,j\right)\in \mathcal{V}$ 必有相应的边 $\left(j,i\right)\in \mathcal{V}$ 存在，该网络拓扑图为无向图，反之为有向图。若图中任意两个节点都存在一条有向路径，那么称此图是强连通的。

分布式优化即指上述网络中的所有节点共同解决以下分布式优化问题：

$\underset{\tilde{s}\in {\text{R}}^{\text{p}}}{\min }f\left(\tilde{s}\right)=\frac{1}{\text{n}}{\displaystyle \underset{i=1}{\overset{\text{n}}{\sum }}{f}_i\left(\tilde{s}\right)}$ (1)

其中 $\tilde{s}\in {\text{R}}^{\text{np}}$ 为全局决策变量， $f_i\left(\tilde{s}\right):{\text{R}}^{\text{p}}\to \text{R}$ 为节点i私有的局部目标函数。若以分布形式来解决问题(1)，需要引入一个变量来模拟节点状态，则上述优化问题可转化为：

$\begin{array}{l}\underset{s\in {\text{R}}^{\text{np}}}{\min }f\left(s\right)=\frac{1}{\text{n}}{\displaystyle \underset{i=1}{\overset{\text{n}}{\sum }}{f}_i\left(s_i\right)}\\ \text{s}\text{.t}\text{.}{s}_i=s_j\forall i,j=1,2,\cdots ,\text{n}\end{array}$ (2)

其中 $s=\left[s_1^{\text{T}},s_2^{\text{T}},\cdots ,s_{\text{n}}^{\text{T}}\right]\in {\text{R}}^{\text{np}}$ ，因为问题(1)和(2)等价，则问题(2)的最优解可写为 $s^{*}=1\otimes {\tilde{s}}^{*}\in {\text{R}}^{\text{np}}$ 。

2.2. 相关定义和假设

定义2.1若矩阵 $A=\left[a_{ij}\right]$ 每一行(列)求和都为1，称矩阵为行(列)随机矩阵。若该矩阵同时满足行随机与列随机，那么称矩阵 $A=\left[a_{ij}\right]$ 为双随机矩阵。

定义2.2若一个连续可微函数 $f:{\text{R}}^{\text{p}}\to \text{R}$ ，对任意的 ${\tilde{s}}_1,{\tilde{s}}_2\in {\text{R}}^{\text{p}}$ 存在 $\mu$ 使得：

$f\left({\tilde{s}}_1\right)\ge f\left({\tilde{s}}_2\right)+\nabla f{\left({\tilde{s}}_2\right)}^{\text{T}}\left({\tilde{s}}_1-{\tilde{s}}_2\right)+\frac{\mu }{2}{\Vert {\tilde{s}}_1-{\tilde{s}}_2\Vert }^2$ (3)

成立，则称函数f是 $\mu$ -强凸，其中 $\mu$ 是强凸系数。

定义2.3若一个连续可微函数 $f:{\text{R}}^{\text{p}}\to \text{R}$ ，对任意的 ${\tilde{s}}_1,{\tilde{s}}_2\in {\text{R}}^{\text{p}}$ 存在l使得：

$\Vert \nabla f\left({\tilde{s}}_2\right)-\nabla f\left({\tilde{s}}_1\right)\Vert \le l{\Vert {\tilde{s}}_2-{\tilde{s}}_1\Vert }^2$ (4)

成立，则称函数f是l-光滑或简称光滑，其中l是Lipschitz常数。

假设2.1网络拓扑图 $\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$ 强连通。

假设2.2局部目标函数 $f_i:{\text{R}}^{\text{p}}\to \text{R}$ 强凸且光滑。

2.3. 算法发展

1) Heavy-ball方法

Polyak为解决一般优化问题在文献 [25] 中提出了Heavy-ball方法：

$x_{k+1}=x_k-\alpha \nabla f\left(x_k\right)+\eta \left(x_k-x_{k-1}\right)$

其中 $\eta \left(x_k-x_{k-1}\right)$ 为重球动量项，文中指出当步长 $\alpha$ 和动量参数 $\eta$ 的选取满足约束条件时，该算法可达到比一般梯度下降法更快的收敛速度，因此后续有学者将该方法引入分布式优化算法 [23] [26] 中以实现更快收敛。

2) Nesterov梯度法

文献 [26] 对一阶梯度法使用历史信息提出了Nesterove梯度方法：

$\begin{array}{l}{x}_{k+1}=s_k-\alpha \nabla f\left(s_k\right)\\ s_{k+1}=x_{k+1}+\eta \left(x_{k+1}-x_k\right)\end{array}$

其中 $\beta \left(x_{k+1}-x_k\right)$ 为Nesterov动量项，当目标函数满足强凸且光滑条件， $\alpha =\frac{1}{l}$ 且 $\beta =\frac{\sqrt{l}-\sqrt{\mu }}{\sqrt{l}+\sqrt{\mu }}$ 时，该算法可以达到 $O\left({\left(1-\sqrt{\alpha \mu }\right)}^k\right)$ 的收敛速率，这比相同情况下的梯度下降法更快，因此后续有学者将其应用到

分布式算法 [22] [23] 中。

受上述算法的启发，我们将动量项与文献 [11] 中的算法相结合，设计出一种行随机加速优化算法(ARNH)。所提出的算法中，对任意第 $k\in N$ 次迭代，每个节点 $i\in \mathcal{V}$ 持有四个变量， $x_k^i$ 、 $s_k^i$ 、 $v_k^i$ 和 $u_k^i$ ，根据如下规则进行更新

$x_{k+1}^i={\displaystyle \underset{j=1}{\overset{\text{n}}{\sum }}{r}_{ij}{s}_k^j-{\alpha }_i\left(\frac{\nabla f_i\left(s_k^i\right)}{{\left[v_k^i\right]}_i}+u_k^i\right)}+{\eta }_i\left(x_k^i-x_{k-1}^i\right)$ (5)

$s_{k+1}^i=x_{k+1}^i+{\eta }_i\left(x_{k+1}^i-x_k^i\right)$ (6)

$u_{k+1}^i=u_k^i-{\displaystyle \underset{j=1}{\overset{\text{n}}{\sum }}{l}_{ij}\left(\frac{\nabla f_j\left(s_k^j\right)}{{\left[v_k^j\right]}_j}+u_k^j-{\displaystyle \underset{l=1}{\overset{\text{n}}{\sum }}{b}_{jl}{s}_k^l}\right)}$ (7)

$v_{k+1}^i={\displaystyle \underset{j=1}{\overset{\text{n}}{\sum }}{r}_{ij}{v}_k^j}$ (8)

算法初始化设定任意 $x_0^i=s_0^i\in {\text{R}}^{\text{p}}$ ， $u_k^i=0_{\text{p}}$ 和 $v_0^i=e_i$ ，权重矩阵 $R=\left[r_{ij}\right]$ 为行随机矩阵， $L=\left[l_{ij}\right]=I_n-R$ ，矩阵 $B=\left[b_{ij}\right]$ 为 $\text{n}\times \text{n}$ 维的行随机矩阵，并且满足有 $b\in \text{R}$ 存在使得 $B{1}_{\text{n}}=b{1}_{\text{n}}$ 成立。 ${\alpha }_i$ 和 ${\eta }_i$ 分别对应节点i的步长和动量参数。为了更好地分析算法收敛性，我们将ARNH改写成矩阵形式前需要引入必要符号：

$\begin{array}{l}\alpha ={\left[{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_{\text{n}}\right]}^{\text{T}},D_{\alpha }=diag\left\{\alpha \right\}\otimes I_{\text{p}},V_k={\left[v_k^1,v_k^2,\cdots ,v_k^{\text{n}}\right]}^{\text{T}},\bar{B}=B\otimes I_{\text{p}},\bar{L}=L\otimes I_{\text{p}},\\ \eta ={\left[{\eta }_1,{\eta }_2,\cdots ,{\eta }_{\text{n}}\right]}^{\text{T}},D_{\eta }=diag\left\{\eta \right\}\otimes I_{\text{p}},{\bar{V}}_k=diag\left\{V_k\right\}\otimes I_{\text{p}},\bar{R}=R\otimes I_{\text{p}}.\end{array}$

那么ARNH算法可转换为如下矩阵形式：

$x_{k+1}=\bar{R}{s}_k-D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k\right)+D_{\eta }\left(x_k-x_{k-1}\right)$ (9)

$s_{k+1}=x_{k+1}-D_{\eta }\left(x_{k+1}-x_k\right)$ (10)

$u_{k+1}=u_k-\bar{L}\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k-\bar{B}{s}_k\right)$ (11)

$V_{k+1}=\bar{R}{V}_k$ (12)

其中 $\nabla F\left(s_k\right)$ 、 $x_k$ 、 $s_k$ 和 $u_k$ 被分别定义为 $\nabla F\left(x_k\right)={\left[\nabla f_1{\left(x_k^1\right)}^{\text{T}},\nabla f_2{\left(x_k^2\right)}^{\text{T}},\cdots ,\nabla f_{\text{n}}{\left(x_k^{\text{n}}\right)}^{\text{T}}\right]}^{\text{T}}$ 、 $x_k={\left[{\left(x_k^1\right)}^{\text{T}},{\left(x_k^2\right)}^{\text{T}},\cdots ,{\left(x_k^{\text{n}}\right)}^{\text{T}}\right]}^{\text{T}}$ 、 $s_k={\left[{\left(s_k^1\right)}^{\text{T}},{\left(s_k^2\right)}^{\text{T}},\cdots ,{\left(s_k^{\text{n}}\right)}^{\text{T}}\right]}^{\text{T}}$ 和 $u_k={\left[{\left(u_k^1\right)}^{\text{T}},{\left(u_k^2\right)}^{\text{T}},\cdots ,{\left(u_k^{\text{n}}\right)}^{\text{T}}\right]}^{\text{T}}$ 。

3. 算法收敛性证明

$\begin{array}{l}{V}_{\infty }=\underset{k\to \infty }{\lim V_k},\hfill \\ {\bar{V}}_k=diag\left(V_k\right),\hfill \end{array}\begin{array}{l}v=\underset{k\ge 0}{\sup }\Vert V_k\Vert ,\hfill \\ \hat{v}=\underset{k\ge 0}{\sup }\Vert {\bar{V}}_k^{-1}\Vert ,\hfill \end{array}\begin{array}{l}\bar{\eta }=\underset{i}{\max }\left\{{\eta }_i\right\},\hfill \\ \bar{\alpha }=\underset{i}{\max }\left\{{\alpha }_i\right\},\hfill \end{array}\begin{array}{l}\tau =\Vert \bar{R}-I_{\text{np}}\Vert ,\lambda =\Vert \bar{R}+I_{\text{np}}\Vert ,\hfill \\ \gamma =\Vert I_{\text{np}}-{\bar{V}}_{\infty }\Vert .\hfill \end{array}$

3.1. 辅助引理

引理3.1 [24] 考虑由行随机矩阵R生成的 ${\bar{V}}_k$ ，对于任意的 $k\in N$ ，有下列不等式成立

$\Vert {\bar{V}}_k-{\bar{V}}_{\infty }\Vert \le k_1{\sigma }^k$

其中 $k_1$ 为大于0的常数， $\sigma \in \left(0,1\right)$ 为收缩因子。

引理3.2 [22] 考虑由行随机矩阵R生成的 ${\bar{V}}_k$ ，对于所有的 $k\in N$ ，有下列不等式成立

$\Vert {\bar{V}}_k^{-1}-{\bar{V}}_{\infty }^{-1}\Vert \le k_1\sqrt{\text{n}}{\hat{v}}^2{\sigma }^k$

其中 $\sigma \in \left(0,1\right)$ 为收缩因子在引理1中被定义，其中 $k_1$ 为大于0的常数。

引理3.3 [21] 给定 $0<\alpha <\frac{2}{\text{n}l}$ ，令 $\omega =\max \left\{\left|1-\alpha \text{n}\mu \right|,\left|1-\alpha \text{n}l\right|\right\}$ ，如果假设2.2成立，那么对于 $\forall x\in {\text{R}}^{\text{np}}$ ，我们有

$\Vert x-\alpha \nabla F\left(x\right)-x^{*}\Vert \le \omega {\Vert x-x^{*}\Vert }_2$

引理3.2建立了 ${\bar{V}}_k^{-1}$ 的线性收敛性。引理3.3指出，在集中式梯度法中，当前迭代值与最优解之间的距离在每次迭代中收缩。

引理3.4 [21] 对于一个非负矩阵 $X\in {\text{R}}^{\text{n}\times \text{n}}$ 和正向量 $x\in {\text{R}}^{\text{n}}$ ，如果有 $Xx<\zeta x$ ，那么 $\rho \left(X\right)<\zeta$ 。

3.2. 收敛关系

被提出的算法收敛关系将通过推导如下四项误差的上界得到

1) 对偶误差： $\Vert u_{k+1}-u^{\text{*}}\Vert$ ；

2) 最优误差： $\Vert {\hat{x}}_{k+1}-s^{*}\Vert$ ；

3) 状态误差:： $\Vert x_k-x_{k-1}\Vert$ ；

4) 一致性误差： $\Vert x_{k+1}-{\hat{x}}_{k+1}\Vert$ 。

其中 ${\hat{x}}_{k+1}={\bar{V}}_{\infty }{x}_{k+1}$ 。

引理 3.5 若假设2.1-2.2成立，对任意 $k\ge 0$ 有下列不等式成立

$\begin{array}{c}\Vert u_{k+1}-u^{\ast }\Vert \le \sigma \Vert u_k-u^{\ast }\Vert +\left(\Vert B\Vert +\hat{v}l\right)\Vert L\Vert \Vert x_k-{\hat{x}}_k\Vert +\left(\Vert B\Vert +\hat{v}l\right)\Vert L\Vert \Vert {\hat{x}}_k-s^{*}\Vert \\ +\bar{\eta }\Vert L\Vert \left(\Vert B\Vert +\hat{v}l\right)\Vert x_k-x_{k-1}\Vert +{\hat{v}}^2{\sigma }^k{k}_1\Vert L\Vert \Vert \nabla F\left(s_k\right)\Vert \end{array}$

证明 考虑k趋近于无穷时算法收敛于 $\left(s^{*},u^{*}\right)$ 根据式子(11)，我们有

$u^{*}=u^{*}-\bar{L}\left({\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+u^{*}-\bar{B}{s}^{*}\right)$ (13)

这意味着 $u^{*}=-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)$ ，则等式(13)可变换为下列形式

$\begin{array}{c}{u}_{k+1}-u^{\ast }=u_k-u^{\ast }-\bar{L}\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+u_k\right)+\bar{L}\bar{B}{s}_k\\ =\bar{R}\left(u_k-u^{\ast }\right)+\bar{L}\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\right)+\bar{L}\bar{B}{s}_k,\end{array}$ (14)

根据初始化条件 $u_0=0_{\text{np}}$ 可证得 ${\bar{V}}_{\infty }{u}_{k+1}={\bar{V}}_{\infty }{u}_k=0_{\text{np}}$ ，由于 $\bar{L}\bar{B}{s}^{*}=b\bar{L}{s}^{*}=0_{\text{np}}$ ，(14)可改写为

$u_{k+1}-u^{\ast }=\left(\bar{R}-{\bar{V}}_{\infty }\right)\left(u_k-u^{\ast }\right)+\bar{L}\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\right)+\bar{L}\bar{B}\left(s_k-s^{\ast }\right)$ (15)

根据引理2.2~2.3以及假设2，等式(15)右边的第二项可改写为

$\begin{array}{c}\Vert {\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\Vert \le \Vert {\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s_k\right)\Vert +\Vert {\bar{V}}_{\infty }^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\Vert \\ \le \hat{v}l\Vert x_k-{\hat{x}}_k\Vert +\hat{v}l\Vert {\hat{x}}_k-s^{*}\Vert +\bar{\eta }\hat{v}l\Vert x_k-x_{k-1}\Vert +{\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert \end{array}$ (16)

将等式(16)带入等式(15)，并对两边取范数可得

$\begin{array}{c}\Vert u_{k+1}-u^{\ast }\Vert \le \sigma \Vert u_k-u^{\ast }\Vert +\left(\Vert \bar{B}\Vert +\hat{v}l\right)\Vert \bar{L}\Vert \Vert x_k-{\hat{x}}_k\Vert +\left(\Vert \bar{B}\Vert +\hat{v}l\right)\Vert \bar{L}\Vert \Vert {\hat{x}}_k-s^{*}\Vert \\ +\bar{\eta }\Vert \bar{L}\Vert \left(\Vert \bar{B}\Vert +\hat{v}l\right)\Vert x_k-x_{k-1}\Vert +{\hat{v}}^2{\sigma }^k{k}_1\Vert \bar{L}\Vert \Vert \nabla F\left(s_k\right)\Vert \end{array}$ (17)

引理 3.6 若假设1~3成立，对 $k\ge 0$ 下面不等式成立：

$\begin{array}{c}\Vert x_{k+1}-{\hat{x}}_{k+1}\Vert \le \bar{\alpha }\gamma \Vert u_k-u^{\ast }\Vert +\left(\sigma +\bar{\alpha }\gamma \hat{v}l\right)\Vert x_k-{\hat{x}}_k\Vert +\bar{\alpha }\gamma \hat{v}l\Vert {\hat{x}}_k-s^{*}\Vert \\ +\left(\lambda \gamma \bar{\eta }+\bar{\alpha }\gamma \bar{\eta }\hat{v}l\right)\Vert x_k-x_{k-1}\Vert +\bar{\alpha }\gamma {\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert \end{array}$

证明 结合(9)和(10)可得

$x_{k+1}=\bar{R}{x}_k-D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k\right)+\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)$ (18)

在上式两端乘以 $\left(I_{np}-{\bar{V}}_{\infty }\right)$ 并使用 $\bar{R}{\bar{V}}_{\infty }={\bar{V}}_{\infty }$ ，我们有

$\begin{array}{c}{x}_{k+1}-{\hat{x}}_{k+1}=\left(\bar{R}-{\bar{V}}_{\infty }\right)x_k+\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)\\ -\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k\right),\end{array}$ (19)

根据 $\left(\bar{R}-{\bar{V}}_{\infty }\right)x_k=\left(\bar{R}-{\bar{V}}_{\infty }\right)\left(x_k-{\hat{x}}_k\right)$ ，进一步可得

$\begin{array}{c}{x}_{k+1}-{\hat{x}}_{k+1}=\left(\bar{R}-{\bar{V}}_{\infty }\right)\left(x_k-{\hat{x}}_k\right)+\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)\\ -\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+u_k\right)\\ =\left(\bar{R}-{\bar{V}}_{\infty }\right)\left(x_k-{\hat{x}}_k\right)+\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)\\ -\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\right)\\ -\left(I_{\text{np}}-{\bar{V}}_{\infty }\right)D_{\alpha }\left({\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+u_k\right),\end{array}$ (20)

对式子(20)取范数并将式子(16)带入，我们可得

$\begin{array}{c}\Vert x_{k+1}-{\hat{x}}_{k+1}\Vert \le \bar{\alpha }\gamma \Vert u_k-u^{\ast }\Vert +\left(\sigma +\bar{\alpha }\gamma \hat{v}l\right)\Vert x_k-{\hat{x}}_k\Vert +\bar{\alpha }\gamma \hat{v}l\Vert {\hat{x}}_k-s^{*}\Vert \\ +\left(\lambda \gamma \bar{\eta }+\bar{\alpha }\gamma \bar{\eta }\hat{v}l\right)\Vert x_k-x_{k-1}\Vert +\bar{\alpha }\gamma {\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert \end{array}$

引理3.7 若假设1~3成立，对 $k\ge 0$ 下面不等式成立：

$\begin{array}{c}\Vert x_{k+1}-x_k\Vert \le \left(\tau +\bar{\alpha }\hat{v}l\right)\Vert x_k-{\hat{x}}_k\Vert +\left(\bar{\alpha }\bar{\eta }\hat{v}l+\bar{\eta }\lambda \right)\Vert x_k-x_{k-1}\Vert \\ +\bar{\alpha }\hat{v}l\Vert {\hat{x}}_k-s^{*}\Vert +\bar{\alpha }{\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert +\bar{\alpha }\Vert u_k-u^{\ast }\Vert \end{array}$

在等式(9)两边同时减去 $x_k$ 并运用(10)可得

$x_{k+1}-x_k=\left(\bar{R}-I_{\text{np}}\right)x_k-D_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k\right)+\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)$

根据 $\bar{R}{\hat{x}}_k={\hat{x}}_k$ ，我们有下式成立

$\begin{array}{c}{x}_{k+1}-x_k=\left(\bar{R}-I_{\text{np}}\right)\left(x_k-{\hat{x}}_k\right)+\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)\\ +D_{\alpha }\left({\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)+u_k+{\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\right),\end{array}$ (21)

对(21)两边同时取范数，我们有

$\begin{array}{c}\Vert x_{k+1}-x_k\Vert \le \left(\tau +\bar{\alpha }\hat{v}l\right)\Vert x_k-{\hat{x}}_k\Vert +\left(\bar{\eta }\bar{\alpha }\hat{v}l+\lambda \bar{\eta }\right)\Vert x_k-x_{k-1}\Vert \\ +\bar{\alpha }\hat{v}l\Vert {\hat{x}}_k-s^{*}\Vert +\bar{\alpha }{\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert +\bar{\alpha }\Vert u_k-u^{\ast }\Vert \end{array}$

引理3.7证明完毕。

引理3.8 若假设1~3成立，对 $k\ge 0$ 下列不等式成立

$\begin{array}{c}\Vert {\hat{x}}_{k+1}-s^{*}\Vert \le \left(\omega +v\hat{v}l{\Delta }_{\alpha }\right)\Vert {\hat{x}}_k-s^{*}\Vert +\left(\bar{\alpha }+{\Delta }_{\alpha }\right)v\hat{v}l\Vert x_k-{\hat{x}}_k\Vert +{\Delta }_{\alpha }v\Vert u_{k+1}-u^{\text{*}}\Vert \\ +\left(\bar{\alpha }\hat{v}l+{\Delta }_{\alpha }\hat{v}l+\lambda \right)v\bar{\eta }\Vert x_k-x_{k-1}\Vert +\left(\bar{\alpha }+{\Delta }_{\alpha }\right)v{\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert \end{array}$

其中 ${\Delta }_{\alpha }=\bar{\alpha }-{\alpha }_{\min }$ 。

根据 ${\bar{V}}_{\infty }\bar{R}={\bar{V}}_{\infty }$ 在等式(9)两边同时乘 ${\bar{V}}_{\infty }$ 并运用(10)可得

${\bar{V}}_{\infty }{x}_{k+1}={\bar{V}}_{\infty }{x}_k+{\bar{V}}_{\infty }\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)-{\bar{V}}_{\infty }{D}_{\alpha }\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)+u_k\right)$ (22)

根据 ${\bar{V}}_{\infty }{u}_{k+1}={\bar{V}}_{\infty }{u}_k=0_{\text{np}}$ ，在(22)右边加减 $\bar{\alpha }{\bar{V}}_{\infty }{\bar{V}}_{\infty }^{-1}\nabla F\left({\hat{x}}_k\right)$ ，我们可得

$\begin{array}{c}{\bar{V}}_{\infty }{x}_{k+1}={\bar{V}}_{\infty }{x}_k-\bar{\alpha }{\bar{V}}_{\infty }{\bar{V}}_{\infty }^{-1}\nabla F\left({\hat{x}}_k\right)+\bar{\alpha }{\bar{V}}_{\infty }\left({\bar{V}}_{\infty }^{-1}\nabla F\left({\hat{x}}_k\right)-{\bar{V}}_k^{-1}\nabla F\left(s_k\right)\right)\\ +{\bar{V}}_{\infty }\left(\bar{\alpha }{I}_{\text{np}}-D_{\alpha }\right)\left({\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s^{*}\right)\right)\\ +{\bar{V}}_{\infty }\left(\bar{\alpha }{I}_{\text{np}}-D_{\alpha }\right)\left(u_{k+1}-u^{\text{*}}\right)+{\bar{V}}_{\infty }\left(\bar{R}+I_{\text{np}}\right)D_{\eta }\left(x_k-x_{k-1}\right)\end{array}$

根据假设2和引理2.3，(23)式的第二项满足下列不等式

$\begin{array}{c}\Vert {\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left({\hat{x}}_k\right)\Vert \le \Vert {\bar{V}}_k^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left(s_k\right)\Vert +\Vert {\bar{V}}_{\infty }^{-1}\nabla F\left(s_k\right)-{\bar{V}}_{\infty }^{-1}\nabla F\left({\hat{x}}_k\right)\Vert \\ \le {\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert +\hat{v}l\Vert x_k-{\hat{x}}_k\Vert +\bar{\eta }\hat{v}l\Vert x_k-x_{k-1}\Vert +\bar{\eta }\hat{v}l\Vert x_k-x_{k-1}\Vert \end{array}$ (23)

将(23)和(16)带入(22)，并对等式两边减去 $s^{*}$ 同时取范数可得

$\begin{array}{c}\Vert {\hat{x}}_{k+1}-s^{*}\Vert \le \left(\omega +v\hat{v}l{\Delta }_{\alpha }\right)\Vert {\hat{x}}_k-s^{*}\Vert +\left(\bar{\alpha }+{\Delta }_{\alpha }\right)v\hat{v}l\Vert x_k-{\hat{x}}_k\Vert +{\Delta }_{\alpha }v\Vert u_{k+1}-u^{\text{*}}\Vert \\ +\left(\bar{\alpha }\hat{v}l+{\Delta }_{\alpha }\hat{v}l+\lambda \right)v\bar{\eta }\Vert x_k-x_{k-1}\Vert +\left(\bar{\alpha }+{\Delta }_{\alpha }\right)v{\hat{v}}^2{\sigma }^k{k}_1\Vert \nabla F\left(s_k\right)\Vert \end{array}$

3.3. 主要结果

在呈现主要结果之前，根据以上所提及的结果和符号，我们进行如下定义：

$\begin{array}{l}{t}_k=\left[\begin{array}{c}\Vert u_k-u^{*}\Vert \\ \Vert x_k-{\hat{x}}_k\Vert \\ \Vert {\hat{x}}_k-s^{*}\Vert \\ \Vert x_k-x_{k-1}\Vert \end{array}\right],H_k={\sigma }^k\left[\begin{array}{cccc}{\hat{v}}^2{\sigma }^k{k}_1\Vert \bar{L}\Vert & 0& 0& 0\\ \bar{\alpha }\gamma {\hat{v}}^2{k}_1& 0& 0& 0\\ v{\hat{v}}^2{k}_1\left({\Delta }_{\alpha }+\bar{\alpha }\right)& 0& 0& 0\\ \bar{\alpha }{\hat{v}}^2{k}_1& 0& 0& 0\end{array}\right],s_k=\left[\begin{array}{c}\Vert \nabla F\left(s_k\right)\Vert \\ 0\\ 0\\ 0\end{array}\right]\\ J_{\left(\alpha ,\eta \right)}=\left[\begin{array}{cccc}\sigma & w_1& w_1& \bar{\eta }{w}_1\\ \bar{\alpha }\gamma & \lambda +\bar{\alpha }{w}_2& \bar{\alpha }{w}_2& \lambda \gamma \bar{\eta }+\bar{\alpha }\bar{\eta }{w}_2\\ v{\Delta }_{\alpha }& \left({\Delta }_{\alpha }+\bar{\alpha }\right)w_3& \omega +{\Delta }_{\alpha }{w}_3& \bar{\eta }\left(\bar{\alpha }{w}_3+{\Delta }_{\alpha }{w}_3+\lambda v\right)\\ \bar{\alpha }& \tau +\bar{\alpha }{w}_4& \bar{\alpha }{w}_4& \bar{\eta }\left(\bar{\alpha }{w}_4+\lambda \right)\end{array}\right],\begin{array}{l}{w}_1=\left(\Vert \bar{B}\Vert +\hat{v}l\right)\Vert \bar{L}\Vert ,\hfill \\ \begin{array}{l}{w}_2=\gamma \hat{v}l,\\ w_3=v\hat{v}l,\end{array}\hfill \\ w_4=\hat{v}l.\hfill \end{array}\end{array}$

定理3.1 若假设1~2成立，根据引理3.5~3.8有下列线性不等式成立

$t_{k+1}\le J_{\left(\alpha ,\eta \right)}{t}_k+H_k{s}_k$

当最大步长 $\bar{\alpha }$ 满足：

$0\le \bar{\alpha }<\min \left\{\frac{c_2-\lambda \left(\bar{\eta }{c}_4+c_2\right)}{\gamma c_1+w_2{c}_2+w_2{c}_3+w_2\bar{\eta }{c}_4},\frac{c_4-\tau c_2}{c_1+w_4{c}_2+w_4{c}_3+\bar{\eta }{w}_4{c}_4},\frac{1}{nl}\right\}$ (24)

动量参数 $\bar{\eta }$ 满足：

$\begin{array}{l}0\le \bar{\eta }<\min \{\frac{\left(1-\lambda \right)c_2-\bar{\alpha }\left(\gamma c_1+w_2{c}_2+w_2{c}_3\right)}{\lambda c_4+\bar{\alpha }{w}_2{c}_4},\frac{c_4-\tau c_2-\bar{a}\left(c_1+w_4{c}_2+w_4{c}_3\right)}{\lambda c_4+\bar{a}{w}_4{c}_4},\\ \frac{\bar{\alpha }\left(n\mu c_3-w_3{c}_2\right)-{\Delta }_{\alpha }\left(v{c}_1+w_3{c}_2+w_3{c}_3\right)}{n\mu c_3+\bar{\alpha }{w}_3{c}_4+w_3{\Delta }_{\alpha }{c}_4}\}.\end{array}$ (25)

其中 $c_1,c_2,c_3,c_4$ 为随机常数，取值满足：

$0<c_2,\tau c_2<c_4,\frac{w_1\left(c_2+c_3\right)+\bar{\eta }{w}_1{c}_4}{1-\sigma }<c_1,0<c_3<\frac{n\mu c_3-\bar{\eta }{w}_3{c}_4}{w_3}$

最大步长和最小步长之间的差距满足：

$0<{\Delta }_{\alpha }<\frac{\bar{\alpha }\left(n\mu c_3-w_3{c}_2-\bar{\eta }{w}_3{c}_4\right)}{v{c}_1+w_3{c}_2+w_3{c}_3+w_3\bar{\eta }{c}_4}$

则矩阵 $J_{\left(\alpha ,\eta \right)}$ 的谱半径小于1，即 $\rho \left(J_{\left(\alpha ,\eta \right)}\right)<1$ 。

证明 由于 $l>\mu$ 所以 $\omega =1-\bar{\alpha }\text{n}\mu$ ，根据引理4可知存在正向量 $c={\left[c_1,c_2,c_3,c_4\right]}^{\text{T}}\in R_{+}^4$ 使得 $J_{\left(\alpha ,\eta \right)}c<c$ ，即下列不等式组成立

$\{\begin{array}{l}{w}_1\left(c_2+c_3\right)+\bar{\eta }{w}_1{c}_4<\left(1-\sigma \right)c_1,\\ \lambda \gamma \bar{\eta }{c}_4<\left(1-\lambda \right)c_2-\bar{\alpha }\left(\gamma c_1+w_2{c}_2+w_2{c}_3+\bar{\eta }{w}_2{c}_4\right),\\ v\lambda \bar{\eta }{c}_4<\bar{\alpha }\left(n\mu c_3-w_3{c}_2-\bar{\eta }{w}_3{c}_4\right)-{\Delta }_{\alpha }\left(v{c}_1+w_3{c}_2+w_3{c}_3+w_3\bar{\eta }{c}_4\right),\\ \bar{\eta }\lambda c_4<c_4-\tau c_2-\bar{a}\left(c_1+w_4{c}_2+w_4{c}_3+\bar{\eta }{w}_4{c}_4\right).\end{array}$ (26)

为了确保该不等式的左项严格大于0，我们需要下列不等式组成立

$\{\begin{array}{l}0<\left(1-\lambda \right)c_2-\bar{\alpha }\left(\gamma c_1+w_2{c}_2+w_2{c}_3+\bar{\eta }{w}_2{c}_4\right),\\ 0<\bar{\alpha }\left(n\mu c_3-w_3{c}_2-\bar{\eta }{w}_3{c}_4\right)-{\Delta }_{\alpha }\left(v{c}_1+w_3{c}_2+w_3{c}_3+w_3\bar{\eta }{c}_4\right),\\ 0<c_4-\tau c_2-\bar{a}\left(c_1+w_4{c}_2+w_4{c}_3+\bar{\eta }{w}_4{c}_4\right).\end{array}$ (27)

通过计算可知要使不等式(26)第一项成立，最大步长 $\bar{\alpha }$ 需要满足：

$\bar{\alpha }<\frac{c_2-\lambda \left(\bar{\eta }{c}_4+c_2\right)}{\gamma c_1+w_2{c}_2+w_2{c}_3+w_2\bar{\eta }{c}_4}$ (28)

根据式子(27)的第二项，参数 $c_2$ 和 $\bar{\alpha }$ 必须满足下列条件：

$0<c_3<\frac{n\mu c_3-\bar{\eta }{w}_3{c}_4}{w_3},0<{\Delta }_{\alpha }<\frac{\bar{\alpha }\left(n\mu c_3-w_3{c}_2-\bar{\eta }{w}_3{c}_4\right)}{v{c}_1+w_3{c}_2+w_3{c}_3+w_3\bar{\eta }{c}_4}$ (29)

根据式子(27)的第三项，可得

$c_4>\tau c_2,\bar{a}<\frac{c_4-\tau c_2}{c_1+w_4{c}_2+w_4{c}_3+\bar{\eta }{w}_4{c}_4}$ (30)

为了确保式子(26)成立，必须有

$\frac{w_1\left(c_2+c_3\right)+\bar{\eta }{w}_1{c}_4}{1-\sigma }<c_1$ (31)

首先选择合适的参数 $c_2$ 之后，根据式子(29)选择 $c_3$ ，根据式子(30)选择 $c_4$ ，最后选择满足(31)的 $c_1$ ，

则可以找出符合要求的正向量c。由于步长的选择需要满足原始条件 $\bar{\alpha }<\frac{2}{nl}$ ，结合(28)和(30)将式子进行整理得到步长的最终取值范围：

$0\le \bar{\alpha }<\min \left\{\frac{c_2-\lambda \left(\bar{\eta }{c}_4+c_2\right)}{\gamma c_1+w_2{c}_2+w_2{c}_3+w_2\bar{\eta }{c}_4},\frac{c_4-\tau c_2}{c_1+w_4{c}_2+w_4{c}_3+\bar{\eta }{w}_4{c}_4},\frac{1}{nl}\right\}$ (32)

根据(26)可以求得最大动量参数 $\bar{\eta }$ 的取值范围如下

$\begin{array}{l}0\le \bar{\eta }<\min \{\frac{\left(1-\lambda \right)c_2-\bar{\alpha }\left(\gamma c_1+w_2{c}_2+w_2{c}_3\right)}{\lambda c_4+\bar{\alpha }{w}_2{c}_4},\frac{c_4-\tau c_2-\bar{a}\left(c_1+w_4{c}_2+w_4{c}_3\right)}{\lambda c_4+\bar{a}{w}_4{c}_4},\\ \frac{\bar{\alpha }\left(n\mu c_3-w_3{c}_2\right)-{\Delta }_{\alpha }\left(v{c}_1+w_3{c}_2+w_3{c}_3\right)}{n\mu c_3+\bar{\alpha }{w}_3{c}_4+w_3{\Delta }_{\alpha }{c}_4}\}.\end{array}$ (33)

当步长和参数选取满足约束时，我们有 $\rho \left(J_{\left(\alpha ,\eta \right)}\right)<1$ 。

引理3.9 [15] 假设所选步长满足(32)，则对于所有 $k\ge 0$ ，下列不等式均成立：

$\begin{array}{l}\Vert J_{\left(\alpha ,\eta \right)}^k\Vert \le {\Gamma }_1{\theta }_1^{k}0<{\theta }_1<1,0<{\Gamma }_1<\infty ,\\ \Vert H_r\Vert \le {\Gamma }_2{\theta }_2^{k}0<{\theta }_1<1,0<{\Gamma }_1<\infty ,\\ \Vert J_{\left(\alpha ,\eta \right)}^{k-r-1}{H}_r\Vert \le \Gamma {\theta }^{k}0\le r\le k-1,\end{array}$

其中 $\theta =\max \left\{{\theta }_1\text{,}{\theta }_2\right\}$ ， $\Gamma ={\Gamma }_1{\Gamma }_2/\theta$ 。

定理3.2 假定假设1~2成立，当步长和动量项满足定理3.1时，由所提出的算法生成的序列 $\left\{x_k\right\}$ 线性收敛于全局最优解 $s^{*}$ ，即存在常数 $p>0$ 使得：

$\Vert x_k-s^{*}\Vert \le 2p{\left(\theta +\xi \right)}^k$

其中 $\theta =\max \left\{{\theta }_1\text{,}{\theta }_2\right\}$ 取自引理3.9， $\xi$ 是满足 $0<\xi +\theta <1$ 的足够小的正常数.

证明 利用数学归纳法对 $t_{k+1}\le J_{\left(\alpha ,\eta \right)}{t}_k+H_k{s}_k$ 进行不断递归，整理后可得到

$t_{k+1}\le J_{\left(\alpha ,\eta \right)}{t}_0+{\displaystyle \underset{r=0}{\overset{k-1}{\sum }}{J}_{\left(\alpha ,\eta \right)}^{k-r-1}{H}_r}{s}_r$ (34)

对(34)两边同时取范数并利用引理3.9我们有

$\Vert t_k\Vert \le \Vert J_{\left(\alpha ,\eta \right)}\Vert \Vert t_0\Vert +{\displaystyle \underset{r=0}{\overset{k-1}{\sum }}\Vert J_{\left(\alpha ,\eta \right)}^{k-r-1}{H}_r\Vert \Vert s_r\Vert }\le \Gamma {\omega }^k\left(\Vert t_0\Vert +{\displaystyle \underset{j=0}{\overset{k-1}{\sum }}\Vert s_r\Vert }\right)$ (35)

进一步，利用三角不等式和假设3对 $\Vert s_r\Vert$ 进行定界

$\begin{array}{c}\Vert s_k\Vert \le \Vert \nabla F\left(V_{\infty }{x}_k\right)-\nabla F\left(s^{*}\right)\Vert +\Vert \nabla F\left(s^{*}\right)\Vert \\ \le l\Vert x_k-V_{\infty }{x}_{k-1}\Vert +l\Vert V_{\infty }{x}_k-s^{*}\Vert +\Vert \nabla F\left(s^{*}\right)\Vert \\ \le 2l\Vert t_k\Vert +\Vert \nabla F\left(s^{*}\right)\Vert \end{array}$ (36)

将(36)代入(35)可得下式成立：

$\Vert t_k\Vert \le \left(\Vert t_0\Vert +2l{\displaystyle \underset{r=0}{\overset{k-1}{\sum }}\Vert t_r\Vert }+k\Vert \nabla F\left(s^{*}\right)\Vert \right)\Gamma {\theta }^k$ (37)

对 $k\ge 0$ ，定义 $a_k\triangleq {\displaystyle \underset{r=0}{\overset{k-1}{\sum }}\Vert t_r\Vert }$ ， $b_k=0$ ， $c_k=l\Gamma {\theta }^k$ ， $d_k\triangleq {\theta }^k\left({\Gamma }_2\Vert t_0\Vert +k\Gamma \Vert \nabla F\left(s^{*}\right)\Vert \right)$ 那么(37)可重写为：

$\Vert t_k\Vert =a_{k+1}-a_k\le c_k{a}_{k+1}+d_k,\forall k>0$

根据引理3.9我们可知 $a_k$ 收敛且有界，则对于任意 $0<\omega <\xi <1$ ，可得

$\underset{k\to \infty }{\lim }\frac{\Vert t_k\Vert }{{\left(\theta +\xi \right)}^k}\le \frac{c_k{a}_{k+1}+d_k}{{\left(\theta +\xi \right)}^k}=0$

因此存在 $p>0$ 使得下式成立

$\Vert t_k\Vert \le p{\left(\theta +\xi \right)}^k,\forall k\ge 0$

由此，我们可得到以下结果

$\Vert x_k-s^{*}\Vert \le \Vert x_k-V_{\infty }{x}_k\Vert +\Vert V_{\infty }{x}_k-s^{*}\Vert \le 2p{\left(\theta +\xi \right)}^k$

即得到定理3.2的结果，证明结束。

4. 数值实验

我们考虑有向图上的分布式逻辑回归问题：

${\tilde{s}}^{*}=\underset{\bar{x}\in {\text{R}}^{\text{p}}}{\arg \min }\frac{\delta }{2}{\Vert \tilde{s}\Vert }^2+{\displaystyle \underset{i=1}{\overset{\text{n}}{\sum }}{\displaystyle \underset{j=1}{\overset{m_i}{\sum }}\ln \left[1+\exp \left(-y_{ij}{c}_{ij}^{\text{T}}\tilde{s}\right)\right]}}$

其中 $\left(c_{ij},y_{ij}\right)\in {\text{R}}^{\text{p}}\times \left\{-1,+1\right\}$ ， $c_{ij}$ 为节点i的第j个数据样本特征向量，其相应的标签用 $y_{ij}$ 表示，n个节点共同处理 $N={\displaystyle {\sum }_{i=1}^{\text{n}}{m}_i}$ 个样本，其中 $m_i$ 对应节点i所需要处理的样本数。若任意节点所需要处理的样本数相同，则上述问题便转化为分布式无约束优化问题：

$f_i\left(\tilde{s}\right)=\frac{\delta }{2\text{n}}{\Vert \tilde{s}\Vert }^2+{\displaystyle \underset{j=1}{\overset{m_i}{\sum }}\ln \left[1+\exp \left(-y_{ij}{c}_{ij}^{\text{T}}\tilde{s}\right)\right]}$

其中正则项 $\frac{\delta }{\text{2n}}{\Vert \tilde{s}\Vert }^2$ 是用以规避数据过拟合。

实验中的初始强连通有向网络由十个节点随机生成，应用规则 $R=I-\frac{1}{2d_{\max }^{in}}{L}_R$ 生成行随机矩阵，其中 $d_{\max }^{in}$ 为最大入度， $L_R$ 是有关于矩阵R的拉普拉斯矩阵。类似地， $C=I-\frac{1}{2d_{\max }^{out}}{L}_C$ 用以列随机矩阵的生成。此外，对于所有的分布式算法，我们使用 ${\left\{r\left(x\right)\right\}}_{k\ge 0}$ 来刻画残差序列，其中 $r\left(k\right)=\frac{\Vert {\bar{x}}_k-{\bar{x}}^{*}\Vert }{\Vert {\bar{x}}_0-{\bar{x}}^{*}\Vert }$ 。

根据定理3.1和3.2可看出ARNH的收敛速率与步长和参数有关，对于动量参数对收敛速率的影响，我们设定步长 $\alpha =0.004$ ，参数 $b=130$ ，动量参数的选取为 $\eta \in \left[0,0.5\right]$ ，算法在不同动量参数下第300次迭代时的残差变化曲线见图1，从中可以看出最优动量参数为0.3。

Figure 1. Performance of ARNH algorithm with different momentum parameters $\eta$

图1. 不同参数 $\eta$ 下ARNH算法性能

实验2测试参数b对算法性能的影响，选取异构步长 $\alpha =0.004$ ，动量参数 $\eta =0.3$ ，将带有不同参数b的算法进行性能比较，从实验结果图2可以观察到ARSD在 $b=130$ 时达到最佳收敛。

Figure 2. Performance of ARNH algorithm with different parameters b

图2. 不同参数b下ARNH算法性能

实验3设定所提出算法的非协作步长 ${\alpha }_i\in \left[0.0035,0.0045\right]$ ，动量参数 ${\eta }_i\in \left[0.3,0.35\right]$ ，参数 $b=130$ ，并ARNH与前沿算法进行比较，所有相关算法的参数已调至最优可获得最佳性能表现，由图3可以看出ARNH相较与现有的分布式一阶算法有较快的收敛速度。

Figure 3. Performance comparison of different algorithms

图3. 不同算法的性能比较

5. 总结

本文提出了一种基于行随机优化的分布式同步动量加速算法，称为ARNH。该算法利用Push-Sum技术消除网络不平衡性，并运用双加速机制提高算法收敛速率。若目标函数强凸且具有Lipschitz连续梯度，本文证明当所选步长和动量参数满足取值范围，ARNH能更快地线性收敛到全局最优解。最后，数值实验验证了理论分析的正确性以及算法的高效性。