基于ALM的非精确加速算法

Inexact Acceleration Algorithm Based on ALM

摘要: 增广拉格朗日乘子法为经典有效的解决线性等式约束凸优化问题的一阶优化方法，算法通过原变量与对偶变量的交替迭代更新收敛至最优点。然而，子问题中原变量的更新在实际应用中往往无法精确求解。本文基于增广拉格朗日乘子法、对偶优化以及Nesterov加速技巧，提出一种非精确求解的增广拉格朗日乘子法，利用KKT条件从对偶残差的角度分析并从理论上证明该算法的收敛速率可达到$O\left(1/k^2\right)$ 。

Abstract: The Augmented Lagrangian Method is a classical and effective first-order optimization technique for solving convex optimization problems with linear equality constraints. The algorithm converges to the optimal solution through alternating iterative updates between the primal and dual variables. However, in practical applications, the update of the primal variables in the subproblem is often not solved exactly. In this paper, based on the Augmented Lagrangian Method, dual optimization, and Nesterov’s acceleration technique, we propose an inexact solution version of the Augmented Lagrangian Method. By leveraging the Karush-Kuhn-Tucker (KKT) conditions, we analyze and prove that the convergence rate of the proposed algorithm can achieve a rate of $O\left(1/k^2\right)$ .

1. 引言

现实世界中大量问题可转化为优化问题，特别地，具有特殊结构的凸优化问题是现代优化和计算数学领域的基石之一。原因在于以下两点：其一，凸优化问题具有良好的性质，如：局部最优解必然是全局最优解，并且具有丰富的理论背景，如最优性条件、对偶理论、拉格朗日乘数法等，这些理论为问题的分析、算法的设计及其性质提供了深入的理解；其二，现代科学和工程上的大量问题本质为求解凸优化问题，如信号处理与图像处理[1]-[4]、网络优化、控制理论、经济学与金融、机器学习与数据科学[5] [6]。为此，对于凸优化问题的研究显得尤为重要，特别是模型的求解以及加速算法成为了科学研究的重点与难点。

对于无约束光滑凸优化问题

$\underset{x\in \mathcal{X}}{\min }f\left(x\right),$

20世纪80年代，Nesterov在其开创性论文[7]中首次提出了仅使用一阶梯度信息且收敛速率可达到$O\left(1/k^2\right)$ 的加速算法，其迭代格式如下：

$\{\begin{array}{l}{x}_k=y_k-s\nabla f\left(y_k\right),\\ t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2},\\ y_{k+1}=x_k+\frac{t_k-1}{t_{k+1}}\left(x_k-x_{k-1}\right).\end{array}$

相较于基于当前位置的梯度来更新下一步位置的传统的梯度下降算法，Nesterov加速梯度方法的特殊之处在于，它先外推到一个预测位置，然后基于该预测位置的梯度信息进行调整，为此该加速技术也被称为Nesterov外推法。Nesterov加速算法提出时并没有受到太大的关注，原因在于当时的优化问题规模并不是很大，二阶优化方法可以非常有效地处理实际问题。随着越来越多领域优化问题规模的上升，Beck和Teboulle于2008年给出了Nesterov在1983年提出的针对两个函数的复合优化问题

$\underset{x\in {ℝ}^n}{\min }\psi \left(x\right)=f\left(x\right)+g\left(x\right),$

的加速算法版本——FISTA [8]，一阶加速梯度算法开始广泛应用。FISTA迭代格式如下：

$\{\begin{array}{l}{x}_k={\text{Prox}}_{t_{k}g}\left(y_k-t_k\nabla f\left(y_k\right)\right),\\ t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2},\\ y_{k+1}=x_k+\frac{t_k-1}{t_{k+1}}\left(x_k-x_{k-1}\right),\end{array}$

其中，$f\left(x\right),g\left(x\right)$ 为凸函数，且其中至少有一个是光滑的。FISTA核心思想为，第一步沿着前两步的计算方向计算一个新点，第二步在该新点处做一步近似点梯度迭代。此后，基于Nesterov加速技巧与FISTA思想受到了大量的关注与研究应用。

对于线性等式约束优化问题

$\begin{array}{l}\underset{x}{\min }f\left(x\right),\\ \text{s}\text{.t}\text{. }Ax=b,\end{array}$

其中$f\left(x\right)$ 为凸集$\mathcal{X}$ 上的凸函数，$A\in {ℝ}^{m\times n},b\in {ℝ}^m$ ，经典而有效的求解方法为增广拉格朗日法(ALM, Augmented Lagrangian Method)，其迭代格式如下：

