求解结构型凸优化问题的一种算法改进

An Improved Algorithm for Solving Structural Convex Optimization Problems

摘要: 本文考虑一个求解结构型凸优化问题的新算法——带随机步长的并行分裂ADMM下降算法，它是基于并行分裂ADMM下降算法和改善步长的收缩算法产生的。新算法改变了步长和更新公式，同时利用服从独立同分布的随机数来扩张步长，提高了ADMM下降算法中因固定步长因子带来的收敛较慢的结果。然后在适当的条件下，证明了该方法是依概率收敛的。最后，通过对来自金融和统计中的一类问题进行的一系列数值实验，验证了新算法的高效性。

Abstract: This paper considers a new algorithm for solving structural convex optimization problems: parallel split ADMM descent algorithm with random step size, which is based on parallel split ADMM descent algorithm and shrinkage algorithm with improved step size. The new algorithm changes the step size and updates formula, and expands the step size by using random numbers subject to independent and identically distributed, which improves the slow convergence result caused by fixed step size factor in ADMM descent algorithm. Then, under appropriate conditions, it is proved that the method converges according to probability. Finally, a series of numerical experiments on a class of problems from finance and statistics verify the efficiency of the new algorithm.

1. 引言

1.1. 研究背景及意义

随着科技快速的发展，如今数字化技术与网络化技术日新月异，大数据正在飞速增长，人类已经迈入一个全新的时代。最优化问题的研究和发展一直受到广泛关注。大数据时代带来许多机遇的同时，也带来许多问题，例如工程、信息、生物等领域，所建立的模型可以转化为等式约束优化问题。

实际问题中一般所求的目标函数问题规模巨大，且可能是非光滑的，传统的内点法等算法往往无法求解这类问题。而根据ADMM算法的核心思想：先分解协调过程，将全局问题分解为多个较容易求解的局部子问题，再求解协调子问题而得到全局问题的解；运用ADMM算法等一阶算法求解这类问题更为适合，所以对ADMM算法的研究非常具有理论意义和应用价值，并且具有巨大的发展潜力。

1.2. 研究现状

Glowinski & Marrocco [1] 及Gabay & Mercier [2] 分别于1975年和1976年最先提出了ADMM算法，现在ADMM算法主要用于解决具有可分离变量的优化问题，它可以解决增广拉格朗日算法所不能解决的问题。50年代中期，有大量文献分析了相似的算法的性质，但当时这一类似算法主要用于解决偏微分方程问题。

本文主要研究以下具有分离结构的约束凸优化问题：

(1)

其中f和g是闭凸连续函数， $A\in {\mathcal{R}}^{r\times n}$ 和 $B\in {\mathcal{R}}^{r\times m}$ 是一个给定的行满秩矩阵， $b\in {\mathcal{R}}^r$ 是一个给定的向量， $\mathcal{X}\subset {\mathcal{R}}^n$ 和 $\mathcal{Y}\subset {\mathcal{R}}^m$ 是非空闭凸集。

针对求解式(1)的算法目前已经有很多种，其增广拉格朗日函数为：

$L_{\rho }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-{\lambda }^{\text{T}}\left(Ax+By-b\right)+\frac{\rho }{2}{\Vert Ax+By-b\Vert }_2^2$

其中， $\lambda \in {\mathcal{R}}^r$ 为拉格朗日乘子， $\rho >0$ 为罚参数。

经典的ADMM算法迭代步骤如下：

