带有绝对值形式的非线性约束下的交替方向乘子法

Alternating Direction Method of Multipliers under Nonlinear Constraints with Absolute Value Form

摘要: 交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)广泛应用于线性约束优化问题，无论是凸目标函数还是非凸目标函数，其约束一般是线性约束。文章研究了具有绝对值形式的非线性约束的非凸极小化问题的ADMM。在假设相关函数满足Kurdyka-Lojasiewicz (KL)不等式的情况下，证明了由ADMM生成的迭代子序列收敛于问题的一个临界点，并根据一些数值例子说明了ADMM是可行的。

Abstract: The Alternating Direction Method of Multipliers (ADMM) is widely used for linear constraint optimization problems, whether the objective function is convex or non-convex, with constraints generally being linear. This article studies the ADMM applied to non-convex minimization problems with nonlinear constraints in the form of absolute values. Under the assumption that the relevant functions satisfy the Kurdyka-Lojasiewicz (KL) inequality, it is proved that the iterative subsequence generated by ADMM converges to a critical point of the problem. Additionally, some numerical examples are provided to illustrate the feasibility of ADMM.

1. 引言

近年来，Gabay等[1]提出的交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)由于能够解决套索问题[2]、矩阵完成问题[3]等凸优化问题而得到了广泛的关注。许多学者对ADMM的收敛性进行了分析[4] [5]。此外，部分学者还存在对ADMM的收敛速度的研究。例如，He等[6]利用变分不等式给出了ADMM在遍历意义上的收敛速度为O(1/k) (k表示迭代度量)，其研究问题为：

$\min \left\{f_1\left(x_1\right)+f_2\left(x_2\right)|A_1{x}_1+A_2{x}_2-b=0\right\}$

并且Davis等[7]指出，在遍历意义上的收敛速度是紧的。此外，对于非遍历意义，He等[8]表明ADMM的收敛速度为$O\left(1/\sqrt{k}\right)$ ，Davis等[7]也指出它是紧密的。

ADMM最初被用于求解具有线性约束的凸优化问题。目前，为了得到更广泛的应用，ADMM发展了两个方面：(1) 算法的推导。如通过线性化增强项和光滑目标函数[9]的线性化版本，以及通过将线性ADMM与Nesterov加速度[10]相结合的Fast-ADMM (FADMM)等。(2) 应用范围的扩展。一些研究人员已经将其扩展到更一般的约束，包括线性等式约束、线性不等式约束和非线性约束等[11]。

非凸目标函数的ADMM是近年来研究的热点之一。例如，Wang等[12]利用布雷格曼距离提出了近似ADMM。Zhang等[13]使用指数平均布雷格曼距离到所有历史迭代近似ADMM。最近，Guo等[14]使用ADMM用来求解线性约束下的非凸目标函数，即

$\min \left\{f\left(x\right)+g\left(y\right)|Ax+y-b=0\right\}$ (1)

其迭代格式为：

$\{\begin{array}{l}{x}^{k+1}\in \arg \min \left\{{ℒ}_{\beta }\left(x,y^k,{\lambda }^k\right)\right\}\hfill \\ y^{k+1}\in \arg \min \left\{{ℒ}_{\beta }\left(x^{k+1},y,{\lambda }^k\right)\right\}\hfill \\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+y^{k+1}-b\right).\hfill \end{array}$

在本文中，受式(1)的启发，考虑了以下形式的具有非线性约束的优化问题：

$\min \left\{f\left(x\right)+g\left(y\right)|Ax+\left|y\right|-b=0\right\}$ (2)

式中，$f:R^n\to R\cup \left\{+\infty \right\}$ 是一个下半连续函数，$g:R^m\to R$ 是一个连续可微的函数，并且$\nabla g$ 满足L > 0的利普希兹连续，$A\in R^{n\times n}$ 是一个矩阵，$b\in R^n$ 是一个向量，y中每个元素非零。另外，${ℒ}_{\beta }(\cdot )$ 表示为问题(2)的增广拉格朗日函数，其定义为：

${ℒ}_{\beta }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-\langle \lambda ,\left(Ax+\left|y\right|-b\right)\rangle +\frac{\beta }{2}{\Vert Ax+\left|y\right|-b\Vert }^2$ (3)

式中，$\Vert \cdot \Vert$ 在表示2-范数。

目前，还没有研究表明可以将ADMM用于问题(2)。因此，本文将使用ADMM来解决不同凸性假设下的问题(2)。我们将通过Kurdyka-Lojasiewicz (KL)不等式证明，如果增广拉格朗日函数是KL函数，那么ADMM生成的序列收敛到问题(2)的Karush-Kuhn-Tucker (KKT)点。最后用一些数值实验来说明其ADMM的有效性。

2. 预备知识

在本节中，将回顾一些关于非凸非光滑问题下的次梯度微分的符号和相关概念[15]。$F:R^n\rightrightarrows R^m$ 是点对集的映射，其图被定为：

$Graph\left(F\right)=\left\{\left(x,y\right)\in R^n\times R^m:y\in F\left(x\right)\right\}.$

对任意的集合$S\subseteq R^n$ ，任意的点$x\in R^n$ ，若S非空，点x到S的距离记为：

$d\left(x,S\right)=\underset{y\in S}{\inf }\Vert y-x\Vert .$ (4)

若$S=\varnothing$ ，则令$d\left(x,S\right)=+\infty$ 。

定义1 [8]：若函数$f:R^n\to R\cup \left\{+\infty \right\}$ 在$x_0$ 处满足$f\left(x_0\right)\le \lim \underset{\text{x}\to {\text{x}}_0}{\inf }f\left(x\right)$ ，则称函数f在$x_0$ 处下半连续。若f在每一点处均下半连续，则称f为下半连续函数。

定义2 [16]：设函数$f:R^n\to R\cup \left\{+\infty \right\}$ 为适当下半连续函数：

(1) f在$x\in domf$ 处的Fréchet次微分定义为

$\widehat{\partial }f\left(x\right)=\left\{u\in R^n:\underset{y\ne x}{\lim }\underset{y\to x}{\inf }\frac{f\left(y\right)-f\left(x\right)-\langle u,y-x\rangle }{\Vert y-x\Vert }\ge 0\right\}.$

当$x\ni domf$ 时，令$\widehat{\partial }f\left(x\right)=\varnothing$ 。

(2) f在$x\in domf$ 处的极限次微分定义为

$\partial f\left(x\right)=\left\{u\in R^n:\exists x^k\to x,f\left(x^k\right)\to f\left(x\right)\text{and}{u}^k\in \widehat{\partial }f\left(x\right)\to u\text{as}k\to \infty \right\}.$