$\{\begin{array}{l}{x}^{k+1}=\arg \underset{x}{\min }\left\{L_{\beta }\left(x,{\lambda }^k\right),x\in \mathcal{X}\right\},\\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}-b\right),\end{array}$

其中，增广拉格朗日函数

$L_{\beta }\left(x,\lambda \right)=f\left(x\right)-\langle \lambda ,Ax-b\rangle +\frac{\beta }{2}{\Vert Ax-b\Vert }^2,\lambda \in {ℝ}^m.$

ALM最初由Hestenes [9]和Powell [10]提出的(它最初被称为[9] [10]中的乘子法；见[11]-[13])。相较于二次罚函数法(Quadratic Penalty Method)，ALM通过引入对偶乘子，克服了原罚函数法中存在的病态问题。ALM不仅在理论上有完整的收敛保证，并且在实际应用中具有高效的性能，为此ALM成为科研与工程应用的基础且成熟的有效算法。关于ALM算法的研究有大量文献，这里仅列取部分，见[8] [9] [11]。

随着优化问题规模的上升，如何基于ALM设计加速算法受到了大量科研人员的关注。当$f\left(x\right)$ 可微时，He [14]结合Nesterov加速技巧[7]，提出收敛速度为$O\left(1/k^2\right)$ 的加速ALM，迭代格式如下：

$\{\begin{array}{l}{x}^{k+1}=\arg \underset{x\in \mathcal{X}}{\min }\left\{f\left(x\right)-\langle {\lambda }^k,Ax-b\rangle +\frac{1}{2}{\Vert Ax-b\Vert }_{H_k}^2\right\},\\ {\tilde{\lambda }}^k={\lambda }^k-H_k\left(A{x}^{k+1}-b\right),t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2},\\ {\lambda }^{k+1}={\tilde{\lambda }}^k+\frac{t_k-1}{t_{k+1}}\left({\tilde{\lambda }}^k-{\tilde{\lambda }}^{k-1}\right)+\frac{t_k}{t_{k+1}}\left({\tilde{\lambda }}^k-{\lambda }^k\right),\end{array}$

其中$k\ge 0$ ，H是任意的非单调递增对称正定矩阵。在此基础上，[15]给出$f\left(x\right)$ 仅为凸函数时，收敛速率为$O\left(1/k^2\right)$ 的加速ALM。

在实际应用中，ALM中的子问题$x^{k+1}$ 精确求解往往较为复杂，为此，是否可以在子问题非精确求解情况下设计算法使其仍可达到$O\left(1/k^2\right)$ 的收敛速率？本文基于ALM与Nesterov加速技巧提出一种非精确的加速ALM，并且从理论上给出收敛速率可达到$O\left(1/k^2\right)$ 的证明。

2. 预备知识

为了方便算法的收敛性说明，本章对符号进行统一的说明并给出预备知识。

对任意常数$p\in \left[0,\infty \right)$ 和向量$x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}\in {ℝ}^n$ ，向量x的$l^p$ -范数定义为${\Vert x\Vert }_p:={\left({\displaystyle \sum _{i=1}^n\left|x_i^p\right|}\right)}^{1/p}$ 。本文所述$\Vert \cdot \Vert$ 均表示$l^2$ -范数。对任意向量$x,y\in {ℝ}^n$ ，我们用$x^{\text{T}}y:={\displaystyle \sum _{i=1}^n{x}_i}{y}_i$ 表示${ℝ}^n$ 空间中的标准内积。

定义2.1. 设函数f为适当函数，如果$domf$ 是凸集，且

$f\left(\theta x+\left(1-\theta \right)y\right)\le \theta f\left(x\right)+\left(1-\theta \right)f\left(y\right),$

对所有$x,y\in domf,0\le \theta \le 1$ 都成立，则称f是凸函数。

定义2.2. 凸函数$f:{ℝ}^n\to ℝ$ ，其次微分为

$\partial f\left(x\right)=\left\{s:f\left(y\right)-f\left(x\right)\ge s^{\text{T}}\left(y-x\right),\forall y\in {ℝ}^n\right\}.$

定义2.3. 函数f的共轭函数$f^{*}:{ℝ}^n\to ℝ$ 定义如下

$f^{*}\left(x\right)=\underset{p\in {ℝ}^n}{\max }\left\{x^{\text{T}}p-f\left(p\right)\right\}.$

性质1. 共轭函数$f^{*}$ 的次微分性质

$y\in \partial f\left(x\right)\iff x\in \partial f^{*}\left(y\right).$