$\{\begin{array}{l}{x}^{k+1}=\arg \min \left\{f\left(x\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(Ax+B{y}^k-b\right)+\frac{1}{2}\Vert {Ax+B{y}^k-b\Vert }_H^2|x\in \mathcal{X}\right\}\\ y^{k+1}=\arg \min \left\{g\left(y\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(A{x}^{k+1}+By-b\right)+\frac{1}{2}\Vert {A{x}^k+By-b\Vert }_H^2|y\in \mathcal{Y}\right\}\\ {\lambda }^{k+1}={\lambda }^k-H\left(A{x}^{k+1}+B{y}^{k+1}-b\right)\end{array}$

其中， $H\in {\mathcal{R}}^{r\times r}$ 是给定的对称正定阵。

与增广拉格朗日乘子算法(ALM) [3] [4] [5] 相比，ALM算法可以同时求解两个分离的变量，而ADMM算法是对变量交替进行求解，这也是算法名字的由来。

我们可以将经典的ADMM算法看作是ALM算法的Gauss-Seidel [6] 形式，而Douglas-Rachford分裂算法 [7] [8] 是ADMM的一种对偶形式，并且邻近点算法(PPA) [9] [10] 可以说明D-R算法。

2011年，Boyd [11] 等人重新回顾总结并证明ADMM算法适用于大规模优化问题后，使得这种方法逐渐进入了学者们的视野。随后，ADMM算法因为其良好的理论性质备受学者们的追捧，其收敛性与计算复杂性有丰富的研究成果 [12] [13] [14] [15]。此外，ADMM算法在压缩感知 [16]、图像处理 [17]、信号处理 [18] [19]、机器学习 [20] 等领域也取得了重大进展。由于其广泛的应用性，该算法近十来年已经有了很多改进和推广。

ADMM下降算法 [21] 是ADMM算法的一种改进，我们定义：

$v=\left(\begin{array}{c}y\\ \lambda \end{array}\right)\in \mathcal{Y}\times {\mathcal{R}}^r$，

算法的迭代步骤如下

$\{\begin{array}{l}{\tilde{x}}^k=\arg \min \left\{f\left(x\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(Ax+B{y}^k-b\right)+\frac{1}{2}\Vert {Ax+B{y}^k-b\Vert }_H^2|x\in \mathcal{X}\right\},\\ {\tilde{y}}^k=\arg \min \left\{g\left(y\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(A{\tilde{x}}^k+By-b\right)+\frac{1}{2}\Vert {A{\tilde{x}}^k+By-b\Vert }_H^2|y\in \mathcal{Y}\right\},\\ {\tilde{\lambda }}^k={\lambda }^k-H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right),\\ v^{k+1}=v^k-\gamma {\alpha }_k^{\ast }\left(v^k-{\tilde{v}}^k\right),{\alpha }_k^{\ast }=\frac{1}{2}+\frac{1}{2}\frac{\Vert {A{\tilde{x}}^k+B{y}^k-b\Vert }_H^2}{\Vert {v^k-{\tilde{v}}^k\Vert }_G^2},0<\gamma <2,\end{array}$

其中 ${\alpha }_k^{\ast }$ 为最优步长， $H\in {\mathcal{R}}^{r\times r}$ 是给定的对称正定阵， $\gamma$ 是延长因子(一般 $\gamma \in \left(1,2\right)$ 时会使收敛速度加快)。

并行分裂ADMM下降算法 [22] 的迭代步骤如下，定义：

$w=\left(\begin{array}{c}x\\ y\\ \lambda \end{array}\right)\in \mathcal{W}=\mathcal{X}\times \mathcal{Y}\times {\mathcal{R}}^r$

$\{\begin{array}{l}{\tilde{x}}^k=\arg \min \left\{f\left(x\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(Ax+B{y}^k-b\right)+\frac{1}{2}\Vert {Ax+B{y}^k-b\Vert }_H^2|x\in \mathcal{X}\right\},\\ {\tilde{y}}^k=\arg \min \left\{g\left(y\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(A{x}^k+By-b\right)+\frac{1}{2}\Vert {A{x}^k+By-b\Vert }_H^2|y\in \mathcal{Y}\right\},\\ {\tilde{\lambda }}^k={\lambda }^k-H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right),\\ w^{k+1}=w^k-\gamma {\alpha }_k^{\ast }{G}^{-1}M\left(w^k-{\tilde{w}}^k\right),{\alpha }_k^{\ast }=\frac{\phi \left(w^k,{\tilde{w}}^k\right)}{\Vert {G^{-1}M\left(w^k-{\tilde{w}}^k\right)\Vert }_G^2},1\le \gamma <2,\end{array}$

在ADMM下降算法中，要得到 ${\tilde{y}}^k$，都要用到上一步的结果 ${\tilde{x}}^k$，而并行分裂ADMM下降算法可以弥补这一不足， ${\tilde{y}}^k$ 的获得是独立不依赖于 ${\tilde{x}}^k$ 的， ${\tilde{x}}^k$ 和 ${\tilde{y}}^k$ 是并行分解的，这也是称之为并行分裂的原因。并行分裂ADMM下降算法在实际应用中可以大大地加快收敛的速度。

文献 [23] 考虑改善步长收缩算法 [24] [25] 的固定扩张步长没有充分利用下降量函数的不等式放缩，将算法中不变的延长因子改为使用随机数生成的延长因子，并称为随机步长收缩算法，这一改进方便选定步长且其取值更加丰富。

本文将上述并行分裂ADMM下降算法和随机步长收缩算法的思想相结合，提出了带随机步长的并行分裂ADMM下降算法，并在一定的假设条件下证明了算法的收敛性，且数值实验表明新算法是有效的。

2. 预备知识

下面简单回顾一些在随后的证明中要用到的一些基础知识。

引入拉格朗日乘子 $\lambda$，将式(1)转化为下列变分不等式，也就是寻找 $w=\left(x,y,\lambda \right)\in \mathcal{W}=\mathcal{X}\times \mathcal{Y}\times {\mathcal{R}}^r$，使得

(2)

再记 ${\mathcal{W}}^{\ast }$ 为上式的非空解集， $w^{\ast }=\left(x^{\ast },y^{\ast },{\lambda }^{\ast }\right)$ 是 ${\mathcal{W}}^{\ast }$ 中的一个解。

为了分析的便利，我们引入以下记号

$G=\left(\begin{array}{ccc}{A}^{\text{T}}HA& 0& 0\\ 0& B^{\text{T}}HB& 0\\ 0& 0& H^{-1}\end{array}\right),\bar{G}=\left(\begin{array}{ccc}0& 0& 0\\ -B^{\text{T}}HA& B^{\text{T}}HB& 0\\ 0& 0& H^{-1}\end{array}\right),F\left(w\right)=\left(\begin{array}{c}\nabla f\left(x\right)-A^{\text{T}}\lambda \\ \nabla g\left(y\right)-B^{\text{T}}\lambda \\ Ax+By-b\end{array}\right)$

定义2.1 [26] 设 $x=\left(x_1,x_2,\cdots ,x_n\right)\in {\mathcal{R}}^n$，对称正定阵 $G\in {\mathcal{R}}^{n\times n}$，则向量x在矩阵G意义下的范数定义为

${\Vert x\Vert }_G={\left(x^{\text{T}}Gx\right)}^{\frac{1}{2}}$

定义2.2 [27] 设 $X_1,X_2,\cdots ,X_n,\cdots$ 是一列随机变量，若 $\forall \epsilon >0$，恒有

$\underset{n\to \infty }{\lim }P\left\{\left|X_n-X\right|>\epsilon \right\}=0$

则称 $\left\{X_n\right\}$ 依概率收敛到X，记作 $X_n\stackrel{P}{\to }X$。

定理2.1 [27] 设 $X_n\stackrel{P}{\to }X$，则必有子序列 $X_{n_k}\to X$ a.s. (几乎必然地)。

定理2.2 [27] Markov不等式：对 $\forall \epsilon >0$ 、 $r>0$，有

$P\left(\left|x\right|>\epsilon \right)\le \frac{E\left({\left|x\right|}^r\right)}{{\epsilon }^r}$

定理2.3 [28] 设 $\mathcal{X}\subset {\mathcal{R}}^n$ 是闭凸集， $\theta \left(x\right)$ 和 $h\left(x\right)$ 为可微凸函数。设 $x^{\ast }$ 满足 $\min \left\{\theta \left(x\right)+h\left(x\right)|x\in \mathcal{X}\right\}$，即

$x^{\ast }=\arg \min \left\{\theta \left(x\right)+h\left(x\right)|x\in \mathcal{X}\right\}$

的充分必要条件是

$x^{\ast }\in \mathcal{X},{\left(x-x^{\ast }\right)}^{\text{T}}\left(\nabla \theta \left(x^{\ast }\right)+\nabla h\left(x^{\ast }\right)\right)\ge 0,\forall x\in \mathcal{X}$

定理2.4 [27] Jenson不等式：设X是一个随机变量，f是一个凸函数，则有

$f\left(E\left(X\right)\right)\le E(f(\; X\; ))$

如果f是一个凹函数，则有

$f\left(E\left(X\right)\right)\ge E\left(f(\; X\; )\right)$

3. 带随机步长的并行分裂ADMM下降算法及其收敛性

3.1. 带随机步长的并行分裂ADMM下降算法

步0初始化 $w=w^0=\left(x^0,y^0,z^0\right)$， $stopc=1$， $0\le a<b\le 2$， $k=0$，容许度 $\epsilon$ ；

步1当 $stopc\le \epsilon$ 时，停机；否则依次计算

${\tilde{x}}^k=\arg \min \left\{f\left(x\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(Ax+B{y}^k-b\right)+\frac{1}{2}\Vert {Ax+B{y}^k-b\Vert }_H^2|x\in \mathcal{X}\right\}$ (3)

${\tilde{y}}^k=\arg \min \left\{g\left(y\right)-{\left({\lambda }^k\right)}^{\text{T}}\left(A{x}^k+By-b\right)+\frac{1}{2}\Vert {A{x}^k+By-b\Vert }_H^2|y\in \mathcal{Y}\right\}$ (4)

${\tilde{\lambda }}^k={\lambda }^k-H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)$ (5)

步2计算

$w^{k+1}=w^k-{\gamma }^k{\alpha }_k^{\ast }\left(w^k-{\tilde{w}}^k\right)$ (6)

其中

${\gamma }^k=\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\xi }^i}$

${\alpha }_k^{\ast }=\frac{\phi \left(w^k,{\tilde{w}}^k\right)}{\Vert {w^k-{\tilde{w}}^k\Vert }_G^2}$ (7)

$\phi \left(w^k,{\tilde{w}}^k\right)=\Vert {w^k-{\tilde{w}}^k\Vert }_G^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left[\left(A{x}^k-A{\tilde{x}}^k\right)+\left(B{y}^k-B{\tilde{y}}^k\right)\right]$ (8)

步3计算

$stopc=\frac{\Vert w^{k+1}-w^k\Vert }{\Vert w^k\Vert },k=k+1$

返回步1。

注1 $\left\{{\xi }^k\right\}$ 为服从区间 $\left(a,b\right)$ 上的某种独立同分布的随机分布序列， ${\xi }^k$ 的数学期望 $E\left({\xi }^k\right)=\rho$ ；

注2 当 ${\xi }^k$ 取为固定值时，该算法退化为并行分裂的ADMM下降算法。

3.2. 收敛性

在该算法的收敛性分析中还需利用下述引理。

引理3.1 当 $F\left(w\right)$ 为单调连续算子时，由新算法依次计算得到的 ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 满足

${\left(\begin{array}{c}{x}^{\prime }-{\tilde{x}}^k\\ y^{\prime }-{\tilde{y}}^k\\ {\lambda }^{\prime }-{\tilde{\lambda }}^k\end{array}\right)}^{\text{T}}\left\{F\left({\tilde{w}}^k\right)+\left(\begin{array}{c}{A}^{\text{T}}HB\left(y^k-{\tilde{y}}^k\right)\\ B^{\text{T}}HB\left(y^k-{\tilde{y}}^k\right)\\ 0\end{array}\right)+\bar{G}\left({\tilde{w}}^k-w^k\right)\right\}\ge 0$ (9)

证明由(3)~(5)可得

${\left(x^{\prime }-{\tilde{x}}^k\right)}^{\text{T}}\left\{\nabla f\left({\tilde{x}}^k\right)-A^{\text{T}}\left[{\lambda }^k-H\left(A{\tilde{x}}^k+B{y}^k-b\right)\right]\right\}\ge 0,\forall x^{\prime }\in \mathcal{X}$ (10)

${\left(y^{\prime }-{\tilde{y}}^k\right)}^{\text{T}}\left\{\nabla g\left({\tilde{y}}^k\right)-B^{\text{T}}\left[{\lambda }^k-H\left(A{x}^k+B{\tilde{y}}^k-b\right)\right]\right\}\ge 0,\forall y^{\prime }\in \mathcal{Y}$ (11)

${\tilde{\lambda }}^k={\lambda }^k-H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)$

将上述式子简单整理写为向量格式，即可得到(9)。

引理3.2给定 $w^k=\left(x^k,y^k,{\lambda }^k\right)$， ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由(3)~(5)产生得到的， $\phi \left(w^k,{\tilde{w}}^k\right)$ 由(8)所定义，则有

$\phi \left(w^k,{\tilde{w}}^k\right)\ge \frac{2-\sqrt{2}}{2}{\Vert w^k-{\tilde{w}}^k\Vert }_G^2$ (12)

证明首先，根据矩阵G和 $\phi \left(w^k,{\tilde{w}}^k\right)$ 的定义，

$\begin{array}{l}\phi \left(w^k,{\tilde{w}}^k\right)={\Vert A\left(x^k-{\tilde{x}}^k\right)\Vert }_H^2+{\Vert B\left(y^k-{\tilde{y}}^k\right)\Vert }_H^2+{\Vert {\lambda }^k-{\tilde{\lambda }}^k\Vert }_{H^{-1}}^2\\ +{\left(A{x}^k-A{\tilde{x}}^k\right)}^{\text{T}}\left({\lambda }^k-{\tilde{\lambda }}^k\right)+{\left(B{y}^k-B{\tilde{y}}^k\right)}^{\text{T}}\left({\lambda }^k-{\tilde{\lambda }}^k\right)\end{array}$ (13)

根据Cauchy-Schwarz不等式，得

${\left(A{x}^k-A{\tilde{x}}^k\right)}^{\text{T}}\left({\lambda }^k-{\tilde{\lambda }}^k\right)\ge -\frac{1}{2}\left(\sqrt{2}{\Vert A\left(x^k-{\tilde{x}}^k\right)\Vert }_H^2+\frac{1}{\sqrt{2}}{\Vert {\lambda }^k-{\tilde{\lambda }}^k\Vert }_{H^{-1}}^2\right)$ (14)

${\left(B{y}^k-B{\tilde{y}}^k\right)}^{\text{T}}\left({\lambda }^k-{\tilde{\lambda }}^k\right)\ge -\frac{1}{2}\left(\sqrt{2}{\Vert B\left(y^k-{\tilde{y}}^k\right)\Vert }_H^2+\frac{1}{\sqrt{2}}{\Vert {\lambda }^k-{\tilde{\lambda }}^k\Vert }_{H^{-1}}^2\right)$ (15)

把(14) (15)带入到(13)中，得

$\phi \left(w^k,{\tilde{w}}^k\right)\ge \frac{2-\sqrt{2}}{2}\left({\Vert A\left(x^k-{\tilde{x}}^k\right)\Vert }_H^2+{\Vert B\left(y^k-{\tilde{y}}^k\right)\Vert }_H^2+{\Vert {\lambda }^k-{\tilde{\lambda }}^k\Vert }_{H^{-1}}^2\right)$

从而直接得到引理中3.2中的结果。

引理3.3给定 $w^k=\left(x^k,y^k,{\lambda }^k\right)$， ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由(3)~(5)产生得到的，则对任意的 $w^{\ast }\in {\mathcal{W}}^{\ast }$，有

${\left({\tilde{\lambda }}^k-{\lambda }^{\ast }\right)}^{\text{T}}{H}^{-1}\left({\lambda }^k-{\tilde{\lambda }}^k\right)\ge {\left(A{\tilde{x}}^k-A{x}^{\ast }\right)}^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)+{\left(B{\tilde{y}}^k-B{y}^{\ast }\right)}^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)$ (16)

证明因为 $w^{\ast }\in {\mathcal{W}}^{\ast }$， ${\tilde{x}}^k\in \mathcal{X}$， ${\tilde{y}}^k\in \mathcal{Y}$，由(8)可得

${\left(\begin{array}{c}{\tilde{x}}^k-x^{\ast }\\ {\tilde{y}}^k-y^{\ast }\end{array}\right)}^{\text{T}}\left(\begin{array}{c}\nabla f\left(x^{\ast }\right)-A^{\text{T}}{\lambda }^{\ast }\\ \nabla g\left(y^{\ast }\right)-B^{\text{T}}{\lambda }^{\ast }\end{array}\right)\ge 0$ (17)

$A{x}^{\ast }+B{y}^{\ast }-b=0$

另一方面，因为 $x^{\ast }\in \mathcal{X}$， $y^{\ast }\in \mathcal{Y}$，从(10) (11)可得到

${\left(\begin{array}{c}{x}^{\ast }-{\tilde{x}}^k\\ y^{\ast }-{\tilde{y}}^k\end{array}\right)}^{\text{T}}\left(\begin{array}{c}\nabla f\left({\tilde{x}}^k\right)-A^{\text{T}}{\tilde{\lambda }}^k+A^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)\\ \nabla g\left({\tilde{y}}^k\right)-B^{\text{T}}{\tilde{\lambda }}^k+B^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)\end{array}\right)\ge 0$ (18)