注1

(1) 极限次微分是通过在x附近的点取Fréchet次微分的极限得到的，即定义2意味着$\widehat{\partial }f\left(x\right)\subseteq \partial f\left(x\right)$ 对于每个$u\in R^n$ ，其中第一个集合是闭凸的，而第二个集合仅是闭的。并不是在所有$x\in domf$ 处都有Fréchet次微分。

(2) $x\in domf$ 为f的极小值的一个必要条件是$0\in \partial f\left(x\right)$ 。

(3) 设$\left(x^k,x^{k^{*}}\right)\in Graph\left(\partial f\right)$ 为一个序列，收敛到$\left(x,x^{*}\right)$ 。根据$\partial f\left(x\right)$ 的定义，如果$f\left(x^k\right)$ 收敛到$f\left(x\right)\left(k\to +\infty \right)$ ，则$\left(x,x^{*}\right)\in Graph\left(\partial f\right)$ 。

(4) 如果$f:R^n\to R\cup \left\{+\infty \right\}$ 是一个适当的下半连续函数，$g:R^n\to R$ 是连续可微的，那么对于任意$x\in domf$ ，有$\partial \left(f+g\right)=\partial f\left(x\right)+\nabla g\left(y\right)$ 。

引理1 [17]：设函数$G\left(x,y\right)=f\left(x\right)+h\left(y\right)$ ，其中$f:R^n\to R\cup \left\{+\infty \right\}$ 和$h:R^m\to R$ 都是适当下半连续函数。当$\forall \left(x,y\right)\in domG=domf\times domh$ ，有

$\partial G\left(x,y\right)={\partial }_{x}G\left(x,y\right)\times {\partial }_{y}G\left(x,y\right).$

定义3 [17]：(KL不等式) 设$f:R^n\to R\cup \left\{+\infty \right\}$ 为一个适当的下半连续函数。对于 $-\infty <{\eta }_1<{\eta }_2\le +\infty$ ，

$\left[{\eta }_1<f<{\eta }_2\right]=\left\{x\in R^n:{\eta }_1<f\left(x\right)<{\eta }_2\right\}$ 。

我们说函数f在$x^{*}\in domf$ 处具有KL性质，如果存在$\eta \in \left(\text{0,}+\infty \right]$ ，$x^{*}$ 的一个邻域U，以及一个连续凹函数$\phi :\left[0,\eta \right)\to R_{+}$ ，使得

(1) $\phi \left(0\right)=0$ ；

(2) $\phi$ 在$\left(0,+\infty \right)$ 上连续可微且在0处连续；

(3) $\forall s\in \left(0,\eta \right),{\phi }^{\prime }\left(s\right)>0$ ；

(4) 对于所有x在$U\cap \left[f\left(x^{*}\right)<f<f\left(x^{*}\right)+\eta \right]$ 中，KL不等式成立

${\phi }^{\prime }\left(f\left(x\right)-f\left(x^{*}\right)\right)d\left(0,\partial f\left(x\right)\right)\ge 1$ 。

定义4 [18]：(一致KL性质) 设$\Omega$ 为一个紧集，函数$f:R^n\to R\cup \left\{+\infty \right\}$ 是一个适当的下半连续函数。

(1) 如果在给定点$\overline{x}\in dom\partial f=\left\{x|\partial f\left(x\right)\ne \varnothing \right\}$ 处，存在$\epsilon >0,\eta >0$ ，和$\phi \in {\Phi }_{\eta }$ 使得对于所有$\overline{x}\in \Omega$ ，

$\left\{x\in R^n:d\left(x,\Omega \right)<\epsilon \right\}\cap \left[f\left(\overline{x}\right)<f<f\left(\overline{x}\right)+\eta \right]$

且以下不等式成立

${\phi }^{\prime }\left(f\left(x\right)-f\left(\overline{x}\right)\right)d\left(0,\partial f\left(x\right)\right)\ge 1$ 。

(2) 如果f在$dom\partial f$ 上的任意点都满足(1)，则f是一个KL函数。

定义5 [19]：(梯度利普希茨连续) 给定一个可微函数f，对于所有$x,y\in domf$ ，如果存在$L>0$ ，使得

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert$ 。

引理2 [19]：(二次上界) 设可微函数f的定义域为$R^n$ ，并且$\nabla f$ 是利普希茨连续的，L为其利普希茨常数，则f具有二次上界：

$\left|f\left(y\right)-f\left(x\right)-\nabla f{\left(x\right)}^{\text{T}}\left(y-x\right)\right|\le \frac{L}{2}{\Vert y-x\Vert }^2,\forall x,y\in domf$ 。

定义6：$\left(x^{*},y^{*},{\lambda }^{*}\right)$ 是问题(2)的增广拉格朗日函数${ℒ}_{\beta }(\cdot )$ 的一个临界点。则其满足

$A^{\text{T}}{\lambda }^{*}\in \partial f\left(x^{*}\right);\nabla g\left(y^{*}\right)={\lambda }^{*}\cdot \text{sign}\left(y^{*}\right);A{x}^{*}+\left|y^{*}\right|-b=0.$

备注1：定义6中，我们可以看“$\cdot$ ”表示两个向量相乘得到一个新的向量。下文中的表示意义同上。

定理1 [20]：(有限长度性质) 设函数$\Psi$ 是一个KL函数，并且满足下面的假设：

(1) $f:R^n\to \left(-\infty ,+\infty \right]$ 和$g:R^m\to \left(-\infty ,+\infty \right]$ 均是适当下半连续函数，并且$\underset{R^n\times R^m}{\inf }\Psi >-\infty ,\underset{R^n}{\inf }f>-\infty$ 以及$\underset{R^m}{\inf }g>-\infty$ ；

(2) $H:R^n\times R^m\to R$ 是个连续可微函数，并且$\nabla H$ 在有界集上是联合利普希茨连续的，即对任意的$\forall B_1\times B_2\subset R^n\times R^m,\exists L>0,\forall \left(x_i,y_i\right)\in B_1\times B_2,i=1,2$ 有

$\Vert \left({\nabla }_{x}H\left(x_1,y_1\right)-{\nabla }_{x}H\left(x_2,y_2\right),{\nabla }_{y}H\left(x_1,y_1\right)-{\nabla }_{y}H\left(x_2,y_2\right)\right)\Vert \le L\Vert \left(x_1-x_2,y_1-y_2\right)\Vert .$

则有以下结论成立：

(1) 序列$\left\{z^k\right\}$ 的长度有限，即

${\displaystyle \sum _{k=1}^{\infty }\Vert z^{k+1}-z^k\Vert }<+\infty ;$