定义2.4. 函数f是一个参数为${\sigma }_f$ 的强凸函数，当且仅当存在一个常数${\sigma }_f>0$ ，使得函数

$f\left(x\right)-\frac{{\sigma }_f}{2}{\Vert x\Vert }^2$ 是凸函数，且对每一个x和y满足以下不等式：

$\langle p-q,x-y\rangle \ge {\sigma }_f{\Vert x-y\Vert }^2,p\in \partial f\left(x\right),q\in \partial f\left(y\right).$

引理2.1 若f是凸性参数为${\sigma }_f$ 的强凸函数，则共轭函数$f^{*}$ 可微且$\nabla f^{*}$ 是利普希茨连续函数，其利普

西茨常数$L\left(\nabla f^{*}\right)=\frac{1}{{\sigma }_f}$ ，即满足下列不等式：

$\nabla f^{*}\left(x\right)-\nabla f^{*}\left(y\right)\le \frac{1}{{\sigma }_f}\Vert x-y\Vert .$

3. 非精确加速ALM

对于线性等式约束优化问题

$\begin{array}{l}\underset{x}{\min }f\left(x\right),\\ \text{s}\text{.t}\text{. }Ax=b,\end{array}$ (1)

其中$f\left(x\right)$ 为凸集$\mathcal{X}$ 上的凸函数，$A\in {ℝ}^{m\times n},b\in {ℝ}^m$ 。本章具体展示以上优化问题的非精确加速ALM，在此之前，先给出以下假设：

假设1. 优化问题(1)中的函数$f\left(x\right)$ 是${\sigma }_f$ -强凸函数。

基于以上假设，下面给出优化问题(1)的非精确加速ALM，具体迭代格式如下：给定初值${\widehat{\lambda }}_1={\lambda }_0$ ，并作如下更新，