把(17)和(18)相加，并利用 $\nabla f$ 和 $\nabla g$ 的单调性，得

${\left(\begin{array}{c}{\tilde{x}}^k-x^{\ast }\\ {\tilde{y}}^k-y^{\ast }\end{array}\right)}^{\text{T}}\left(\begin{array}{c}{A}^{\text{T}}\left({\tilde{\lambda }}^k-{\lambda }^{\ast }\right)-A^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)\\ B^{\text{T}}\left({\tilde{\lambda }}^k-{\lambda }^{\ast }\right)-B^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)\end{array}\right)\ge 0$

整理得到

$\begin{array}{l}{\left({\tilde{\lambda }}^k-{\lambda }^{\ast }\right)}^{\text{T}}\left[\left(A{\tilde{x}}^k-A{x}^{\ast }\right)+\left(B{\tilde{y}}^k-B{y}^{\ast }\right)\right]\\ \ge {\left(A{\tilde{x}}^k-A{x}^{\ast }\right)}^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)+{\left(B{\tilde{y}}^k-B{y}^{\ast }\right)}^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)\end{array}$ (19)

由于 $A{x}^{\ast }+B{y}^{\ast }-b=0$ 且 $A{\tilde{x}}^k+B{\tilde{y}}^k-b=H^{-1}\left({\lambda }^k-{\tilde{\lambda }}^k\right)$，从(19)我们直接得到(16)。

