基于广义近似交替方向乘子法求解可分离凸优化问题

Solving Separable Convex Optimization Problem Based on Generalized Proximal Alternating Direction Method of Multipliers

摘要: 本文提出了一种广义近似交替方向乘子法(gPADMM)来求解可分离凸优化问题。和近似邻近点算法(APPA)和扩展邻近交替方向方法(ePADM)相比，新算法不仅更新自定义矩阵的结构，而且引入随机变量进行随机加速更新步长，从而克服了旧算法固定步长的不灵活性。在某些适当的假设条件下，本文证明了新算法的全局收敛性，并且初步数值实验表明该算法是有效的，收敛速度比旧算法更快。

Abstract: In this paper, we propose a generalized-proximal alternating direction method of multipliers (gPADMM) for separable convex optimization problem. Compared with the approximate proximal point algorithm (APPA) and the extend proximal alternating directions method (ePADM), the new algorithm not only updates the structure of customed matrix, but also induces random variables for random acceleration to update the step length, which overcomes the inflexibility of the old al-gorithms' fixed step length. We prove the global convergence of the new algorithm under certain mild conditions. And preliminary numerical experiments show that the algorithm is effective and the gPADMM converges faster than the old algorithms.

1. 引言

本文考虑一个具有如下形式的可分离凸优化问题

$\min \left\{f\left(x\right)+g\left(y\right)|Ax+By=b,x\in X,y\in Y\right\},$ (1.1)

其中 $X\subset R^{n_1},Y\subset R^{n_2}$ 是有界闭合的、凸的、非空集合， $f:X\to R$ 和 $g:Y\to R$ 是凸函数(不一定是平滑函数)。 $A\in R^{m\times n_1},B\in R^{m\times n_2}$ 是给定的矩阵， $b\in R^m$ 是一个向量。

Glowinski [1] 和Gabay [2] 证明了基于增广拉格朗日方法(ALM)的交替方向乘子方法对于问题(1.1)是非常有效的。针对问题(1.1)，ALM算法的迭代形式为