$\left(\text{I-AALM}\right)\{\begin{array}{l}{x}_k\approx \underset{x}{\arg \min }\left\{f\left(x\right)-{\left({\widehat{\lambda }}_k\right)}^{\text{T}}\left(Ax-b\right)+\frac{\beta }{2}{\Vert Ax-b\Vert }^2\right\},\\ {\lambda }_k={\widehat{\lambda }}_k-\beta \left(A{x}_k-b\right),\\ {\widehat{\lambda }}_{k+1}={\lambda }_k+\left(1-{\theta }_{k-1}\right)\frac{{\theta }_k}{{\theta }_{k-1}}\left({\lambda }_k-{\lambda }_{k-1}\right),\end{array}$ (2)

其中${\theta }_k=\frac{2}{k+2},k\ge 0$ 。

由算法I-AALM中子问题$x_k$ 最优性条件可知

$0\in \partial f\left(x_k\right)-A^{\text{T}}{\widehat{\lambda }}_k+\beta A^{\text{T}}\left(A{x}_k-b\right),$

结合算法I-AALM中${\lambda }_k$ 的更新方式，可得

$A^{\text{T}}{\lambda }_k\in \partial f\left(x_k\right).$

记误差向量${\delta }_k=f^{\prime }\left(x_k\right)-A^{\text{T}}{\lambda }_k$ ，其中$f^{\prime }\left(x_k\right)\in \partial f\left(x_k\right)$ ，所以

$\{\begin{array}{l}{\delta }_k=0,x_k是精确解,\\ {\delta }_k\ne 0,x_k是非精确解.\end{array}$

由${\delta }_k$ 的记法和性质1可得

$A^{\text{T}}{\lambda }_k+{\delta }_k\in \partial f\left(x_k\right)\Rightarrow x_k\in \nabla f^{*}\left(A^{\text{T}}{\lambda }_k+{\delta }_k\right)\Rightarrow A{x}_k\in A\nabla f^{*}\left(A^{\text{T}}{\lambda }_k+{\delta }_k\right).$

记误差向量${\eta }_k=A\nabla f^{*}\left(A^{\text{T}}{\lambda }_k\right)-A\nabla f^{*}\left(A^{\text{T}}{\lambda }_k+{\delta }_k\right)$ 。若f是凸性参数为${\sigma }_f$ 的强凸函数，易知$\nabla f^{\ast }$ 利普西茨连续，所以误差向量的上界易得

$\Vert {\eta }_k\Vert =\Vert A\nabla f^{*}\left(A^{\text{T}}{\lambda }_k\right)-A\nabla f^{*}\left(A^{\text{T}}{\lambda }_k+{\delta }_k\right)\Vert \le \frac{1}{{\sigma }_f}\sqrt{\rho \left(A^{\text{T}}A\right)}\Vert {\delta }_k\Vert .$

为此，子问题$x_k$ 求解的停止条件为：

${\delta }_k=f^{\prime }\left(x_k\right)-A^{\text{T}}{\lambda }_k,\Vert {\delta }_k\Vert \le \frac{{\sigma }_f{\theta }_{k-1}}{\sqrt{\rho \left(A^{\text{T}}A\right)}}{ϵ}_k,$ (3)

其中${ϵ}_k\ge 0$ 且满足${\displaystyle \sum _{k=1}^{\infty }{ϵ}_k}<\infty ,{ϵ}_{k+1}\le {ϵ}_k$ 。

4. 收敛性分析

本章给出非精确加速ALM的收敛分析并说明其收敛速率为$O\left(1/k^2\right)$ 。问题(1)的对偶函数为

$\begin{array}{c}D\left(\lambda \right)=\underset{x}{\min }\left\{f\left(x\right)-{\lambda }^{\text{T}}\left(Ax-b\right)\right\}\\ =-\underset{x}{\max }\left\{{\lambda }^{\text{T}}Ax-f\left(x\right)\right\}+{\lambda }^{\text{T}}b,\\ =-f^{*}\left(A^{\text{T}}\lambda \right)+{\lambda }^{\text{T}}b.\end{array}$

不难得到问题(1)的对偶问题

$\underset{\lambda }{\max }D\left(\lambda \right)=\underset{\lambda }{\max }\left\{-f^{*}\left(A^{\text{T}}\lambda \right)+{\lambda }^{\text{T}}b\right\}.$ (4)

因此，对原问题(1)的研究可转换为对对偶问题(4)的研究，本章以下内容将围绕问题(4)及假设1进行讨论。在此之前，我们先给出以下引理，这对本文算法的收敛性分析有着至关重要的作用。

引理4.1. 算法I-AALM 中参数${\theta }_k$ 满足$\frac{1-{\theta }_{k+1}}{{\theta }_{k+1}^2}\le \frac{1}{{\theta }_k^2},\forall k\ge 0$ 。

证明. 数学归纳法易证。

引理4.2. 记$s_k=\frac{1}{{\theta }_{k-1}}{\lambda }_k-\left(\frac{1}{{\theta }_{k-1}}-1\right){\lambda }_{k-1}-{\lambda }^{*}$ ，则$s_{k+1}=s_k+\frac{1}{{\theta }_k}\left({\lambda }_{k+1}-{\widehat{\lambda }}_{k+1}\right)$ .

证明. 由$s_k$ 的记法，有

$\begin{array}{c}{s}_{k+1}=\frac{1}{{\theta }_k}{\lambda }_{k+1}-\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-{\lambda }^{*}\\ =s_k+\frac{1}{{\theta }_k}{\lambda }_{k+1}-\frac{1}{{\theta }_k}{\lambda }_k+\left(1-\frac{1}{{\theta }_{k-1}}\right)\left({\lambda }_k-{\lambda }_{k-1}\right)\\ =s_k+\frac{1}{{\theta }_k}\left({\lambda }_{k+1}-{\lambda }_k+\left(1-\frac{1}{{\theta }_{k-1}}\right){\theta }_k\left({\lambda }_k-{\lambda }_{k-1}\right)\right)\\ =s_k+\frac{1}{{\theta }_k}\left({\lambda }_{k+1}-{\widehat{\lambda }}_{k+1}\right).\end{array}$

引理4.3. 设$\left\{{\lambda }_{k+1},{\widehat{\lambda }}_{k+1}\right\}$ 为I-AALM生成的点列，对任何的$\lambda \in R^m,k\ge 0$ ，有

$D\left({\lambda }_{k+1}\right)-D\left(\lambda \right)\ge \frac{1}{\beta }{\left(\lambda -{\widehat{\lambda }}_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+\frac{1}{2\beta }{\Vert {\lambda }_{k+1}-{\widehat{\lambda }}_{k+1}\Vert }^2+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1},$ (5)

其中${\eta }_{k+1}=A\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right)-A\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}+{\delta }_{k+1}\right)$ 。

证明. 因为$f\left(x\right)$ 是${\sigma }_f$ -强凸函数，所以其共轭函数$f^{*}$ 是凸函数，于是

$f^{*}\left(A^{\text{T}}\lambda \right)-f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right)\ge {\left(A^{\text{T}}\left(\lambda -{\lambda }_{k+1}\right)\right)}^{\text{T}}\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right)={\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}A\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right),$