(2) 序列$\left\{z^k\right\}$ 收敛到$\Psi$ 的一个临界点$z^{*}=\left(x^{*},y^{*}\right)$ 。

备注2：续可根据临界点的性质，$\omega \left(z^0\right)$ 是一个非空紧集，并且$\Psi$ 在$\omega \left(z^0\right)$ 上连续。在定义4中，设$\Omega =\omega \left(z^0\right)$ ，对于任意的$k>l$ (l是一个足够大的正整数)，

${\phi }^{\prime }\left(\Psi \left(z^k\right)-\Psi \left(\overline{z}\right)\right)d\left(0,\partial \Psi \left(z^k\right)\right)\ge 1.$

备注3：定理1中$\left\{z^k\right\}$ 的迭代序列是收敛的。不难看出，问题(2)中${ℒ}_{\beta }(\cdot )$ 的临界点正是其KKT点。

引理3：设迭代序列$\left\{y^k\right\}$ 收敛到$\left\{y^{*}\right\},y^k\in R^n$ 。则总存在N使得对于$k>N$ ，使得

$\text{sign}\left(y^k\right)=\text{sign}\left(y^{k+1}\right).$

3. 收敛性分析

在本节中，假设问题(2)至少存在一个KKT点。此外，假设问题(2)中的两个子问题的最小化问题都具有解。因此，问题(2)的ADMM是定义良好的，并且生成一个无限迭代序列$\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 。求解问题(2)的ADMM设计如下：

$\{\begin{array}{l}{x}^{k+1}\in \text{arg}\min \left\{{ℒ}_{\beta }\left(x,y^k,{\lambda }^k\right)\right\}\hfill \\ y^{k+1}\in \text{arg}\min \left\{{ℒ}_{\beta }\left(x^{k+1},y,{\lambda }^k\right)\right\}\hfill \\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+\left|y^{k+1}\right|-b\right).\hfill \end{array}$ (5)

根据问题(2)的优化条件，有

$\{\begin{array}{l}0\in \partial f\left(x^{k+1}\right)-A^{\text{T}}{\lambda }^k+\beta A^{\text{T}}\left(A{x}^{k+1}+\left|y^k\right|-b\right)\hfill \\ 0=\nabla g\left(y^{k+1}\right)-{\lambda }^k\cdot \text{sign}\left(y^{k+1}\right)+\beta \left(A{x}^{k+1}+\left|y^{k+1}\right|-b\right)\cdot \text{sign}\left(y^{k+1}\right)\hfill \end{array}$ (6)

基于(6)和(5)中的第三个等式，得到

$\{\begin{array}{l}{A}^{\text{T}}{\lambda }^k+\beta A^{\text{T}}\left(A{x}^{k+1}+\left|y^k\right|-b\right)\in \partial f\left(x^{k+1}\right)\hfill \\ \nabla g\left(y^{k+1}\right)={\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right)\hfill \\ {\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+\left|y^{k+1}\right|-b\right)\hfill \end{array}$ (7)

在本文中，我们还做了以下假设：

假设1：设$f:R^n\to R\cup \left\{+\infty \right\}$ 是一个适当的下半连续函数，$g:R^n\to R$ 是一个可微函数，并且$\nabla g$ 满足利普希茨连续，并且$L>0$ 。假设$\beta \sigma >2L,\sigma \in \left[0,1\right]$ 使得$\delta =\left(\beta \sigma -2L\right)/2-L^2/\beta >0$ 。

为了后续讨论，需要以下引理：

引理4：设$\left(x^{*},y^{*},{\lambda }^{*}\right)$ 是${ℒ}_{\beta }\left({\omega }^{k+1}\right)$ 的一个临界点，并且$y^{*}$ 中的每个元素均不为0。设${\left\{{\omega }^k\right\}}_{k\ge 0}={\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}}_{k\ge 0}$ 为算法(5)生成的序列。假设假设1成立并且$\left\{y^k\right\}$ 收敛到$y^{*}$ 。存在一个N当$k>N$ ，则有

${ℒ}_{\beta }\left({\omega }^{k+1}\right)\le {ℒ}_{\beta }\left({\omega }^k\right)-\delta {\Vert y^{k+1}-y^k\Vert }^2.$ (8)

证明：基于增广拉格朗日函数${ℒ}_{\beta }\left(\omega \right)$ 的定义，有

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)={ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)+\langle {\lambda }^k-{\lambda }^{k+1},A{x}^{k+1}+\left|y^{k+1}\right|-b\rangle \\ ={ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)+\frac{1}{\beta }{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2\end{array}$ (9)

和

$\begin{array}{l}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)-L_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)\\ =f\left(x^{k+1}\right)+g\left(y^k\right)-\langle {\lambda }^k,A{x}^{k+1}+\left|y^k\right|-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^k\right|-b\Vert }^2\\ -\left\{f\left(x^{k+1}\right)+g\left(y^{k+1}\right)-\langle {\lambda }^k,A{x}^{k+1}+\left|y^{k+1}\right|-b\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^{k+1}\right|-b\Vert }^2\right\}\\ =g\left(y^k\right)-g\left(y^{k+1}\right)+\langle {\lambda }^k,\left|y^{k+1}\right|-\left|y^k\right|\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^k\right|-b\Vert }^2-\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^{k+1}\right|-b\Vert }^2.\end{array}$ (10)

由于$\nabla g$ 满足$L>0$ 的利普希兹连续，根据引理2和式(7)中的第二个等式，可得：

$g\left(y^k\right)\ge g\left(y^{k+1}\right)+{\lambda }^{k+1^{\text{T}}}\text{sign}\left(y^{k+1}\right)\left(y^k-y^{k+1}\right)-\frac{L}{2}{\Vert y^k-y^{k+1}\Vert }^2.$ (11)

将(11)带入到(10)中可得：

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)-L_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)\ge \langle {\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right),y^k-y^{k+1}\rangle +\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^k\right|-b\Vert }^2\\ -\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^{k+1}\right|-b\Vert }^2-\langle {\lambda }^k,\left|y^k\right|-\left|y^{k+1}\right|\rangle -\frac{L}{2}{\Vert y^k-y^{k+1}\Vert }^2.\end{array}$ (12)

回忆

${\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+\left|y^{k+1}\right|-b\right)$ ,

即

$A{x}^{k+1}+\left|y^k\right|-b=\frac{1}{\beta }\left({\lambda }^k-{\lambda }^{k+1}\right)+\left(\left|y^k\right|-\left|y^{k+1}\right|\right).$

然后