引理3.4给定 $w^k=\left(x^k,y^k,{\lambda }^k\right)$， ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由(3)~(5)产生得到的，则对任意的 $w^{\ast }\in {\mathcal{W}}^{\ast }$，有

${\left(w^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)\ge \phi \left(w^k,{\tilde{w}}^k\right)$ (20)

证明首先，使用矩阵G的定义，有

$\begin{array}{l}{\left({\tilde{w}}^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)\\ ={\left(A{\tilde{x}}^k-A{x}^{\ast }\right)}^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)+{\left(B{\tilde{y}}^k-B{y}^{\ast }\right)}^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)\\ +{\left({\tilde{\lambda }}^k-{\lambda }^{\ast }\right)}^{\text{T}}{H}^{-1}\left({\lambda }^k-{\tilde{\lambda }}^k\right)\end{array}$ (21)

将(16)代入(21)右边的最后一项得到

$\begin{array}{l}{\left({\tilde{w}}^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)\\ \ge {\left(A{\tilde{x}}^k-A{x}^{\ast }\right)}^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)+{\left(B{\tilde{y}}^k-B{y}^{\ast }\right)}^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)\\ +{\left(B{\tilde{y}}^k-B{y}^{\ast }\right)}^{\text{T}}H\left(A{x}^k-A{\tilde{x}}^k\right)+{\left(A{\tilde{x}}^k-A{x}^{\ast }\right)}^{\text{T}}H\left(B{y}^k-B{\tilde{y}}^k\right)\end{array}$