进一步根据引理4.3.中${\eta }_{k+1}$ 的记法可得

$\begin{array}{l}D\left({\lambda }_{k+1}\right)-D\left(\lambda \right)\\ =f^{*}\left(A^{\text{T}}\lambda \right)-f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right)+{\left({\lambda }_{k+1}-\lambda \right)}^{\text{T}}b\\ \ge {\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}A\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}\right)+{\left({\lambda }_{k+1}-\lambda \right)}^{\text{T}}b\\ ={\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1}+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}\left(-b\right)+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}A\nabla f^{*}\left(A^{\text{T}}{\lambda }_{k+1}+{\delta }_{k+1}\right)\\ ={\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1}+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}\left(A{x}_{k+1}-b\right)\\ =\frac{1}{\beta }{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1}\\ =\frac{1}{\beta }{\left(\lambda -{\widehat{\lambda }}_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+\frac{1}{\beta }{\Vert {\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\Vert }^2+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1}\\ \ge \frac{1}{\beta }{\left(\lambda -{\widehat{\lambda }}_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+\frac{1}{2\beta }{\Vert {\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\Vert }^2+{\left(\lambda -{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1},\end{array}$

其中倒数第二个等号成立是根据$\left\{{\lambda }_k\right\}$ 的更新方式。

引理4.4. 设$\left\{{\lambda }_k\right\}$ 为I-AALM生成的点列，记${h^{\prime }}_k=D\left({\lambda }^{*}\right)-D\left({\lambda }_k\right)$ ，那么

$\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\ge \frac{{\Vert s_{k+1}\Vert }^2}{2\beta }-\frac{{\Vert s_k\Vert }^2}{2\beta }-\frac{1}{{\theta }_k}{\left(s_{k+1}\right)}^{\text{T}}{\eta }_{k+1}.$ (6)

证明. 由${h^{\prime }}_k=D\left({\lambda }^{*}\right)-D\left({\lambda }_k\right)$ ，易得到${h^{\prime }}_k\ge 0$ ，引理4.3.中对不等式(5)分别令$\lambda ={\lambda }_k,\lambda ={\lambda }^{*}$ 可得

${h^{\prime }}_k-{h^{\prime }}_{k+1}\ge \frac{1}{2\beta }{\Vert {\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\Vert }^2+\frac{1}{\beta }{\left({\lambda }_k-{\widehat{\lambda }}_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+{\left({\lambda }_k-{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1},$ (7)

$-{h^{\prime }}_{k+1}\ge \frac{1}{2\beta }{\Vert {\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\Vert }^2+\frac{1}{\beta }{\left({\lambda }^{*}-{\widehat{\lambda }}_{k+1}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+{\left({\lambda }^{*}-{\lambda }_{k+1}\right)}^{\text{T}}{\eta }_{k+1}.$ (8)

对以上两个不等式作如下处理：(7)式乘以$\left(\frac{1}{{\theta }_k}-1\right)$ 加到(8)式，那么

$\begin{array}{c}\left(\frac{1}{{\theta }_k}-1\right){h^{\prime }}_k-\frac{1}{{\theta }_k}{h^{\prime }}_{k+1}\ge \frac{1}{2\beta {\theta }_k}{\Vert {\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\Vert }^2+\frac{1}{\beta }{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\right)}^{\text{T}}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)\\ +{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\right)}^{\text{T}}{\eta }_{k+1}\end{array}$

上述不等式两端同时与$\frac{1}{{\theta }_k}$ 相乘得

$\begin{array}{c}\frac{1-{\theta }_k}{{\theta }_k^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\ge \frac{1}{2\beta }{\Vert \frac{1}{{\theta }_k}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)\Vert }^2+\frac{1}{\beta {\theta }_k}{\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)}^{\text{T}}\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\right)\\ +\frac{1}{{\theta }_k}{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\lambda }_{k+1}+{\lambda }^{*}\right)}^{\text{T}}{\eta }_{k+1}.\end{array}$

由$\frac{1-{\theta }_{k+1}}{{\theta }_{k+1}^2}\le \frac{1}{{\theta }_k^2},\forall k\ge 0$ ，上式进一步可化为

$\begin{array}{c}\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\ge \frac{1}{2\beta }{\Vert \frac{1}{{\theta }_k}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)\Vert }^2+\frac{1}{\beta {\theta }_k}{\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)}^{\text{T}}\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\right)\\ +\frac{1}{{\theta }_k}{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\lambda }_{k+1}+{\lambda }^{*}\right)}^{\text{T}}{\eta }_{k+1}.\end{array}$

取$a=\frac{1}{{\theta }_k}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right),b=\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}$ ，并利用等式关系

$\Vert a\Vert +2a^{\text{T}}b={\Vert a+b\Vert }^2-{\Vert b\Vert }^2,$

以上不等式可进一步转化为

$\begin{array}{l}\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\\ \ge \frac{1}{2\beta }{\Vert \frac{1}{{\theta }_k}\left({\widehat{\lambda }}_{k+1}-{\lambda }_{k+1}\right)+\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\Vert }^2-\frac{1}{2\beta }{\Vert \left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\Vert }^2\\ +\frac{1}{{\theta }_k}{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\lambda }_{k+1}+{\lambda }^{*}\right)}^{\text{T}}{\eta }_{k+1}\\ =\frac{1}{2\beta }{\Vert -\frac{1}{{\theta }_k}{\lambda }_{k+1}+\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k+{\lambda }^{*}\Vert }^2-\frac{1}{2\beta }{\Vert \left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\Vert }^2\\ +\frac{1}{{\theta }_k}{\left(\left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\lambda }_{k+1}+{\lambda }^{*}\right)}^{\text{T}}{\eta }_{k+1}\end{array}$