$\{\begin{array}{l}{x}^{k+1}=\underset{x\in X}{\arg \min }\left\{f\left(x\right)+\frac{\beta }{2}{\Vert Ax+B{y}^k-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\right\},\\ y^{k+1}=\underset{x\in X}{\arg \min }\left\{g\left(y\right)+\frac{\beta }{2}{\Vert A{x}^{k+1}+By-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\right\},\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+B{y}^{k+1}-b\right).\end{array}$ (1.2)

Gabay [3] 表明ADMM算法在本质上是Douglas-Rachford分裂方法的一种应用 [4]。Cai，Gu和He在文献 [5] 中提供了一种新颖简单的邻近点算法(PPA)来解释ADMM算法，并提出了一种广义的ADMM算法(gADMM)，即它首先产生了一个预测算子，形式如下：

$\{\begin{array}{l}{\tilde{x}}^k=\underset{x\in X}{\arg \min }\left\{f\left(x\right)+\frac{\beta }{2}{\Vert Ax+B{y}^k-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\right\},\\ {\tilde{\lambda }}^k={\lambda }^k-\beta \left(A{\tilde{x}}^k+B{y}^k-b\right),\\ {\tilde{y}}^k=\underset{y\in Y}{\arg \min }\left\{g\left(y\right)+\frac{\beta }{2}{\Vert A{\tilde{x}}^k+By-b-\frac{1}{\beta }{\tilde{\lambda }}^k\Vert }^2\right\},\\ x^{k+1}={\tilde{x}}^k,\\ y^{k+1}=y^k-\gamma \left(y^k-{\tilde{y}}^k\right),\\ {\lambda }^{k+1}={\lambda }^k-\gamma \left({\lambda }^k-{\tilde{\lambda }}^k\right),\gamma \in \left(0,2\right).\end{array}$ (1.3)

其中新的迭代步表示为 $w^{k+1}=\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)$。自定义矩阵表示为：

$Q=\left(\begin{array}{ccc}{0}_{n_1\times n_1}& 0_{n_1\times n_2}& 0_{n_1\times m}\\ 0_{n_2\times n_1}& \beta B^{\text{T}}B& -B^{\text{T}}\\ 0_{m\times n_1}& -B& -\frac{1}{\beta }{I}_m\end{array}\right)$

通过以上分析，可以发现针对问题(1.1)，ADMM算法有许多变体。进一步研究得到，文献 [6] 中提出了DRSM算法并在 [7] 中被进一步解释为邻近点算法的应用。Jiang, B. Q.，Peng, Z.，Deng, K. K.提出了两种新颖的定制邻近点算法，在 [8] 中将建立所提出方法的全局收敛性和O (1/k)收敛速率。因此，在 [6] 中建议对PPA应用 [9] 中提出的加速方案来加速原始ADMM。最近， [10] 中的工作表明了开发下降型方法求解的可能性，其下降方向是从ADM生成的迭代中得出的。在 [11] 中，李、袁等人考虑将广义交替方向乘子法与对数-二次近端正则化相结合，以解决具有可分离结构的变分不等式问题(VI)，并建立由在遍历和非遍历意义上的迭代复杂度。袁晓明提出了一种改进的基于PADM的下降方法，该方法继承了 [12] 中ADM，PPA和下降类型方法的所有优点。在 [13] 中，徐使用服从高斯分布的随机数来随机扩展步长，并针对一类变分不等式提出了随机步长收缩方法。但是，在某些实际应用中，宽松的步骤可能是不可接受的，甚至是不被允许的。

为了应对这些实际情况，本文修改了预测步长，并采用随机变量来更新步长，而不是放松固定步长。然后，提出了广义的邻近交替方乘子向法。在一些适当的假设下，本文证明了算法的收敛性。同时，本文通过数值实验，还验证了与以前提出的某些算法相比，新算法在实践中具有更好的数值性能。

本文的其余部分安排如下。本文的第2节描述了一些相关的基础知识和引理，以便后续证明。在第3节中，本文针对问题(1.1)提出了广义近邻交替方向乘子方法。所提方法的收敛性将在第4节中得到证明。在第5节中，与以前提出的算法相比，一些初步的数值结果被提出来表明新方法的高效率。第六部分总结了本文的一些结论。

2. 预备知识

本节给出了将在后续当中使用的一些预备知识。贯穿全文，本文将 $\Vert u\Vert =\sqrt{u^{\text{T}}u}$ 表示为Educlidean范数，而 $\langle \cdot ,\cdot \rangle$ 表示为内积。令 $\Omega \in R^m\times R^n\times R^r$ 是R上的一个非空闭合子集。当 $P_{\Omega }$ 的可行集Ω是非负正数 $R_{+}^N$ 时，向量 $x\in R$ 的每个分量i的投影很简单，表示为 ${\left(P_{\Omega }\left[x\right]\right)}_i=\max \left\{0,x_i\right\}$。

引理2.1 令 $\zeta >0$ 为常数，C为非空封闭的凸集。当且仅当

$x^{\ast }=P_C\left[x^{\ast }-\zeta f\left(x^{\ast }\right)\right],x^{*}\in C$

是 $\text{VI}\left(f,C\right)$ 的最优解。

记 $e\left(x,\zeta \right)=x-P_C\left[x-\zeta f\left(x\right)\right]$ 为投影方程的残差，则 $\text{VI}\left(f,C\right)$ 等价于找到 $e\left(x,\zeta \right)$ 的零点。因此，我们可以将 $\Vert \left(x,\zeta \right)\Vert$ 记为算法的停止准则。下一个引理表明，对于任何 $\zeta >0$， $\Vert \left(x,\zeta \right)\Vert$ 是一个非递减函数。

众所周知，对于任何x和y，正交投影算子 $P_{\Omega }$ 具有以下特性：

引理2.2 [14] 令 $\Omega \in R^m\times R^n\times R^r$ 是一个非空闭合凸集，那么对于任意的 $x,y\in R^n$，都有

(1) $\langle x-P_{\Omega }\left(x\right),P_{\Omega }\left(x\right)-y\rangle \ge 0,\forall y\in \Omega$

(2) $\langle P_{\Omega }\left(x\right)-P_{\Omega }\left(y\right),x-y\rangle \ge 0,\forall x,y\in R^m\times R^n\times R^r$

(3) $\Vert P_{\Omega }\left(x\right)-P_{\Omega }\left(y\right)\Vert \le \Vert x-y\Vert ,\forall x,y\in R^m\times R^n\times R^r$

(4) $\langle x-y,P_{\Omega }\left(x\right)-P_{\Omega }\left(y\right)\rangle \ge {\Vert P_{\Omega }\left(x\right)-P_{\Omega }\left(y\right)\Vert }^2,\forall x,y\in R^m\times R^n\times R^r$

在许多情况下，可行集C具有以下形式： $C=\left\{x|Ax+By=b,x\in Q\right\}$，其中 $A,B\in R^{m\times n},b\in R^m$，而Q是 $R_{+}^N$ 的简单凸子集。基本的 $\text{VI}\left(f,C\right)$ 可以转换为结构化的变分不等式问题，表示为 $\text{VI}\left(F,C\right)$ ：寻找一个 $u^{\ast }\in Q$，使得

$F{\left(u^{\ast }\right)}^{\text{T}}\left(u-u^{\ast }\right)\ge 0,\forall u\in Q,$

其中 $u:=\left(\begin{array}{c}x\\ y\end{array}\right)$， $w:=\left(\begin{array}{c}x\\ y\\ \lambda \end{array}\right)$， $F\left(w\right):=\left(\begin{array}{c}-A^{\text{T}}\lambda \\ -B^{\text{T}}\lambda \\ Ax+By-b\end{array}\right)$。

关于目标函数f的以下定义是非常重要的，并且会在后面证明会使用到。

定义2.3 设f为从 $C\to R^n$ 的映射。如果 ${\left(u-v\right)}^{\text{T}}\left(f\left(u\right)-f\left(v\right)\right)\ge 0,\forall u,v\in C$，那么f在C上是单调的。

如果C是 $R^n$ 的紧凸集，而 $F:C\to R^n$ 是连续映射，则变分不等式问题(VIP)至少具有一个解。假设函数是单调的，那么可以保证变分不等式问题的解存在且唯一。

引理2.4 如果C是 $R^n$ 的非空闭凸集，而 $F:C\to R^n$ 是一个连续映射，那么对于任给的 $x,y\in C$，有 $\langle x-y,F\left(x\right)-F\left(y\right)\rangle \ge 0,\forall x,y\in C$。

定义2.5 假设序列 $\{X_n\}$ 是由 $X_1,X_2,\cdots ,X_n,\cdots$ 组成的随机变量，如果对于任意的 $ϵ>0$，有 $\underset{n\to \infty }{\lim }P\{\left(X_n-X\right)>ϵ\}=0$，那么就说序列 $\{X_n\}$ 以概率收敛到X，并且记为 $X_n\stackrel{P}{\to }X$。

引理2.6 马尔可夫不等式：对于任何 $ϵ>0$ 和 $r>0$，都有

$P\left(\left|X\right|\ge ϵ\right)\le \frac{E{\left(\left|X\right|\right)}^r}{{ϵ}^r}$

引理2.7 假设 $X_n\stackrel{P}{\to }X$，那么一定有 $X_{n_k}\to Xa.s.$ (几乎必然地)。

3. 算法提出

本节提出了一个gPADMM算法来解决问题(1.1)，其中问题(1.1)的增广拉格朗日形式为

$L\left(x,y,\lambda \right)={\theta }_1\left(x\right)+{\theta }_2\left(y\right)-{\lambda }^{\text{T}}\left(Ax+By-b\right)+\frac{\beta }{2}{\Vert Ax+By-b\Vert }^2.$ (3.1)

如果 ${\left(x^{*},y\right)}^{*}\in X\times Y$ 是问题的最优解，那么存在一个 ${\lambda }^{*}\in R^m$，使得 $\left(x^{*},y^{*},{\lambda }^{*}\right)$ 是一个鞍点，满足

$\{\begin{array}{l}L\left(x,y^{*},{\lambda }^{*}\right)-L\left(x^{*},y^{*},{\lambda }^{*}\right)\ge 0,\forall x\in X\\ L\left(x^{*},y,{\lambda }^{*}\right)-L\left(x^{*},y^{*},{\lambda }^{*}\right)\ge 0,\forall y\in Y\\ L\left(x^{*},y^{*},{\lambda }^{*}\right)-L\left(x^{*},y^{*},\lambda \right)\ge 0,\forall \lambda \in R^m\end{array}$ (3.2)

因此，由(3.2)得出

$\{\begin{array}{l}{x}^{*}=\arg \underset{x\in X}{\min }L\left(x,y^{*},{\lambda }^{*}\right),\\ y^{*}=\arg \underset{y\in Y}{\min }L\left(x^{*},y,{\lambda }^{*}\right),\\ {\lambda }^{*}=\arg \underset{x\in X}{\min }L\left(x^{*},y^{*},\lambda \right).\end{array}$ (3.3)

根据 [12] 中的引理2.1，本文可以得到问题(3.3)的一阶最优条件：

$\{\begin{array}{l}f\left(x\right)-f\left(x^{*}\right)-\left(x-x^{*}\right)\left(A^{\text{T}}{\lambda }^{*}\right)\ge 0,\forall x\in X,\\ g\left(y\right)-g\left(y^{*}\right)-\left(y-y^{*}\right)\left(B^{\text{T}}{\lambda }^{*}\right)\ge 0,\forall y\in Y,\\ {\left(\lambda -{\lambda }^{*}\right)}^{\text{T}}\left(A{x}^{*}+B{y}^{*}-b\right)\ge 0,\forall \lambda \in R^m,\end{array}$ (3.4)

因此，问题的解集也可以表示为包括所有满足条件的 $w^{*}\in W^{*}$，其中 $W:=X\times Y\times R^m$， $\theta \left(u\right):={\theta }_1\left(x\right)+{\theta }_2\left(y\right)$ 和

$u:=\left(\begin{array}{c}x\\ y\end{array}\right),w:=\left(\begin{array}{c}x\\ y\\ \lambda \end{array}\right),F\left(w\right):=\left(\begin{array}{c}-A^{\text{T}}\lambda \\ -B^{\text{T}}\lambda \\ Ax+By-b\end{array}\right).$ (3.5)

综上所述，针对可分离凸优化问题(1.1)，本文提出如下的gPADMM算法：

注3.1为了确保收敛， ${\xi }_k=\omega \left(a,b\right)$ 需要满足是某个独立且均匀分布的扩展序列，并且 ${\xi }_k=\omega \left(a,b\right)$ 的数学期望为 $E\left({\xi }_k\right),k=1,2,\cdots$。另外，在整个迭代过程不需要计算 $\rho \left(A^{\text{T}}A\right)$ 或 $A^{-1}$。

4. 收敛性证明

在本节中，本文充分结合变分不等式来证明算法3.1的全局收敛性。因此，公式(3.6)可变为具有如下形式的变分不等式：

$\{\begin{array}{l}\left(x^{\prime }-{\tilde{x}}^k\right)\left\{{\theta }_1\left({\tilde{x}}^k\right)-A^{\text{T}}\left[{\lambda }^k-\beta \left(A{\tilde{x}}^k+B{y}^k-b\right)\right]+\left(R+S\right){\Vert {\tilde{x}}^k-x^k\Vert }^2\right\}\ge 0,\forall x^{\prime }\in X,\\ \left(y^{\prime }-{\tilde{y}}^k\right)\left\{{\theta }_2\left({\tilde{y}}^k\right)-B^{\text{T}}\left[{\lambda }^k-\beta \left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)\right]+S{\Vert {\tilde{y}}^k-y^k\Vert }^2\right\}\ge 0,\forall y^{\prime }\in Y,\\ {\tilde{\lambda }}^k={\lambda }^k-\beta \left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right).\end{array}$ (4.1)

接下来将引入一些重要的引理和定理来证明算法的收敛性，如下所示。

引理4.1 令 ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由公式(3.6)生成得到，那么对于任意的 $w^{*}\in W^{*}$ 是问题(1.1)的最优解，得到

${\left(w^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)\ge {\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}B\left(y^k-{\tilde{y}}^k\right),$ (4.2)

其中 $Q=\left(\begin{array}{ccc}\left(R+S\right)I_{n_1}& 0_{n_1\times n_2}& 0_{n_1\times m}\\ 0_{n_2\times n_1}& \beta B^{\text{T}}B+S{I}_{n_2}& 0_{n_2\times m}\\ 0& 0& \frac{1}{\beta }{I}_m\end{array}\right)$。

证明 由于 $w^{*}\in W^{*},\tilde{x}\in X$ 并且 $\tilde{y}\in Y$，那么可知

$\{\begin{array}{l}{\left({\tilde{x}}^k-x^{*}\right)}^{\text{T}}\left({\theta }_1\left(x^{*}\right)-A^{\text{T}}{\lambda }^{*}\right)\ge 0,\\ {\left({\tilde{y}}^k-y^{*}\right)}^{\text{T}}\left({\theta }_2\left(y^{*}\right)-B^{\text{T}}{\lambda }^{*}\right)\ge 0.\end{array}$ (4.3)

将(3.6)分别加入(4.3)中且算子 ${\theta }_1$ 和 ${\theta }_2$ 的单调性，得出

$\{\begin{array}{l}{\left(A{\tilde{x}}^k-A{x}^{*}\right)}^{\text{T}}\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)+\left({\tilde{x}}^k-x^{*}\right)\left(R+S\right)\left(x^k-{\tilde{x}}^k\right)\ge \beta {\left(A{\tilde{x}}^k-A{x}^{*}\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right),\\ {\left(B{\tilde{y}}^k-B{y}^{*}\right)}^{\text{T}}\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)+\left({\tilde{y}}^k-x^{*}\right)S\left(y^k-{\tilde{y}}^k\right)\ge 0,\end{array}$ (4.4)

因此，由(4.4) (3.6)以及 $A{x}^{*}+B{y}^{*}=b$ 得知

$\begin{array}{l}\frac{1}{\beta }{\left({\tilde{\lambda }}^k-{\lambda }^{*}\right)}^{\text{T}}\left({\lambda }^k-{\tilde{\lambda }}^k\right)+{\left({\tilde{x}}^k-x^{*}\right)}^{\text{T}}\left(R+S\right)\left(x^k-{\tilde{x}}^k\right)+{\left({\tilde{y}}^k-x^{*}\right)}^{\text{T}}S\left(y^k-{\tilde{y}}^k\right)\\ \ge \beta {\left(A{\tilde{x}}^k-A{x}^{*}\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right),\end{array}$ (4.5)

在(4.5)的两边同时加上 $\beta {\left(B{\tilde{y}}^k-B{y}^{*}\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)$ 及矩阵Q的定义和 $A{x}^{*}+B{y}^{*}=b$，于是得到

$\begin{array}{c}{\left({\tilde{w}}^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)\ge \beta {\left(A{\tilde{x}}^k+B{\tilde{y}}^k-b\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\\ \ge {\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right),\end{array}$ (4.6)

这意味着

${\left({\tilde{w}}^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)\ge {\Vert w^k-{\tilde{w}}^k\Vert }_Q^2{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right).$

因此，引理4.1得证。

引理4.2 令 ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$ 是由公式(3.6)生成得到，那么对于任意的 $w^{*}\in W^{*}$ 是问题(1.1)的最优解，有

${\Vert w^k-w^{*}\Vert }_Q^2\ge {\Vert {\tilde{w}}^k-w^{*}\Vert }_Q^2+2{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)+{\Vert {\tilde{w}}^k-w^k\Vert }_Q^2.$ (4.7)

证明 由引理4.1和(3.6)式得

$\begin{array}{c}{\Vert {\tilde{w}}^k-w^{*}\Vert }_Q^2={\Vert w^k-w^{*}-\left(w^k-{\tilde{w}}^k\right)\Vert }_Q^2\\ ={\Vert w^k-w^{*}\Vert }_Q^2+2{\left(w^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)+{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ \le {\Vert w^k-w^{*}\Vert }_Q^2-2\left[{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\right]+{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ \le {\Vert w^k-w^{*}\Vert }_Q^2-{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2-2{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\end{array}$

因此，引理4.2证毕且公式(4.7)表明 $d\left(w^k,{\tilde{w}}^k\right)=w^k-{\tilde{w}}^k$ 是 ${\Vert w^k-w^{*}\Vert }_Q^2$ 的下降方向。

定理4.1 假设 $w^{*}$ 是问题(1.1)的解，那么对任给的迭代点 ${\tilde{w}}^k=\left({\tilde{x}}^k,{\tilde{y}}^k,{\tilde{\lambda }}^k\right)$，本文定义如下的一些函数：

$\{\begin{array}{l}{w}^{k+1}\left(\alpha \right)=w^k-{\alpha }_k\left(w^k-{\tilde{w}}^k\right),\\ {\theta }^k\left(\alpha \right)={\Vert w^k-w^{*}\Vert }_Q^2-{\Vert w^{k+1}\left(\alpha \right)-w^{*}\Vert }_Q^2,\\ \phi \left(w^k,{\tilde{w}}^k\right)={\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right),\\ {\psi }^k\left(\alpha \right)=2\alpha \phi \left(w^k,{\tilde{w}}^k\right)-{\alpha }^2{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2.\end{array}$ (4.8)

那么对任意的 $w^{*}=\left(x^{*},y^{*},{\lambda }^{*}\right)\in W^{*},\alpha \ge 0$，存在 ${\theta }^k\left(\alpha \right)\ge {\psi }^k\left(\alpha \right)$ (4.9)

证明 由(4.8)可知

$\begin{array}{c}{\Vert w^{k+1}\left(\alpha \right)-w^{*}\Vert }_Q^2={\Vert w^k-{\alpha }_k\left(w^k-{\tilde{w}}^k\right)-w^{*}\Vert }_Q^2\\ ={\Vert w^k-w^{*}\Vert }_Q^2-2{\alpha }_k{\left(w^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)+{\alpha }_{{}_k}^2{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ \le {\Vert w^k-w^{*}\Vert }_Q^2-2\alpha \phi \left(w^k,{\tilde{w}}^k\right)+{\alpha }^2{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ ={\Vert w^k-w^{*}\Vert }_Q^2-{\psi }^k\left(\alpha \right).\end{array}$

因此，(4.9)得证。

从定理4.1可知 ${\psi }^k\left(\alpha \right)$ 是 ${\theta }^k\left(\alpha \right)$ 的一个下界且 ${\theta }^k\left(\alpha \right)\ge {\psi }^k\left(\alpha \right)$。由 ${\psi }^k\left(\alpha \right)$ 的定义可知，它是关于 $\alpha$ 的一个二次函数，且它的最大值

${\alpha }_k=\frac{\phi \left(w^k,{\tilde{w}}^k\right)}{{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2}=\frac{{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)}{{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2}$。

也是最优的步长。

定理4.2 如果 $0<a<E\left({\xi }_k\right)=\rho <b$，序列 $\left\{w^k\right\}$ 是由广义的邻近交替方向乘子法生成，那么有

$E\left({\Vert w^{k+1}-w^{*}\Vert }_Q^2\right)\le E\left({\Vert w^k-w^{*}\Vert }_Q^2\right)-\frac{\rho \left(2-p\right)}{4}E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\right),$ (4.10)

证明 由引理4.1和(3.7)，我们得到

$\begin{array}{l}{\Vert w^{k+1}-w^{*}\Vert }_Q^2={\Vert w^k-{\eta }_k{\alpha }_k\left(w^k-{\tilde{w}}^k\right)-w^{*}\Vert }_Q^2\\ ={\Vert w^k-w^{*}\Vert }_Q^2-2{\eta }_k{\alpha }_k{\left(w^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)+{(}^{{\eta }_k}{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ \le {\Vert w^k-w^{*}\Vert }_Q^2-2{\eta }_k{\alpha }_k\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\right)+{\eta }_{{}_k}^2{\alpha }_{{}_k}^2{\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\\ \le {\Vert w^k-w^{*}\Vert }_Q^2-\frac{1}{2}{\eta }_k\left(2-{\eta }_k\right){\alpha }_k\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\right).\end{array}$ (4.11)

由于 ${\xi }_1,{\xi }_2,\cdots ,{\xi }_k,\cdots$ 是独立且均匀分布，可以推出 ${\eta }_k,w^k,{\tilde{w}}^k$ 和 ${\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)$ 也是独立的。又因为

$E\left({\eta }_k\right)=E\left(\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\xi }_k}\right)=\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}E\left({\xi }_k\right)}=\rho ,E\left(\alpha \right)>\frac{1}{2},$

那么 ${\Vert w^{k+1}-w^{*}\Vert }_Q^2$ 的数学期望满足

$\begin{array}{c}E\left({\Vert w^{k+1}-w^{*}\Vert }_Q^2\right)=E\left({\Vert w^k-{\eta }_k{\alpha }_k\left(w^k-{\tilde{w}}^k\right)-w^{*}\Vert }_Q^2\right)\\ =E\left({\Vert w^k-w^{*}\Vert }_Q^2\right)-E\left(2{\eta }_k{\alpha }_k{\left(w^k-w^{*}\right)}^{\text{T}}Q\left(w^k-{\tilde{w}}^k\right)\right)+{\left({\eta }_k{\alpha }_k\right)}^{2}E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\right)\\ \le E\left({\Vert w^k-w^{*}\Vert }_Q^2\right)-2E\left({\eta }_k\right)E\left({\alpha }_k\right)E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2+{\left({\lambda }^k-{\tilde{\lambda }}^k\right)}^{\text{T}}\left(B{y}^k-B{\tilde{y}}^k\right)\right)\\ +E\left({\eta }_k^2\right)E\left({\alpha }_k^2\right)E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\right)\\ \le E\left({\Vert w^k-w^{*}\Vert }_Q^2\right)-\frac{1}{4}\rho \left(2-\rho \right)E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\right).\end{array}$

最后，获得本文期望的结果。

推论4.1 如果 $0<a<E\left({\xi }_k\right)=\rho <b$，序列 $\left\{w^k\right\}$ 是由广义的邻近交替方向乘子法生成，那么有

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

(2) 序列 $E\left({\Vert w^{k+1}-w^{*}\Vert }_Q^2\right)$ 是单调且有界的。

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

定理4.3 如果 $0<a<E\left({\xi }_k\right)=\rho <b$，序列 $\left\{w^k\right\}$ 是由广义的邻近交替方向乘子法生成，那么序列 $\left\{w^k\right\}$ 依概率收敛到 $w^{\infty }\in W^{*}$。

证明 从推论4.1和引理4.2，得到

$\underset{k\to \infty }{\lim }E\left({\Vert A{\tilde{x}}^k+B{\tilde{y}}^k-b\Vert }_Q^2+{\Vert B\left(y^k-{\tilde{y}}^k\right)\Vert }_Q^2\right)=0.$ (4.12)

因为序列 $\{E\left({\tilde{w}}^k\right)\}$ 是有界的，那么它至少有一个聚集点。令 $E\left(w^{\infty }\right)$ 是序列 $\{E\left({\tilde{w}}^k\right)\}$ 的一个聚集点，并且存在一个子序列 $\{E\left({\tilde{w}}^{k_j}\right)\}$ 收敛到 $E\left(w^{\infty }\right)$，那么存在一个子序列 $\{{\tilde{w}}^{k_j}\}$ 依概率收敛到 ${\omega }^{\infty }\in W^{*}$，记为 ${\tilde{w}}^{k_j}\stackrel{P}{\to }{w}^{\infty }$。

从引理2.3得到子序列 $\{{\tilde{w}}^{k_j}\}$ 几乎必然地收敛到 ${\omega }^{\infty }$，那么它也可标记子序列为 $\{{\tilde{w}}^{k_j}\}$，记作

$\underset{j\to \infty }{\lim }{\tilde{w}}^{k_j}=w^{\infty }a.s.$ (4.13)

结合公式(3.6)、(4.12)和(4.13)，有

$\{\begin{array}{l}\underset{j\to \infty }{\lim }{\left(x-{\tilde{x}}^{k_j}\right)}^{\text{T}}\left\{{\theta }_1\left({\tilde{x}}^{k_j}\right)-A^{\text{T}}{\tilde{\lambda }}^{k_j}\right\}\ge 0,\forall x\in X\\ \underset{j\to \infty }{\lim }{\left(y-{\tilde{y}}^{k_j}\right)}^{\text{T}}\left\{{\theta }_2\left({\tilde{y}}^{k_j}\right)-B^{\text{T}}{\tilde{\lambda }}^{k_j}\right\}\ge 0,\forall y\in Y\\ \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-x^{\infty }\right)}^{\text{T}}\left\{{\theta }_1\left(x^{\infty }\right)-A^{\text{T}}{\lambda }^{\infty }\right\}\ge 0,\forall x\in X\\ {\left(y-y^{\infty }\right)}^{\text{T}}\left\{{\theta }_2\left(y^{\infty }\right)-B^{\text{T}}{\lambda }^{\infty }\right\}\ge 0,\forall y\in Y\\ \left(A{x}^{\infty }+B{y}^{\infty }-b\right)=0\end{array}$。

因此，可以推出 ${\omega }^{\infty }\in 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 }_Q^2\right)=0$。同时因为 $\underset{k\to \infty }{\lim }E\left({\Vert w^k-{\tilde{w}}^k\Vert }_Q^2\right)=0$，且对任给地 $\epsilon >0$，有 $l>0$，于是得到

$E\left({\Vert w^{k_l}-{\tilde{w}}^{k_l}\Vert }_Q^2\right)=\frac{\epsilon }{2}$

和

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

因此，对任意的 $k>k_l$，由(4.14)，可知

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

由此推出 $\underset{k\to \infty }{\lim }E\left({\Vert w^k-w^{\infty }\Vert }_Q^2\right)=0$。

结合引理2.2和公式(4.15)，可得对任给的 $\epsilon >0$，如果存在 $l>0$，只要 $k>l$，就有

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

那么得到 $\underset{k\to \infty }{\lim }P\left({\Vert w^k-w^{\infty }\Vert }_Q^2\ge ϵ\right)=0$。

因此，序列 $\{{\omega }^k\}$ 依概率收敛到 $w^{\infty }\in W^{*}$，记作 ${\omega }^k\stackrel{P}{\to }{\omega }^{\infty }$。

至此，收敛性证明全部完成。

5. 数值实验

本节通过数值实验重点介绍算法的有效性。

例5.1 首先，考虑陶、袁和何 [15] 提出的财务和统计问题，其形式如下：

$\min \left\{\frac{1}{2}{\Vert X-C\Vert }_F^2|X\in S_{+}^n\cap S_B\right\},$ (5.1)

其中 $S_B=\left\{H\in R^{n\times n}|H_L\ge H\ge H_U\right\}$。

通过引入一个辅助变量Y使得 $X-Y=0$，问题(5.1)可以重新表示为如下形式的可分离凸优化问题

$\min \left\{\frac{1}{2}{\Vert X-C\Vert }_F^2+\frac{1}{2}{\Vert Y-C\Vert }_F^2|X=Y,X\in S_{+}^n,Y\in S_B\right\},$ (5.2)

显然地，问题(5.2)是问题(1.1)的一个特殊形式，其中 $\rho \left(A^{\text{T}}A\right)=\rho \left(B^{\text{T}}B\right)=1$。令 $\lambda \in R^n$ 是线性约束 $X-Y=0$ 的拉格朗日乘子。对于给定的 $\left(X^k,Y^k,{\lambda }^k\right)$，算法能产生第k+1次迭代步，有

$\{\begin{array}{l}{\tilde{X}}^k=\underset{X\in S_{+}^n}{\arg \min }\left\{\frac{1}{2}{\Vert X-C\Vert }^2+\langle {\lambda }^k,X-Y^k\rangle +\frac{\beta }{2}{\Vert X-Y^k\Vert }^2+\frac{R+S}{2}{\Vert X-X^k\Vert }^2\right\},\\ {\tilde{Y}}^k=\underset{Y\in S_B}{\arg \min }\left\{\frac{1}{2}{\Vert Y-C\Vert }^2+\langle {\lambda }^k,{\tilde{X}}^k-Y\rangle +\frac{\beta }{2}{\Vert {\tilde{X}}^k-Y\Vert }^2+\frac{S}{2}{\Vert Y-Y^k\Vert }^2\right\},\\ {\tilde{\lambda }}^k={\lambda }^k-\beta \left({\tilde{X}}^k-{\tilde{Y}}^k\right).\end{array}$ (5.3)

迭代(5.3)的X-子问题是通过SVD分解来进行求解，它承担每次迭代过程中的主要计算负荷。迭代(5.3)的Y-子问题也是一个投影，有如下形式

${\tilde{Y}}^k=P_{S_B}\left\{\frac{1}{S+1+\beta }\left({\tilde{X}}^k-{\lambda }^k+C+S{Y}^k\right)\right\},$

其中 $P_{S_B}$ 表示根据欧几里得范数到集合S_B的投影。

在数值实验中，对于任意的所有 $i,j$，设 $C={\left(c_{ij}\right)}_{n\times n}$ 是一个满足 $c_{ij}\in \left(-1,1\right)$ 随机矩阵。对于每个给定，将测试20个随机实例。公平地说，将X⁰和Y⁰设置为 $n\times n$ 独立性矩阵， ${\lambda }^0$ 是一个n维零向量，并且将 $\epsilon =\frac{\max \left(\left|w^{k+1}-w^k\right|\right)}{\max \left(\left|w^0-{\tilde{w}}^0\right|\right)}\le {10}^{-6}$ 记为算法的终止准则。

得到的实验结果如下图1所示。

Figure 1. Comparisons of APPA, ePADM, gPADMM: n = 100, 200, 500

图1. APPA，ePADM，gPADMM三种算法的比较：n取100，200，500

Table 1. Numerical results of Example 5.1: Comparisons of APPA, ePADM, gPADMM

表1. 例5.1的实验结果：APPA，ePADM，gPADMM三种算法的比较

显然，从表1中可以看出，算法3.1的性能优于APPA算法和ePADM算法，因为其迭代和计算时间更少。因此，结果表明对于问题(1.1)，提出的算法是有效的。

6. 结论

本文针对线性凸优化问题和可分离凸优化问题，提出了广义的近似交替方向乘子算法，并且通过初步实验结果验证了算法是可行的。算法3.1是一种简单且有希望的迭代方案，其收敛速度比原有算法的收敛速度快。它在其他加速技术和其他应用中进行分析和设计的潜力以及更全面的计算研究是我们进一步研究的方向。

基金项目

国家自然科学基金(72071130)。