利用 $A{x}^{\ast }+B{y}^{\ast }=b$，从上面的不等式我们得到

${\left({\tilde{w}}^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)\ge {\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)}^{\text{T}}H\left[\left(A{x}^k-A{\tilde{x}}^k\right)+\left(B{y}^k-B{\tilde{y}}^k\right)\right]$ (22)

因为 $H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)={\lambda }^k-{\tilde{\lambda }}^k$，再由 $\phi \left(w^k,{\tilde{w}}^k\right)$ 的定义，我们可以直接得到(20)。

引理3.5给定 $w^k=\left(x^k,y^k,{\lambda }^k\right)$， ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由(3)~(5)产生得到的，定义

$w^{k+1}\left(\alpha \right)=w^k-\alpha \left(w^k-{\tilde{w}}^k\right)$ (23)

${\theta }_k\left(\alpha \right)={\Vert w^k-w^{\ast }\Vert }_G^2-{\Vert w^{k+1}\left(\alpha \right)-w^{\ast }\Vert }_G^2,\forall w^{\ast }\in {\mathcal{W}}^{\ast }$ (24)

则有

${\theta }_k\left(\alpha \right)\ge q_k\left(\alpha \right)=2\alpha \phi \left(w^k,{\tilde{w}}^k\right)-{\alpha }^2{\Vert w^k-{\tilde{w}}^k\Vert }_G^2,\forall \alpha >0$ (25)

证明由(23) (24)和(20)可知