由引理4.2中$s_k$ 的记法，上式转化为

$\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\ge \frac{1}{2\beta }{\Vert s_{k+1}\Vert }^2-\frac{1}{2\beta }{\Vert \left(\frac{1}{{\theta }_k}-1\right){\lambda }_k-\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}+{\lambda }^{*}\Vert }^2-\frac{1}{{\theta }_k}{\left(s_{k+1}\right)}^{\text{T}}{\eta }_{k+1}.$ (9)

为满足(6)的形式，仅需将不等式(9)右端做如下处理

$\left(1-\frac{1}{{\theta }_k}\right){\lambda }_k+\frac{1}{{\theta }_k}{\widehat{\lambda }}_{k+1}-{\lambda }^{*}=\frac{1}{{\theta }_{k-1}}{\lambda }_k-\left(\frac{1}{{\theta }_{k-1}}-1\right){\lambda }_{k-1}-{\lambda }^{*},$

化简整理后有

${\widehat{\lambda }}_{k+1}={\lambda }_k+\left(1-{\theta }_{k-1}\right)\frac{{\theta }_k}{{\theta }_{k-1}}\left({\lambda }_k-{\lambda }_{k-1}\right),$

所以$\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k-\frac{1}{{\theta }_k^2}{h^{\prime }}_{k+1}\ge \frac{{\Vert s_{k+1}\Vert }^2}{2\beta }-\frac{{\Vert s_k\Vert }^2}{2\beta }-\frac{1}{{\theta }_k}{\left(s_{k+1}\right)}^{\text{T}}{\eta }_{k+1}$ 得证。

下面展示我们的主要收敛性定理，定理直观地解释了算法的收敛速度可达到$O\left(1/k^2\right)$ 。

定理4.1. 设$\left\{{\lambda }_{k+1},{\widehat{\lambda }}_{k+1}\right\}$ 为I-AALM生成的点列，那么