$\begin{array}{c}\frac{\beta }{2}{\Vert A{x}^{k+1}+\left|y^k\right|-b\Vert }^2=\frac{\beta }{2}{\Vert \frac{1}{\beta }\left({\lambda }^k-{\lambda }^{k+1}\right)+\left(\left|y^k\right|-\left|y^{k+1}\right|\right)\Vert }^2\\ =\frac{1}{2\beta }{\Vert {\lambda }^k-{\lambda }^{k+1}\Vert }^2+\frac{\beta }{2}{\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2+\langle {\lambda }^k-{\lambda }^{k+1},\left|y^k\right|-\left|y^{k+1}\right|\rangle \end{array}$ (13)

组合(12)和(13)，可得

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)-L_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)\ge \langle {\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right),y^k-y^{k+1}\rangle -\langle {\lambda }^k,\left|y^k\right|-\left|y^{k+1}\right|\rangle \\ +\frac{\beta }{2}{\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2+\langle {\lambda }^k-{\lambda }^{k+1},\left|y^k\right|-\left|y^{k+1}\right|\rangle -\frac{L}{2}{\Vert y^k-y^{k+1}\Vert }^2.\end{array}$ (14)

而

$\begin{array}{l}\langle {\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right),y^k-y^{k+1}\rangle -\langle {\lambda }^k,\left|y^k\right|-\left|y^{k+1}\right|\rangle +\langle {\lambda }^k-{\lambda }^{k+1},\left|y^k\right|-\left|y^{k+1}\right|\rangle \\ =\langle {\lambda }^{k+1},y^k\cdot \text{sign}\left(y^{k+1}\right)-\left|y^{k+1}\right|\rangle -\langle {\lambda }^k,\left|y^k\right|-\left|y^{k+1}\right|\rangle +\langle {\lambda }^k-{\lambda }^{k+1},\left|y^k\right|-\left|y^{k+1}\right|\rangle \\ =\langle {\lambda }^{k+1},y^k\cdot \text{sign}\left(y^{k+1}\right)\rangle -\langle {\lambda }^{k+1},\left|y^{k+1}\right|\rangle -\langle {\lambda }^{k+1},\left|y^k\right|\rangle +\langle {\lambda }^{k+1},\left|y^{k+1}\right|\rangle \\ =\langle {\lambda }^{k+1},y^k\cdot \text{sign}\left(y^{k+1}\right)\rangle -\langle {\lambda }^{k+1},\left|y^k\right|\rangle \\ =\langle {\lambda }^{k+1},y^k\cdot \text{sign}\left(y^{k+1}\right)\rangle -\langle {\lambda }^{k+1},y^k\cdot \text{sign}\left(y^k\right)\rangle \\ =\langle {\lambda }^{k+1},y^k\cdot \left(\text{sign}\left(y^{k+1}\right)-\text{sign}\left(y^k\right)\right)\rangle .\end{array}$ (15)

从式(15)中容易看出，存在一个N，当$k>N$ 时，根据引理3，可得：

$\langle {\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right),y^k-y^{k+1}\rangle -\langle {\lambda }^k,\left|y^k\right|-\left|y^{k+1}\right|\rangle +\langle {\lambda }^k-{\lambda }^{k+1},\left|y^k\right|-\left|y^{k+1}\right|\rangle =0.$

根据

${\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2={\sigma }_k{\Vert y^k-y^{k+1}\Vert }^2,{\sigma }_k\in \left[0,1\right]$

可得：

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)-L_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^k\right)\ge \frac{\beta }{2}{\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2-\frac{L}{2}{\Vert y^k-y^{k+1}\Vert }^2\\ =\frac{\beta {\sigma }_k}{2}{\Vert y^k-y^{k+1}\Vert }^2-\frac{L}{2}{\Vert y^k-y^{k+1}\Vert }^2\\ =\frac{\beta {\sigma }_k-L}{2}{\Vert y^k-y^{k+1}\Vert }^2.\end{array}$ (16)

利用定义5和等式(7)当中的第二个等式，可得：

$\Vert {\lambda }^{k+1}\cdot \text{sign}\left(y^{k+1}\right)-{\lambda }^k\cdot \text{sign}\left(y^k\right)\Vert \le L\Vert y^{k+1}-y^k\Vert .$ (17)

根据式(17)，可以知道存在一个利普希茨常数L，使得：

$\Vert {\lambda }^{k+1}\pm {\lambda }^k\Vert \le L\Vert y^{k+1}-y^k\Vert .$ (18)

组合(9)、(16)和(18)可得：

$\begin{array}{c}{ℒ}_{\beta }\left(x^{k+1},y^{k+1},{\lambda }^{k+1}\right)\le {ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)-\left(\frac{\beta {\sigma }_k-L}{2}-\frac{L^2}{\beta }\right){\Vert y^k-y^{k+1}\Vert }^2\\ \le {ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)-\left(\frac{\beta {\sigma }_k-L}{2}-\frac{L^2}{\beta }\right){\Vert y^k-y^{k+1}\Vert }^2.\end{array}$ .

其中，上述第二个不等式满足$x^{k+1}$ 是${ℒ}_{\beta }\left(x,y^k,{\lambda }^k\right)$ 中关于x的最小值，即

${ℒ}_{\beta }\left(x^{k+1},y^k,{\lambda }^k\right)\le {ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right).$

令$\sigma =\inf \left\{{\sigma }_k\right\}$ ，则

$\delta =\frac{\beta \sigma -2L}{2}-\frac{L^2}{\beta }.$

因此，引理4成立。

备注4：由于$\sigma =\inf \left\{{\sigma }_k\right\}$ 和${\sigma }_k\in \left(\text{0},\text{1}\right]$ ，则说明$\sigma \ge 0$ 。然而对于任意的k，都有$0<{\sigma }_k\le 1$ ，这就意味着$\sigma =\underset{k\ge 0}{\inf }\left\{{\sigma }_k\right\}={\min }_{k\ge 0}\left\{{\sigma }_k\right\}>0$ 。因此，存在$\xi =\frac{{\min }_{k\ge 0}\left\{{\sigma }_k\right\}}{2}$ 使得$\sigma >\xi >0$ 。

备注5：由$\delta >0$ ，根据引理3，${ℒ}_{\beta }\left({\omega }^k\right)$ 单调递减。

接下来，我们给出一些充分条件来保证算法(5)生成的序列$\left\{{\omega }^k=\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是有界的。

引理5：设$\left\{{\omega }^k\right\}=\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是算法(5)生成的序列，并假设

$\underset{y}{\inf }\left\{g\left(y\right)-\tau {\left|\nabla g\left(y\right)\right|}^2\right\}=:\overline{g}>-\infty .$

那么以下陈述是正确的。

(1) f是强制性的，即$\lim {\text{inf}}_{{\left|x\right|}^2\to +\infty }f\left(x\right)=+\infty$ ；

(2) 存在常数$\tau =\frac{1}{2L}$ 。

证明：根据引理4，可得：

${ℒ}_{\beta }\left(x^k,y^k,{\lambda }^k\right)\le {ℒ}_{\beta }\left(x^0,y^0,{\lambda }^0\right).$

然后，结合${\lambda }^k\cdot \text{sign}\left(y^k\right)=\nabla g\left(y^k\right)$ ，可得：

$\begin{array}{c}{ℒ}_{\beta }\left(x^0,y^0,{\lambda }^0\right)\ge f\left(x^k\right)+g\left(y^k\right)-\langle {\lambda }^k,\left(A{x}^k+\left|y^k\right|-b\right)\rangle +\frac{\beta }{2}{\Vert A{x}^k+\left|y^k\right|-b\Vert }^2\\ =f\left(x^k\right)+g\left(y^k\right)-\frac{1}{2\beta }{\Vert {\lambda }^k\Vert }^2+\frac{\beta }{2}{\Vert A{x}^k+\left|y^k\right|-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\\ =f\left(x^k\right)+\left(g\left(y^k\right)-\frac{1}{2L}{\Vert \nabla g\left(y^k\right)\Vert }^2\right)+\left(\frac{1}{2L}-\frac{1}{2\beta }\right){\Vert {\lambda }^k\Vert }^2+\frac{\beta }{2}{\Vert A{x}^k+\left|y^k\right|-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\\ \ge f\left(x^k\right)+\overline{g}+\left(\tau -\frac{1}{2\beta }\right){\Vert {\lambda }^k\Vert }^2+\frac{\beta }{2}{\Vert A{x}^k+\left|y^k\right|-b-\frac{1}{\beta }{\lambda }^k\Vert }^2.\end{array}$

观察陈述(1)意味着$\underset{x}{\inf }f\left(x\right)>-\infty$ 。由$\beta >2L$ 得到$\left\{x^k\right\},\left\{{\lambda }^k\right\}$ 和$\left\{\frac{\beta }{2}{\Vert A{x}^k+\left|y^k\right|-b-\frac{1}{\beta }{\lambda }^k\Vert }^2\right\}$ 是有界的。因此，$\left\{y^k\right\}$ 是有界的，从而，$\left\{{\omega }^k\right\}$ 是有界的。

引理6：设$\left\{{\omega }^k\right\}=\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是算法(5)生成的序列，且$\left\{{\omega }^k\right\}$ 是有界的。那么，

${\displaystyle \sum _{k=0}^{+\infty }{\Vert {\omega }^{k+1}-{\omega }^k\Vert }^2}<+\infty .$ (19)

证明：为了证明(19)成立，考虑三种情况：

${\displaystyle \sum _{k=0}^{\infty }{\Vert y^{k+1}-y^k\Vert }^2}<+\infty ,{\displaystyle \sum _{k=0}^{\infty }{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2}<+\infty ,{\displaystyle \sum _{k=0}^{\infty }{\Vert x^{k+1}-x^k\Vert }^2}<+\infty .$

首先，证明${\displaystyle \sum _{k=0}^{\infty }{\Vert y^{k+1}-y^k\Vert }^2}<+\infty$ 。由于$\left\{{\omega }^k\right\}$ 是有界的，它至少有一个聚点。设$\left\{{\omega }^{*}\right\}$ 是$\left\{{\omega }^k\right\}$ 的一个聚点，$\left\{{\omega }^{k^j}\right\}$ 是收敛到它的子序列，即${\omega }^{k^j}\to {\omega }^{*}$ 。由于f是下半连续的且g是连续的，${ℒ}_{\beta }(\cdot )$ 是下半连续的，可得：

${ℒ}_{\beta }\left({\omega }^{*}\right)\le \underset{j\to +\infty }{\lim }\inf {ℒ}_{\beta }\left({\omega }^{k^j}\right).$

由于$\left\{{ℒ}_{\beta }\left({\omega }^{k^j}\right)\right\}$ 收敛，所以$\left\{{ℒ}_{\beta }\left({\omega }^{k^j}\right)\right\}$ 有界。此外，$\left\{{ℒ}_{\beta }\left({\omega }^k\right)\right\}$ 是收敛的，并且$\left\{{ℒ}_{\beta }\left({\omega }^k\right)\right\}\ge \left\{{ℒ}_{\beta }\left({\omega }^{*}\right)\right\}$ 。根据式(8)，可得：

$\delta {\Vert y^{k+1}-y^k\Vert }^2\le L_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{k+1}\right).$ (20)

根据式(20)，可得：

${\displaystyle \sum _{k=0}^n\delta }{\Vert y^{k+1}-y^k\Vert }^2\le L_{\beta }\left({\omega }^0\right)-L_{\beta }\left({\omega }^{n+1}\right)\le L_{\beta }\left({\omega }^0\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)<+\infty .$

由于$\delta >0$ ，有：

${\displaystyle \sum _{k=0}^{\infty }{\Vert y^{k+1}-y^k\Vert }^2}<+\infty .$

其次，证明${\displaystyle \sum _{k=0}^{\infty }{\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2}<+\infty$ 。这显然来自于方程(18)。

最后，证明${\displaystyle \sum _{k=0}^{\infty }{\Vert x^{k+1}-x^k\Vert }^2}<+\infty$ 。回忆

${\lambda }^{k+1}={\lambda }^k-\beta \left(A{x}^{k+1}+\left|y^{k+1}\right|-b\right),{\lambda }^k={\lambda }^{k-1}-\beta \left(A{x}^k+\left|y^k\right|-b\right).$

那么

$\beta \left(A{x}^k-A{x}^{k+1}\right)=\left({\lambda }^{k+1}-{\lambda }^k\right)-\left({\lambda }^k-{\lambda }^{k-1}\right)-\beta \left(\left|y^k\right|-\left|y^{k+1}\right|\right).$

所以

$\begin{array}{c}{\Vert \beta \left(A{x}^k-A{x}^{k+1}\right)\Vert }^2={\Vert \left({\lambda }^{k+1}-{\lambda }^k\right)-\left({\lambda }^k-{\lambda }^{k-1}\right)-\beta \left(\left|y^k\right|-\left|y^{k+1}\right|\right)\Vert }^2\\ \le 3\left({\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\beta }^2{\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2\right)\\ =3\left({\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\beta }^2\sigma {\Vert y^k-y^{k+1}\Vert }^2\right).\end{array}$ (21)

根据${\left|A\right|}_2=\sqrt{{\lambda }_{\max }\left(A^{\text{T}}A\right)}$ ，有

${\Vert \beta \left(A{x}^k-A{x}^{k+1}\right)\Vert }^2={\beta }^2{\lambda }_{\max }{\Vert x^{k+1}-x^k\Vert }^2.$ (22)

然后，根据公式(21)和公式(22)，可以看出

${\displaystyle \sum _{k=0}^{\infty }{\Vert x^{k+1}-x^k\Vert }^2}<+\infty .$

因此，引理6的结果成立。

备注4：如果${ℒ}_{\beta }(\cdot )$ 于是有界的，那么容易推${\displaystyle \sum _{k=0}^{+\infty }{\Vert {\omega }^{k+1}-{\omega }^k\Vert }^2}<+\infty$ 而无需保证$\left\{{\omega }^k\right\}$ 的有界性。

引理7：设$\left\{{\omega }^k\right\}=\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是算法(5)生成的序列，且$\left\{{\omega }^k\right\}$ 是有界的。定义

$x_{k+1}^{*}=\beta A^{\text{T}}\left(\left|y^{k+1}\right|-\left|y^k\right|\right)+A^{\text{T}}\left({\lambda }^k-{\lambda }^{k+1}\right);y_{k+1}^{*}={\lambda }^k-{\lambda }^{k+1};{\lambda }_{k+1}^{*}=\frac{1}{\beta }\left({\lambda }^k-{\lambda }^{k+1}\right).$

则有

$\left(x_{k+1}^{*},y_{k+1}^{*},{\lambda }_{k+1}^{*}\right)\in \partial {ℒ}_{\beta }\left({\omega }^{k+1}\right).$

此外，存在$\zeta >0$ ，使得

$d\left(0,\partial {ℒ}_{\beta }\left({\omega }^{k+1}\right)\right)\le \zeta \Vert y^k-y^{k+1}\Vert .$

证明：根据增广拉格朗日函数${ℒ}_{\beta }(\cdot )$ ，我们可知

$\begin{array}{l}{\partial }_x{ℒ}_{\beta }\left({\omega }^{k+1}\right)=\partial f\left(x^{k+1}\right)-A^{\text{T}}{y}^{k+1}{\lambda }^{k+1}+\beta A^{\text{T}}{y}^{k+1}\left(x^{k+1}{}^{\text{T}}{A}^{\text{T}}{y}^{k+1}-b\right),\\ {\partial }_y{ℒ}_{\beta }\left({\omega }^{k+1}\right)=\nabla g\left(y^{k+1}\right)-x^{k+1}{}^{\text{T}}{A}^{\text{T}}{\lambda }^{k+1}+\beta \left(x^{k+1}{}^{\text{T}}{A}^{\text{T}}{y}^{k+1}-b\right),\\ {\partial }_{\lambda }{ℒ}_{\beta }\left({\omega }^{k+1}\right)=-\left(x^{k+1}{}^{\text{T}}{A}^{\text{T}}{y}^{k+1}-b\right).\end{array}$

下再结合(7)，可得

$\begin{array}{l}\beta A^{\text{T}}\left(\left|y^{k+1}\right|-\left|y^k\right|\right)+A^{\text{T}}\left({\lambda }^k-{\lambda }^{k+1}\right)\in {\partial }_x{ℒ}_{\beta }\left({\omega }^{k+1}\right);\\ \left({\lambda }^k-{\lambda }^{k+1}\right)\cdot \text{sign}\left(y^{k+1}\right)\in {\partial }_y{ℒ}_{\beta }\left({\omega }^{k+1}\right);\\ \frac{1}{\beta }\left({\lambda }^k-{\lambda }^{k+1}\right)\in {\partial }_{\lambda }{ℒ}_{\beta }\left({\omega }^{k+1}\right).\end{array}$

因此，根据引理1，我们可知$\left(x_{k+1}^{*},y_{k+1}^{*},{\lambda }_{k+1}^{*}\right)\in \partial {ℒ}_{\beta }\left({\omega }^{k+1}\right)$ 。除此之外，存在${\zeta }_1,{\zeta }_2>0$ 使得

$\Vert \left(x_{k+1}^{*},y_{k+1}^{*},{\lambda }_{k+1}^{*}\right)\Vert \le {\zeta }_1\sigma \Vert y^{k+1}-y^k\Vert +{\zeta }_2\Vert {\lambda }^{k+1}-{\lambda }^k\Vert .$

连通过定义$\zeta ={\zeta }_1\sigma +L{\zeta }_2$ ，再根据(18)可知

$d\left(0,\partial {ℒ}_{\beta }\left({\omega }^{k+1}\right)\right)\le \Vert \left(x_{k+1}^{*},y_{k+1}^{*},{\lambda }_{k+1}^{*}\right)\Vert \le \zeta \Vert y^k-y^{k+1}\Vert .$

这就完成了此引理的证明。

引理8：设$\left\{{\omega }^k\right\}=\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是算法(5)生成的序列，且$\left\{{\omega }^k\right\}$ 是有界的。令$S\left({\omega }^0\right)$ 表示其极限点的集合。那么：

(1) $\varnothing \ne S\left({\omega }^0\right)\subset crit{ℒ}_{\beta }$ ；

(2) ${ℒ}_{\beta }(\cdot )$ 在$S\left({\omega }^0\right)$ 上是有限的且为常数；

(3) $S\left({\omega }^0\right)$ 是一个非空连通的紧集，并且

$\underset{k\to \infty }{\lim }d\left({\omega }^k,S\left({\omega }^0\right)\right)=0.$

定理2：设$\left\{{\omega }^k\right\}=\left\{\left(x^k,y^k,{\lambda }^k\right)\right\}$ 是算法(5)生成的序列，且$\left\{{\omega }^k\right\}$ 是有界的。假设f和g是半代数函数，那么${\omega }^k$ 具有有限长度，即

${\displaystyle \sum _{k=0}^{+\infty }\Vert {\omega }^{k+1}-{\omega }^k\Vert }<+\infty$

因此，${\omega }^k$ 收敛到${ℒ}_{\beta }(\cdot )$ 的一个临界点。

证明：从引理8可知，对于所有${\omega }^{*}\in S\left({\omega }^0\right)$ ，有${ℒ}_{\beta }\left({\omega }^k\right)\to {ℒ}_{\beta }\left({\omega }^{*}\right)$ ，考虑两种情况：

(1) 如果存在一个整数$k_0$ ，使得${ℒ}_{\beta }\left({\omega }^{k_0}\right)={ℒ}_{\beta }\left({\omega }^{*}\right)$ 。根据方程(8)以及备注3，对于任意$k>k_0$ ，有

$\delta {\Vert y^{k+1}-y^k\Vert }^2\le L_{\beta }\left({\omega }^k\right)-L_{\beta }\left({\omega }^{k+1}\right)\le L_{\beta }\left({\omega }^{k_0}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)=0$ 。

对于任意$k>k_0$ ，有$y^{k+1}=y^k$ 。结合引理5的证明，对于任意$k>k_0+1$ ，有${\omega }^{k+1}={\omega }^k$ ，因此定理2成立。

(2) 假设对于所有k都有${ℒ}_{\beta }\left({\omega }^k\right)>{ℒ}_{\beta }\left({\omega }^{*}\right)$ 。由于$d\left({\omega }^k,S\left({\omega }^0\right)\right)\to 0$ ，对于任意$\epsilon >0$ ，存在$k_1>0$ ，使得对于任何$k>k_1$ ，有$d\left({\omega }^k,S\left({\omega }^0\right)\right)<\epsilon$ 。再次，由于${ℒ}_{\beta }\left({\omega }^k\right)\to {ℒ}_{\beta }\left({\omega }^{*}\right)$ ，对于任意$\eta >0$ ，存在$k_2>0$ ，使得对于任意$k>k_2$ ，有${ℒ}_{\beta }\left({\omega }^k\right)<{ℒ}_{\beta }\left({\omega }^{*}\right)+\eta$ 。因此，对于所有$\epsilon ,\eta >0$ ，当$k>\tilde{k}=\max \left\{k_1,k_2\right\}$ 时，

$d\left({\omega }^k,S\left({\omega }^0\right)\right)<\epsilon ,{ℒ}_{\beta }\left({\omega }^{*}\right)<{ℒ}_{\beta }\left({\omega }^k\right)<{ℒ}_{\beta }\left({\omega }^{*}\right)+\eta$ ，

由于$S\left({\omega }^0\right)$ 是一个非空紧集，并且${ℒ}_{\beta }(\cdot )$ 在$S\left({\omega }^0\right)$ 上是常数，应用定义4中$\Omega =S\left({\omega }^0\right)$ ，推导出对于任意$k>\tilde{k}$ ，有

${\phi }^{\prime }\left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)d\left(0,\partial {ℒ}_{\beta }\left({\omega }^k\right)\right)\ge 1$ .

由于

${ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{k+1}\right)=\left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)-\left({ℒ}_{\beta }\left({\omega }^{k+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right).$

根据$\phi$ 的凹性，可得

$\phi \left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)-\phi \left({ℒ}_{\beta }\left({\omega }^{k+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)\ge {\phi }^{\prime }\left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)\left({ℒ}_{\beta }\left({\omega }^{k+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right).$

关联$d\left(0,\partial {ℒ}_{\beta }\left({\omega }^k\right)\right)\le \zeta \Vert y^k-y^{k-1}\Vert ,{\phi }^{\prime }\left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)>0$ ，得到

$\begin{array}{c}{ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{k+1}\right)\le \frac{\phi \left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)-\phi \left({ℒ}_{\beta }\left({\omega }^{k+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)}{\phi \left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)}\\ \le \zeta \Vert y^k-y^{k-1}\Vert \left[\phi \left({ℒ}_{\beta }\left({\omega }^k\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)-\phi \left({ℒ}_{\beta }\left({\omega }^{k+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)\right].\end{array}$ (23)

设

${\Delta }_{p,q}=\phi \left({ℒ}_{\beta }\left({\omega }^p\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)-\phi \left({ℒ}_{\beta }\left({\omega }^q\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)$ 。

结合引理3和不等式(23)，得到对于所有$k>\tilde{k}$ ，

$\Vert y^{k+1}-y^k\Vert \le \sqrt{\frac{\zeta }{\delta }{\Delta }_{k,k+1}\Vert y^k-y^{k-1}\Vert }\le \frac{1}{2}\left(\Vert y^k-y^{k-1}\Vert +\frac{\zeta }{\delta }{\Delta }_{k,k+1}\right).$ (24)

从方程(24)可以得出

${\displaystyle \sum _{k=\tilde{k}+1}^m\Vert y^{k+1}-y^k\Vert }\le \frac{1}{2}\left({\displaystyle \sum _{k=\tilde{k}+1}^m\Vert y^k-y^{k-1}\Vert }+\frac{\zeta }{\delta }{\Delta }_{\tilde{k}+1,m+1}\right).$ (25)

注意到$\phi \left({ℒ}_{\beta }\left({\omega }^{m+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right)>0$ ，重写(25)，并令$m\to +\infty$ ，有

${\displaystyle \sum _{k=\tilde{k}+1}^{+\infty }\Vert y^{k+1}-y^k\Vert }\le \Vert y^{\tilde{k}+1}-y^{\tilde{k}+1}\Vert +\frac{\zeta }{\delta }\phi \left({ℒ}_{\beta }\left({\omega }^{\tilde{k}+1}\right)-{ℒ}_{\beta }\left({\omega }^{*}\right)\right).$ (26)

这意味着

${\displaystyle \sum _{k=0}^{+\infty }\Vert y^{k+1}-y^k\Vert }<+\infty$ 。

从方程(18)，知道

${\displaystyle \sum _{k=0}^{+\infty }\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }<+\infty$ 。

另一方面，从方程(21)和方程(22)可以得出

$\begin{array}{c}\Vert x^{k+1}-x^k\Vert \le \sqrt{\frac{3}{{\beta }^2{\lambda }_{\max }\left(A^{\text{T}}A\right)}}{\left({\Vert {\lambda }^{k+1}-{\lambda }^k\Vert }^2+{\Vert {\lambda }^k-{\lambda }^{k-1}\Vert }^2+{\beta }^2{\Vert \left|y^k\right|-\left|y^{k+1}\right|\Vert }^2\right)}^{1/2}\\ \le \sqrt{\frac{3}{{\beta }^2{\lambda }_{\max }\left(A^{\text{T}}A\right)}}\left(\Vert {\lambda }^{k+1}-{\lambda }^k\Vert +\Vert {\lambda }^k-{\lambda }^{k-1}\Vert +\beta \sqrt{\sigma }\Vert y^k-y^{k+1}\Vert \right).\end{array}$

且$\left\{{\omega }^k\right\}$ 是一个柯西序列(参见Botel等[18]的第482页的一个简单证明)。因此，根据备注3可知它是收敛的。

4. 数值实验分析

例1：二次规划(Quadratic Programming, QP)问题：二次规划(QP)是一个数学优化问题，其目标是求解满足一组线性或不等式约束的二次函数的最小值或最大值。在优化问题中，QP问题是一个非常重要的问题，因为它广泛应用于金融、工程、计算机视觉、机器学习等领域。QP问题的约束通常是线性约束，将其扩展到非线性约束问题，并通过以下例子来说明

$\begin{array}{l}\min {\left(x-1\right)}^2+{\left(y-3\right)}^2\\ \text{s}\text{.t}\text{.}2x+\left|y\right|-4=0\\ -7\le x\le 5,-8\le y\le 1.\end{array}$

上述问题的增广拉格朗日函数为

${ℒ}_{\beta }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-\langle \lambda ,2x+\left|y\right|-4\rangle +\frac{\beta }{2}{\Vert 2x+\left|y\right|-4\Vert }^2.$

在此实验中，每个问题的子问题根据(5)进行求解。然后，列出了(5)的每次迭代过程中的子x问题和y子问题：

x子问题为

$x^{k+1}=\frac{2\left[{\lambda }^k-\beta \left(2\left|y^k\right|-4\right)\right]+2}{2+4\beta }.$

y子问题为

$y^{k+1}=\frac{\text{sign}\left(y^k\right)\left[{\lambda }^k-\beta \left(2x^{k+1}-4\right)\right]+6}{2+\beta }.$

(a) β = 0.5 (b) β = 1

Figure 1. The relationship between function value and the number of iterations

图1. 函数值与迭代次数的关系

Table 1. Iteration results with different initial values

表1. 不同初始值下的迭代结果

x	1	−2	−5	7
y	1	−2	−5	−1
(x^*, y^*)	(1.5, 1.0)	(1.5, 1.0)	(1.5, 1.0)	(1.5, 1.0)
β	1	1	1	1
IT	49	48	47	48
CPU	5.691	6.238	6.274	5.346
β	0.5	0.5	0.5	0.5
IT	49	48	47	48
CPU	5.657	5.561	6.120	4.367

在计算中，令${ℒ}_{\beta }\left(x,y,\lambda \right)$ 中的$\lambda =1.75$ ，分别测试了四组$\left(x,y\right)$ 的初始值：S1：$\left(x,y\right)=\left(1,1\right)$ ；S2：$\left(x,y\right)=\left(-2,-2\right)$ ；S3：$\left(x,y\right)=\left(-5,-5\right)$ ；S4：$\left(x,y\right)=\left(7,-1\right)$ ，分别取$\beta =0.5$ 和$\beta =1$ 。在这种情况下，图1和表1中显示了一些数值结果。从图1中可以看出，随着迭代次数的增加，函数值逐渐减少，最终达到平稳状态。通过表1可以看出，不同初始值达到最优解的迭代次数是不同的。在x和y的定义域下，发现$\beta$ 的变化不会影响最优解的变化，且最优解都是$\left(x^{*},y^{*}\right)=\left(1.5,1.0\right)$ 。不出所料，随着参数$\beta$ 的增加，CPU时间变长。

例2：矩阵$A\in R^{n\times n}$ ，向量$b\in R^n$ 。考虑问题(2)具体的函数形式为$f\left(x\right)={\Vert x-1\Vert }^2,g\left(y\right)={\Vert y-1\Vert }^2$ ，即

$\begin{array}{l}\min {\Vert x-1\Vert }^2+{\Vert y-1\Vert }^2,\\ \text{s}\text{.t}.Ax+\left|y\right|-b=0,\end{array}$ (27)

且

$A=\left[a_{ij}\right]=\{\begin{array}{cc}10,& i=j.\\ -7,& j-i=1.\\ 2,& i-j=1.\end{array}i,j=\left(1,2,\cdots ,n\right),b={\left(0,0,\cdots ,0,0\right)}^{\top }.$

上述问题的增广拉格朗日函数为

${ℒ}_{\beta }\left(x,y,\lambda \right)={\Vert x-1\Vert }^2+{\Vert y-1\Vert }^2-\langle \lambda ,Ax+\left|y\right|-b\rangle +\frac{\beta }{2}{\Vert Ax+\left|y\right|-b\Vert }^2.$

在此实验中，每个问题的子问题根据(5)进行求解。在求解过程中，我们引入变量$z=\left|y\right|$ ，则问题(27)可改写为

$\min \left\{{\Vert x-1\Vert }^2+{\Vert y-1\Vert }^2|Ax+z-b=0,z=\left|y\right|\right\}$ .

对应的子问题为：

x子问题为

$x^{k+1}={\left(A^{\top }A+\beta I\right)}^{-1}\left(A^{\top }\left(b-z^k\right)+{\lambda }^k\right).$

y子问题为

$y^{k+1}=\text{sign}\left(y^k\right)\cdot \max \left(\left|z^k\right|-\frac{1}{\beta },0\right).$

z相当于约束投影，其子问题为

$z^{k+1}=y^{k+1}+\left(b+A{x}^{k+1}\right).$

(a) n = 1000 (b) n = 10,000

Figure 2. The relationship between $\left(h\left(w^k\right)-h^{*}\right)/h^{*}$ and the number of iterations

图2. $\left(h\left(w^k\right)-h^{*}\right)/h^{*}$ 与迭代次数的关系

在实验中，设定$\beta =1$ ，初始向量为：$x_0={\left(1,1,\cdots ,1,1\right)}^{\top },y_0={\left(1,1,\cdots ,1,1\right)}^{\top },{\lambda }_0={\left(1,1,\cdots ,1,1\right)}^{\top }$ 。在这种情况下，我们在图2中展示了当n = 1000和n = 10,000时的数值结果。很容易发现，当n = 1000时，在迭代562次后得到最优解，而当n = 10,000时，在迭代565次后得到最优解。虽然维数增加迭代次数也增多，但维数的变化对达到最优解的迭代次数变化的影响不是很显著。通过图2，我们可以看到横坐标和纵坐标反映了迭代次数与$\left(h\left(w^k\right)-h^{*}\right)/h^{*}$ 的关系($h^{*}$ 代表函数的最优解)。随着迭代次数的增加,$\left(h\left(w^k\right)-h^{*}\right)/h^{*}$ 的值是递减的，并最终保持为平稳状态。这就表明$h\left(w^k\right)$ 是非递增的，并最终收敛到$h^{*}$ 。

5. 结论

本文通过使用KL不等式，研究了带有绝对值形式非线性约束的最小化问题的ADMM，并证明了ADMM生成的迭代子序列收敛到问题的一个关键点。更重要的是，通过数值例子，进一步验证了本文设计的ADMM在带有绝对值形式的非线性约束的最小化问题中是实用的。值得注意的是，文章仅考虑了这种情况下y的每个元素都非零的情况，而包含零元素的y的另一种情况则有待进一步研究。

基金项目

云南师范大学研究生科研训练基金项目(YJSJJ23-B69)。

NOTES

^*第一作者。

^#通讯作者。