$\begin{array}{c}{\theta }_k\left(\alpha \right)={\Vert w^k-w^{\ast }\Vert }_G^2-{\Vert w^k-\alpha \left(w^k-{\tilde{w}}^k\right)-w^{\ast }\Vert }_G^2\\ =2\alpha {\left(w^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)-{\alpha }^2{\Vert w^k-{\tilde{w}}^k\Vert }_G^2\\ \ge 2\alpha \phi \left(w^k,{\tilde{w}}^k\right)-{\alpha }^2{\Vert w^k-{\tilde{w}}^k\Vert }_G^2\end{array}$ (26)

(26)的右侧是 $q_k\left(\alpha \right)$，得证。

注1 引理3.5中 ${\theta }_k\left(\alpha \right)$ 是迭代点和最优点距离的下降量，因其含有未知量 $w^{\ast }$，从而无法计算； $q_k\left(\alpha \right)$ 是 ${\theta }_k\left(\alpha \right)$ 的一个下界函数，此函数不含未知量 $w^{\ast }$，相对易于计算。

注2 注意到 $q_k\left(\alpha \right)$ 是关于 $\alpha$ 的二次函数，最大值在 ${\alpha }_k^{\ast }=\frac{\phi \left(w^k,{\tilde{w}}^k\right)}{{\Vert w^k-{\tilde{w}}^k\Vert }_G^2}$ 处取得，且 $q_k\left({\alpha }_k^{\ast }\right)={\alpha }_k^{\ast }\phi \left(w^k,{\tilde{w}}^k\right)$。

定理3.1当 $0\le a<E\left({\gamma }^k\right)=\rho <b\le 2$ 时，由(3)~(6)产生的迭代序列 $\left\{w^k\right\}$ 收敛，并且存在 $T_0\left(0<T_0<\infty \right)$ 使得对任意的 $w^{\ast }\in {\mathcal{W}}^{\ast }$， $k\to \infty$ 有

$E\left({\Vert w^{k+1}-w^{\ast }\Vert }_G^2\right)\le E\left({\Vert w^k-w^{\ast }\Vert }_G^2\right)-T_0\cdot E\left({\Vert w^{k+1}-w^k\Vert }_G^2\right)$ (27)

其中 $T_0=\left(2-\sqrt{2}\right)\left(\frac{2}{\rho }-1\right)$。

证明由于G是对称正定阵，根据(5)和 $0\le a<E\left({\gamma }^k\right)=\rho <b\le 2$，得

${\Vert w^{k+1}-w^{\ast }\Vert }_G^2={\Vert w^k-{\gamma }^k{\alpha }_k^{\ast }\left(w^k-{\tilde{w}}^k\right)-w^{\ast }\Vert }_G^2$

$={\Vert w^k-w^{\ast }\Vert }_G^2-2{\gamma }^k{\alpha }_k^{\ast }{\left(w^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)+{\left({\gamma }^k{\alpha }_k^{\ast }\right)}^2{\Vert w^k-{\tilde{w}}^k\Vert }_G^2$

$\le {\Vert w^k-w^{\ast }\Vert }_G^2-2{\gamma }^k{\alpha }_k^{\ast }\phi \left(w^k,{\tilde{w}}^k\right)+{\left({\gamma }^k{\alpha }_k^{\ast }\right)}^2{\Vert w^k-{\tilde{w}}^k\Vert }_G^2$ (28)

$={\Vert w^k-w^{\ast }\Vert }_G^2-\left[2{\gamma }^k{\alpha }_k^{\ast }\phi \left(w^k,{\tilde{w}}^k\right)+\left({\left({\gamma }^k\right)}^2{\alpha }_k^{\ast }\right){\alpha }_k^{\ast }{\Vert w^k-{\tilde{w}}^k\Vert }_G^2\right]$

$={\Vert w^k-w^{\ast }\Vert }_G^2-{\gamma }^k\left(2-{\gamma }^k\right){\alpha }_k^{\ast }\phi \left(w^k,{\tilde{w}}^k\right)$ (29)

$\le {\Vert w^k-w^{\ast }\Vert }_G^2-\frac{1}{2}{\gamma }^k\left(2-{\gamma }^k\right)\phi \left(w^k,{\tilde{w}}^k\right)$ (30)

$\le {\Vert w^k-w^{\ast }\Vert }_G^2-\frac{2-\sqrt{2}}{4}{\gamma }^k\left(2-{\gamma }^k\right){\Vert w^k-{\tilde{w}}^k\Vert }_G^2$ (31)

其中(28)由(20)可得，即 $2{\gamma }^k{\alpha }_k^{\ast }{\left(w^k-w^{\ast }\right)}^{\text{T}}G\left(w^k-{\tilde{w}}^k\right)\ge 2{\gamma }^k{\alpha }_k^{\ast }\phi \left(w^k,{\tilde{w}}^k\right)$ ；(29)由 ${\alpha }_k^{\ast }=\frac{\phi \left(w^k,{\tilde{w}}^k\right)}{{\Vert w^k-{\tilde{w}}^k\Vert }_G^2}$ 可得；(30)由 ${\alpha }_k^{\ast }\ge 0.5$ 可得；(31)由(12)可得。

根据(5)和 ${\alpha }_k^{\ast }\ge 0.5$，可得

$w^{k+1}-w^k=-{\gamma }^k{\alpha }_k^{\ast }\left(w^k-{\tilde{w}}^k\right)\le -\frac{1}{2}{\gamma }^k\left(w^k-{\tilde{w}}^k\right)=\frac{1}{2}{\gamma }^k\left({\tilde{w}}^k-w^k\right)$

即 $\frac{4}{{\left({\gamma }^k\right)}^2}{\Vert w^{k+1}-w^k\Vert }_G^2\le {\Vert w^k-{\tilde{w}}^k\Vert }_G^2$。

故

${\Vert w^{k+1}-w^{\ast }\Vert }_G^2\le {\Vert w^k-w^{\ast }\Vert }_G^2-\left(2-\sqrt{2}\right)\left(\frac{2}{{\gamma }^k}-1\right){\Vert w^{k+1}-w^k\Vert }_G^2$ (32)

由(32)可知，因 ${\xi }^1,{\xi }^2,\cdots ,{\xi }^k,\cdots$ 独立同分布，且 $E\left({\gamma }^k\right)=E\left(\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\xi }^i}\right)=\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}E\left({\xi }^i\right)}=\rho$，所以

$E\left({\Vert w^{k+1}-w^{\ast }\Vert }_G^2\right)\le E\left({\Vert w^k-w^{\ast }\Vert }_G^2-\left(2-\sqrt{2}\right)\left(\frac{2}{{\gamma }^k}-1\right){\Vert w^{k+1}-w^k\Vert }_G^2\right)$

$=E\left({\Vert w^k-w^{\ast }\Vert }_G^2\right)-E\left(\left(2-\sqrt{2}\right)\left(\frac{2}{{\gamma }^k}-1\right){\Vert w^{k+1}-w^k\Vert }_G^2\right)$

$\le E\left({\Vert w^k-w^{\ast }\Vert }_G^2\right)-\left(2-\sqrt{2}\right)\left(\frac{2}{E\left({\gamma }^k\right)}-1\right)E\left({\Vert w^{k+1}-w^k\Vert }_G^2\right)$ (33)

$=E\left({\Vert w^k-w^{\ast }\Vert }_G^2\right)-\left(2-\sqrt{2}\right)\left(\frac{2}{\rho }-1\right)E\left({\Vert w^{k+1}-w^k\Vert }_G^2\right)$