${h^{\prime }}_k\le \frac{4}{{\left(k+1\right)}^2}\left({\left(\sqrt{2\beta }{\overline{ϵ}}_k+\frac{1}{\sqrt{2\beta }}{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\right)}^2+2{\widetilde{ϵ}}_k\right)$

其中${h^{\prime }}_k=D\left({\lambda }^{*}\right)-D\left({\lambda }_k\right),{\overline{ϵ}}_k={\displaystyle \sum _{j=1}^k{ϵ}_j},{\widetilde{ϵ}}_k=2\beta {\displaystyle \sum _{j=1}^k{\left({ϵ}_j\right)}^2}$。

证明. 为了方便证明，我们设置以下记号：

$h_k=\frac{1}{{\theta }_{k-1}^2}{h^{\prime }}_k,p_k=\frac{{\Vert s_k\Vert }^2}{2\beta },$ (10)

由引理4.4中${h^{\prime }}_k$ 的记法可知${h^{\prime }}_k\ge 0$ 。引理4.3.中，令$\lambda ={\lambda }^{*},k=0$ 得

$\begin{array}{c}-h_1=-{h^{\prime }}_1\ge \frac{1}{\beta }{\left({\lambda }^{*}-{\widehat{\lambda }}_1\right)}^{\text{T}}\left({\widehat{\lambda }}_1-{\lambda }_1\right)+\frac{1}{2\beta }{\Vert {\lambda }_1-{\widehat{\lambda }}_1\Vert }^2+{\left({\lambda }^{*}-{\lambda }_1\right)}^{\text{T}}{\eta }_1\\ =\frac{1}{2\beta }{\Vert {\lambda }_1-{\lambda }^{*}\Vert }^2-\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+{\left({\lambda }^{*}-{\lambda }_1\right)}^{\text{T}}{\eta }_1\\ =p_1-\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2-{\left(s_1\right)}^{\text{T}}{\eta }_1.\end{array}$

其中第二个等号成立是因为等式关系

$\Vert a\Vert +2a^{\text{T}}b={\Vert a+b\Vert }^2-{\Vert b\Vert }^2,$

并且根据$x_k$ 的停止条件以及(10)中$p_k$ 的记法易知

${\left(s_k\right)}^{\text{T}}{\eta }_k\le \Vert s_k\Vert \cdot \Vert {\eta }_k\Vert \le \Vert s_k\Vert \left(\frac{1}{{\sigma }_f}\sqrt{\rho \left(A^{\text{T}}A\right)}\Vert {\delta }_k\Vert \right)\le \Vert s_k\Vert {\theta }_{k-1}{ϵ}_k=\sqrt{2\beta p_k}{\theta }_{k-1}{ϵ}_k,$

所以可以得到

$\begin{array}{c}{p}_1+h_1\le \frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+{\left(s_1\right)}^{\text{T}}{\eta }_1\le \frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+\sqrt{2\beta p_1}{\theta }_0{ϵ}_1\\ =\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+\sqrt{2\beta p_1}{ϵ}_1.\end{array}$ (11)

由引理4.4知

$h_k-h_{k+1}\ge p_{k+1}-p_k-\frac{1}{{\theta }_k}{\left(s_{k+1}\right)}^{\text{T}}{\eta }_{k+1}$

即$h_k-h_{k+1}\ge p_{k+1}-p_k-\frac{1}{{\theta }_k}\sqrt{2\beta p_{k+1}}{\theta }_k{ϵ}_{k+1}$ 。

两边求和，我们有

$h_1-h_k\ge p_k-p_1-{\displaystyle \sum _{j=1}^{k-1}\sqrt{2\beta p_{j+1}}}{ϵ}_{j+1}.$

所以(11)经过变形可得

$\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\ge p_1+h_1-\sqrt{2\beta p_1}{ϵ}_1\ge h_k+p_k-q_k,$ (12)

其中$q_k:={\displaystyle \sum _{j=1}^k\sqrt{2\beta p_j}}{ϵ}_j\ge 0$ ，由${ϵ}_k$ 及$p_k$ 的记法，见(3)和(10)，可知$q_k\le q_{k+1}$ ，所以

$q_k=q_{k-1}+{ϵ}_k\sqrt{2\beta p_k}\le q_{k-1}+{ϵ}_k\sqrt{2\beta }\sqrt{q_k+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2}.$ (13)

上式等价于

$\left(q_k+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\right)-{ϵ}_k\sqrt{2\beta }\sqrt{q_k+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2}-\left(q_{k-1}+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\right)\le 0,$

解得

$\begin{array}{c}\sqrt{q_k+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2}\le \frac{1}{2}\left({ϵ}_k\sqrt{2\beta }+\sqrt{2\beta {ϵ}_k^2+4\left(q_{k-1}+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\right)}\right)\\ \le \frac{1}{2}\left({ϵ}_k\sqrt{2\beta }+{ϵ}_k\sqrt{2\beta }+2\sqrt{q_{k-1}+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2}\right)\\ ={ϵ}_k\sqrt{2\beta }+\sqrt{q_{k-1}+\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2}\\ \le {ϵ}_k\sqrt{2\beta }+\sqrt{q_{k-1}}+\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert \end{array}$

其中第二个和最后一个不等号成立均因为$\sqrt{a^2+b^2}\le a+b,\left(a\ge 0,b\ge 0\right)$ ，所以由(13)知

$\begin{array}{c}{q}_k\le q_{k-1}+{ϵ}_k\sqrt{2\beta }\left({ϵ}_k\sqrt{2\beta }+\sqrt{q_{k-1}}+\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert \right)\\ =q_{k-1}+{ϵ}_k^{2}2\beta +{ϵ}_k\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert +{ϵ}_k\sqrt{2\beta }\sqrt{q_{k-1}}.\end{array}$

对上式两边求和，有

$q_k\le q_1+2\beta {\displaystyle \sum _{j=2}^k{ϵ}_j^2}+\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\displaystyle \sum _{j=2}^k{ϵ}_j}+\sqrt{2\beta }{\displaystyle \sum _{j=2}^k{ϵ}_j}\sqrt{q_{j-1}}.$ (14)

又由(11)及$h_1\ge 0$ 知

$p_1-{ϵ}_1\sqrt{2\beta }\sqrt{p_1}-\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\le 0,$

同理可解得

$\begin{array}{l}\sqrt{p_1}\le \frac{1}{2}\left(2{ϵ}_1\sqrt{2\beta }+\sqrt{{ϵ}_1^{2}2\beta +4\left(\frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2\right)}\right)\\ \le \frac{1}{2}\left({ϵ}_1\sqrt{2\beta }+{ϵ}_1\sqrt{2\beta }+2\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert \right)\\ ={ϵ}_1\sqrt{2\beta }+\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert \end{array}$

其中第一个不等号成立是因为$\sqrt{a^2+b^2}\le a+b,\left(a\ge 0,b\ge 0\right)$ 所以

$q_1={ϵ}_1\sqrt{2\beta }\sqrt{p_1}\le {ϵ}_1\sqrt{2\beta }\left({ϵ}_1\sqrt{2\beta }+\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert \right)=2\beta {ϵ}_1^2+{ϵ}_1\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert .$

把上述不等式代入(14)，得到

$\begin{array}{c}{q}_k\le 2\beta {ϵ}_1^2+{ϵ}_1\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert +2\beta {\displaystyle \sum _{j=2}^k{ϵ}_j^2}+\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\displaystyle \sum _{j=2}^k{ϵ}_j}+\sqrt{2\beta }{\displaystyle \sum _{j=2}^k{ϵ}_j}\sqrt{q_{j-1}}\\ \le 2\beta {\displaystyle \sum _{j=1}^k{ϵ}_j^2}+\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\displaystyle \sum _{j=1}^k{ϵ}_j}+\sqrt{2\beta q_k}{\displaystyle \sum _{j=1}^k{ϵ}_j}\\ ={\widetilde{ϵ}}_k+\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+\sqrt{2\beta q_k}{\overline{ϵ}}_k,\end{array}$

其中最后一个不等号成立是因为$q_k\le q_{k+1}$ 。所以上式转化为

$q_k-\sqrt{2\beta q_k}{\overline{ϵ}}_k-\left(\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+{\widetilde{ϵ}}_k\right)\le 0,$

同理可解得

$\begin{array}{c}\sqrt{q_k}\le \frac{1}{2}\left(\sqrt{2\beta }{\overline{ϵ}}_k+\sqrt{2\beta {\overline{ϵ}}_k^2+4\left(\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+{\widetilde{ϵ}}_k\right)}\right)\\ \le \sqrt{\frac{1}{2}\left(2\beta {\overline{ϵ}}_k^2+2\beta {\overline{ϵ}}_k^2+4\left(\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+{\widetilde{ϵ}}_k\right)\right)}\\ =\sqrt{2\beta {\overline{ϵ}}_k^2+2\left(\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+{\widetilde{ϵ}}_k\right)},\end{array}$

其中最后一个不等式成立是因为基本不等式$\frac{a+b}{2}\le \sqrt{\frac{a^2+b^2}{2}}$ 。结合上述不等式以及(12)和$p_k\ge 0$ ，

$\begin{array}{l}{h}_k\le \frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+q_k\le \frac{1}{2\beta }{\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert }^2+2\beta {\overline{ϵ}}_k^2+2\left(\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert {\overline{ϵ}}_k+{\widetilde{ϵ}}_k\right)\\ ={\left(\frac{1}{\sqrt{2\beta }}\Vert {\lambda }^{*}-{\widehat{\lambda }}_1\Vert +\sqrt{2\beta }{\overline{ϵ}}_k\right)}^2+2{\widetilde{ϵ}}_k.\end{array}$

5. 小结

ALM是一类解决线性等式约束凸优化问题的有效方法，不仅在理论上有完整的收敛保证，并且在实际应用中具有高效的性能。然而经典的ALM中子问题通常情况下无法精确求解，且收敛速率为$O\left(1/k\right)$ 。为此，本文基于原优化模型的对偶问题，结合子问题的非精确解对应的停止条件与Nesterov加速技巧设计非精确加速ALM框架，并利用KKT条件从对偶残差的角度证明该算法收敛且收敛速率为$O\left(1/k^2\right)$ 。