其中(33)是由Jenson不等式得到的， $\frac{2}{{\gamma }^k}-1$ 是一个凸函数，故 $E\left(\frac{2}{{\gamma }^k}-1\right)\ge \frac{2}{E\left({\gamma }^k\right)}-1$ ；再令 $T_0=\left(2-\sqrt{2}\right)\left(\frac{2}{\rho }-1\right)$。即(28)得证。

推论3.1当 $0\le a<E\left({\gamma }^k\right)=\rho <b\le 2$ 时， $\left\{w^k\right\}$ 为新算法产生的序列，则有

1) 序列 $\left\{E\left(w^k\right)\right\}$ 和 $\left\{E\left({\tilde{w}}^k\right)\right\}$ 是有界的；

2) 序列 $\left\{E\left({\Vert w^k-w^{\ast }\Vert }_G^2\right)\right\}$ 是严格单调递减且有界的；

3) $\underset{k\to \infty }{\lim }E\left({\Vert w^k-{\tilde{w}}^k\Vert }_G\right)=0$。

下面给出新算法的依概率收敛的证明。

定理3.2由新算法产生的序列 $\left\{w^k\right\}$ 依概率收敛于 $w^{\infty }\in {\mathcal{W}}^{*}$，即 $w^k\stackrel{P}{\to }{w}^{\infty }$。

证明根据上面推论3.1中的2)，有

$\underset{k\to \infty }{\lim }E\left({\Vert A\left(x^k-{\tilde{x}}^k\right)\Vert }_H\right)=0,\underset{k\to \infty }{\lim }E\left({\Vert B\left(y^k-{\tilde{y}}^k\right)\Vert }_H\right)=0$ (34)

$\underset{k\to \infty }{\lim }E\left({\Vert {\lambda }^k-{\tilde{\lambda }}^k\Vert }_{H^{-1}}\right)=\underset{k\to \infty }{\lim }E\left({\Vert A{\tilde{x}}^k+B{\tilde{y}}^k-b\Vert }_H\right)=0$ (35)

对于，由(10) (11)和(6)得：

$\begin{array}{l}{\left(x^{\prime }-{\tilde{x}}^k\right)}^{\text{T}}\left\{\nabla f\left({\tilde{x}}^k\right)-A^{\text{T}}\left[{\tilde{\lambda }}^k+H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)\right]+A^{\text{T}}H\left(A{\tilde{x}}^k+B{y}^k-b\right)\right\}\ge 0\\ {\left(y^{\prime }-{\tilde{y}}^k\right)}^{\text{T}}\left\{\nabla g\left({\tilde{y}}^k\right)-B^{\text{T}}\left[{\tilde{\lambda }}^k+H\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)\right]+B^{\text{T}}H\left(A{x}^k+B{\tilde{y}}^k-b\right)\right\}\ge 0\end{array}$

即：

${\left(x^{\prime }-{\tilde{x}}^k\right)}^{\text{T}}\left(\nabla f\left({\tilde{x}}^k\right)-A^T{\tilde{\lambda }}^k\right)\ge A^{\text{T}}HB\left({\tilde{y}}^k-y^k\right)$ (36)

${\left(y^{\prime }-{\tilde{y}}^k\right)}^{\text{T}}\left(\nabla g\left({\tilde{y}}^k\right)-B^{\text{T}}{\tilde{\lambda }}^k\right)\ge B^{\text{T}}HA\left({\tilde{x}}^k-x^k\right)$ (37)

由(34)和(36) (37)得

$\{\begin{array}{l}\underset{k\to \infty }{\lim }{\left(x^{\prime }-{\tilde{x}}^k\right)}^{\text{T}}\left(\nabla f\left({\tilde{x}}^k\right)-A^{\text{T}}{\tilde{\lambda }}^k\right)\ge 0\\ \underset{k\to \infty }{\lim }{\left(y^{\prime }-{\tilde{y}}^k\right)}^{\text{T}}\left(\nabla g\left({\tilde{y}}^k\right)-B^{\text{T}}{\tilde{\lambda }}^k\right)\ge 0\end{array}$ (38)

由于 $\left\{E\left({\tilde{w}}^k\right)\right\}$ 有界，故该序列至少存在一个聚点，设 $E\left(w^{\infty }\right)$ 是 $\left\{E\left(w^k\right)\right\}$ 的一个聚点，且存在子序列 $\left\{E\left(w^{k_j}\right)\right\}$ 收敛于 $E\left(w^{\infty }\right)$，那么子序列 $\left\{w^{k_j}\right\}$ 依概率收敛到 $w^{\infty }$，即 $w^{k_j}\stackrel{P}{\to }{w}^{\infty }$。

再由(35)和(38)可得

$\{\begin{array}{l}\underset{j\to \infty }{\lim }{\left(x^{\prime }-{\tilde{x}}^{k_j}\right)}^{\text{T}}\left(\nabla f\left({\tilde{x}}^{k_j}\right)-A^{\text{T}}{\tilde{\lambda }}^{k_j}\right)\ge 0\\ \underset{j\to \infty }{\lim }{\left(y^{\prime }-{\tilde{y}}^{k_j}\right)}^{\text{T}}\left(\nabla g\left({\tilde{y}}^{k_j}\right)-B^{\text{T}}{\tilde{\lambda }}^{k_j}\right)\ge 0\\ \underset{j\to \infty }{\lim }\left(A{\tilde{x}}^{k_j}+B{\tilde{y}}^{k_j}-b\right)=0\end{array}$

即

$\{\begin{array}{l}{\left(x^{\prime }-x^{\infty }\right)}^{\text{T}}\left(\nabla f\left(x^{\infty }\right)-A^{\text{T}}{\lambda }^{\infty }\right)\ge 0\\ {\left(y^{\prime }-y^{\infty }\right)}^{\text{T}}\left(\nabla g\left(y^{\infty }\right)-B^{\text{T}}{\lambda }^{\infty }\right)\ge 0\\ \left(A{x}^{\infty }+B{y}^{\infty }-b\right)=0\end{array}$

因此， $w^{\infty }\in {\mathcal{W}}^{*}$。

由 $\underset{j\to \infty }{\lim }E\left({\tilde{w}}^{k_j}\right)=E\left(w^{\infty }\right)$ 可知， $\underset{l\to \infty }{\lim }E\left({\Vert {\tilde{w}}^{k_l}-w^{\infty }\Vert }_G\right)=0$。

又因为 $\underset{k\to \infty }{\lim }E\left({\Vert w^k-{\tilde{w}}^k\Vert }_G\right)=0$，则对任意 $\epsilon >0$，存在 $l\in {\mathbb{Z}}^{+}$ 使得

$E\left(\Vert w^{k_l}-{\tilde{w}}^{k_l}\Vert \right)<\frac{{\epsilon }^2}{2}$， $E\left(\Vert {\tilde{w}}^{k_l}-w^{\infty }\Vert \right)<\frac{{\epsilon }^2}{2}$

根据推论， $\left\{E\left({\Vert w^k-w^{*}\Vert }_G^2\right)\right\}$ 是严格单调递减的。因此，对任意 $k\ge k_l$，有

$E\left({\Vert w^k-w^{\infty }\Vert }_G\right)\le E\left({\Vert w^{k_l}-w^{\infty }\Vert }_G\right)\le E\left({\Vert w^{k_l}-{\tilde{w}}^{k_l}\Vert }_G\right)+E\left({\Vert {\tilde{w}}^{k_l}-w^{\infty }\Vert }_G\right)<{\epsilon }^2$ (39)

即 $\underset{k\to \infty }{\lim }E\left({\Vert w^k-w^{\infty }\Vert }_G\right)=0$。

由定理2.2和(39)可知，对任意 $\epsilon >0$，存在 $l>0$，只要 $k>l$，就有

$P\left({\Vert w^k-w^{\infty }\Vert }_G\ge \epsilon \right)\le \frac{E\left({\Vert w^k-w^{\infty }\Vert }_G\right)}{\epsilon }<\epsilon$

即 $\underset{k\to \infty }{\lim }P\left({\Vert w^k-w^{\infty }\Vert }_G\ge \epsilon \right)=0$。

故 $\left\{w^k\right\}$ 依概率收敛到 $w^{\infty }\in {\mathcal{W}}^{*}$，即 $w^k\stackrel{P}{\to }{w}^{\infty }$。

4. 数值实验

我们考虑求解下列等式约束二次规划问题

$\begin{array}{l}\underset{x,y}{\min }\frac{1}{2}{x}^{\text{T}}Px+p^{\text{T}}x+\frac{1}{2}{y}^{\text{T}}Qy+q^{\text{T}}y\\ \text{s}\text{.t}\text{.}Ax+By=b\end{array}$

其中P和Q是对称正定阵， $A\in {\mathcal{R}}^{m\times n_1}$， $B\in {\mathcal{R}}^{m\times n_2}$， $x\in {\mathcal{R}}^{n_1}$， $y\in {\mathcal{R}}^{n_2}$， $b\in {\mathcal{R}}^m$， $p\in {\mathcal{R}}^{n_1}$， $q\in {\mathcal{R}}^{n_2}$。

我们令 $H=\beta I$，其中的最优取值是通过反复测试确定的。同时， ${\gamma }^k$ 是在区间 $\left(0,2\right)$ 上选取的服从正态分布的随机数。在新算法运行前，我们对矩阵 $P,Q,A^{\text{T}}A,B^{\text{T}}B$ 进行Cholesky分解，来化简对子问题的求解。我们取

$stopc={\Vert \left({\tilde{x}}^k-x^k,{\tilde{y}}^y-y^y,A{\tilde{x}}^k+B{\tilde{y}}^y-b\right)\Vert }_{\infty }\le {10}^{-12}$

作为停机准则。

我们在每组 $\left(m,n_1,n_2\right)$ 设置下，测试了几组不同设置的问题。然后将几种算法数值实验的结果进行比较，见表1。

Table 1. Numerical experimental results of four algorithms

表1. 四种算法的数值实验结果

5. 结语

本文基于并行分裂ADMM下降算法和改善步长的收缩算法，提出了一种求解结构型凸优化问题的新算法——带随机步长的并行分裂ADMM下降算法，文章证明了新算法的收敛性。数值实验结果显示，在求解结构型凸优化问题时，新算法的迭代步数及CPU运行时间均优于文章中的其他4类算法，并且新算法的计算效率对数据维度的增长有较好的鲁棒性，进一步说明新算法可用于处理一些高维数据的问题。

本文在ADMM算法基础上进行算法改进的研究，并取得了一些新的成果，但还有许多问题值得我们更深一步的研究。在随后的研究中，我们主要考虑以下几个方面：

1) 本文考虑的目标函数是带有两块的结构型凸优化问题，后面还可以考虑新算法能否推广到带有三块及多块的结构型凸优化问题的情况；

2) 能否加入Nesterov加速等其他加速算法，使算法的计算效率进一步提高；

3) 以后还可测试一些实际问题，比如图像降噪、信号处理等问题。

NOTES

^*第一作者Email: [e-mail]

^#通讯作者Email: [e-mail]