Convergence Analysis of Multiblock Inertial ADMM for Nonconvex Consensus Problem

Abstract

The alternating direction method of multipliers (ADMM) is one of the most powerful and successful methods for solving various nonconvex consensus problem. The convergence of the conventional ADMM (i.e., 2-block) for convex objective functions has been stated for a long time. As an accelerated technique, the inertial effect was used by many authors to solve 2-block convex optimization problem. This paper combines the ADMM and the inertial effect to construct an inertial alternating direction method of multipliers (IADMM) to solve the multiblock nonconvex consensus problem and shows the convergence under some suitable conditions. Simulation experiment verifies the effectiveness and feasibility of the proposed method.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The nonconvex global consensus problem with regularization [1] has the following form:$$\begin{array}{c}\text{(1)}& \min {\displaystyle \sum }_{i=1}^N{f}_{i}x+gx\mathrm{s}.\mathrm{t}.x\in X\text{,}\end{array}$$where $f_i:R^n⟶R\cup +\infty ,i=1,2,\cdots ,N$ are smooth, possibly nonconvex functions, while $g:R^n⟶R$ is a convex nonsmooth regularization term and X is a closed convex set. This problem is related to the convex global consensus problem discussed heavily [2], but it is possible that $f_i{}^{\prime }$s are nonconvex.

In many practical applications, $f_i{}^{\prime }$s need to be handled by a single agent, such as a thread or a processor. Now, we transform problem (1) into the following equivalent linearly constrained problem under the help of new variables ${x_i}_{i=0}^N$:$$\begin{array}{c}\text{(2)}& \min {\displaystyle \sum }_{i=1}^N{f}_i{x}_i+g{x}_0\mathrm{s}.\mathrm{t}.x_i=x_0\forall i=\mathrm{1,2},\cdots ,N,x_0\in X\text{.}\end{array}$$

Note that the problem (2) owns $N$ blocks with different variables $x_1,\dots ,x_N$ and one globe variable. Then, each distributed agent can handle a single local variable $x_i$ and a local function $f_i$, respectively.

The augmented Lagrangian function with multipliers $y_i\in R^n,i=1,2,\cdots ,N$ of problem (2) is defined as follows:$$\begin{array}{}\text{(3)}& L_{\rho }{x}_i,x_0,y={\displaystyle \sum }_{i=1}^N{f}_i{x}_i+g{x}_0+{\displaystyle \sum }_{i=1}^N{y}_i,x_i-x_0+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i-x_0}^2\text{,}\end{array}$$where $\rho >0$ is a penalty parameter and problem (2) can be solved distributively by the following classical ADMM procedure:$$\begin{array}{}\text{(4)}& \begin{array}{c}{x}_0^{k+1}=\underset{x_0\in X}{\mathrm{argmin}}{L}_{\rho }{x}_i^k,x_0,y^k\text{,}\\ x_i^{k+1}=\underset{x_i}{\mathrm{argmin}}{f}_i{x}_i+y_i^k,x_i-x_0^{k+1}+\frac{\rho }{2}{x_i-x_0^{k+1}}^2\text{,}\\ y_i^{k+1}=y_i^k+\rho x_i^{k+1}-x_0^{k+1}\text{,}\\ i=\mathrm{1,2},\cdots ,N\text{.}\end{array}\end{array}$$

ADMM was initially introduced in the 1970s [3, 4], and its convergence properties for convex case have been extensively studied. However, ADMM or its directly extended version may not converge when there is a nonconvex function in the objective. Yang et al. [5] studied the convergence of the ADMM for the nonconvex optimization model which come from the background/foreground extraction. Hong et al. [6] analyzed the convergence of alternating direction method of multipliers for a family of nonconvex problems. Guo et al. [7] studied the convergence of ADMM for multiblock nonconvex separable optimization models.

Recently, some scholars studied the inertial type of ADMM for convex optimization. For example, Chen et al. [8] analyzed a class of inertial ADMM for linearly constrained separable convex optimization, and Moudafi and Elissabeth [9] extended the inertial technique to solve the maximal monotone operator inclusion problem. The research interests for the nonconvex cases are increasing in recent years; e.g., Chao et al. [10] proposed and analyzed an inertial proximal ADMM for a class of nonconvex optimization problems while all the above inertial ADMM algorithms were presented for solving only two-block optimization problem (not for multiple-block case). Whether the convergence of the inertial ADMM is assured when the involved number of blocks is more than two? It is an important problem to research.

The purpose of the present study is to examine the convergence of inertial ADMM with multiblocks for nonconvex consensus problem under the assumption that the potential function satisfies the Kurdyka–Lojasiewicz property. The preliminary numerical results show the effectiveness of the proposed algorithm.

The rest of this paper is organized as follows. In Section 2, some necessary preliminaries for further analysis are summarized. Section 3 proposes a multiblock nonconvex inertial ADMM algorithm and analyzes its convergence under some conditions. In Section 4, we prove the validity of the algorithm by the numerical experiment. Finally, some conclusions are drawn in Section 5.

2. Preliminaries

Let $R^n$ denote the n-dimensional Euclidean space, $R\cup +\infty$ denote the extended real number set, and N denote the natural number set. $.$ represents the Euclidean norm. Let $\text{dom}f:=x\in R^n:fx<+\infty$ denote the domain of function $f:R^n⟶R\cup \infty$ and $x,y={\sum }_{i=1}^n{x}_i{y}_i$ denote the inner product. For function if $f$ if $f\overline{x}\le {\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}_{x⟶\overline{x}}fx\text{,}$ we say that $f$ is lower semicontinuous at $\overline{x}$. If $f$ is lower semicontinuous at every point $x\in R^n$, we say that $f$ is lower semicontinuous function.

For a set $S\subset R^n$ and a point $x\in R^n$, let $dx,S=\underset{y\in S}{\inf }{y-x}^2$. If $S=\varnothing$, we set $dx,S=+\infty$ for all $x\in R^n$.

The Lagrangian function of (2), with multiplier $y={y_1,y_2,\cdots ,y_N}^T$, is defined as$$\begin{array}{}\text{(5)}& L{x}_i,x_0,y={\displaystyle \sum }_{i=1}^N{f}_i{x}_i+g{\mathrm{x}}_0+{\displaystyle \sum }_{i=1}^N{y}_i,x_i-x_0\text{.}\end{array}$$

Definition 1.

If $w^{\ast }={x_i^{\ast },x_0^{\ast },y^{\ast }}^{\mathrm{{\rm T}}}$ such that$$\begin{array}{}\text{(6)}& \begin{array}{c}{\nabla }_{x_i}{f}_i{x}_i^{\ast }=-y_i^{\ast }\text{,}\\ {\displaystyle \sum }_{i=1}^N{y}_i^{\ast }\in \partial g{x}^{\ast }\text{,}\\ x_i^{\ast }-x_0^{\ast }=0\text{,}\end{array}\end{array}$$then $w^{\ast }$ is called a critical point or stationary point of the Lagrange function $L{x}_i,x_0,y$.

A very important technique to prove the convergence of the ADMM for nonconvex optimization problems relies on the assumption that the potential function satisfying the following Kurdyka–Lojasiewicz property (KL property) [11–14].

For notational simplicity, we use ${\mathrm{\Psi }}_{{\epsilon }_2}{\epsilon }_2>0$ to denote the set of concave functions $\varphi :0,{\epsilon }_2⟶0,+\infty$ such that

(i) $\varphi 0=0$, $\varphi$ is continuous differentiable on $0,{\epsilon }_2$ and continuous at $0$

(ii) ${\varphi }^{\prime }s>0,\forall s\in 0,{\epsilon }_2$

Definition 2.

(see [14]) (KL property). Let $f:{\mathbb{R}}^n⟶{\mathbb{R}}^n\cup +\infty$ be a proper lower semicontinuous function. If there exists ${\epsilon }_2\in 0,+\infty$, a neighborhood $U$ of $x^{\ast }$, and a function $\varphi \in {\mathrm{\Psi }}_{{\epsilon }_2}$, such that for all $x\in U\cap f{x}^{\ast }<f<f{x}^{\ast }+{\epsilon }_2$, it holds that$$\begin{array}{}\text{(7)}& \varphi \prime fx-f{x}^{\ast }d0,\partial fx\ge 1,\end{array}$$then $f$ is said to have the KL property at $x^{\ast }$.

3. Algorithm and Convergence Analysis

For convenience, we fix the following notations: $w^k={x_i^k,y^k,x_0^k}^{\mathrm{{\rm T}}}$, ${\widehat{w}}^k={x_i^k,y^k,x_0^k,x_i^{k-1},y^{k-1},x_0^{k-1}}^{\mathrm{{\rm T}}}$. Basis on (4), we propose the following algorithm for solving problem (2).

Algorithm 1.

Inertial ADMM (IADMM). Choose $x_0^0\in R^n,y_i^0\in R^n,x_i^0\in R^n,i=\mathrm{1,2},\cdots ,N,{\tau }_k>0,\rho >0$ and ${\theta }_k\in \mathrm{0,1}$, $\forall k\ge 1\text{.}$ For the given point $w^k={x_i^k,y^k,x_0^k}^{\mathrm{{\rm T}}}$, consider the iterative scheme:$$\begin{array}{}\text{(8)}& \begin{array}{c}{x}_0^{k+1}=\underset{x_0\in X}{\mathrm{argmin}}g{x}_0+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^k-x_0+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0}^2+\frac{{\tau }_k}{2}{x_0-z_0^k}^2\mathrm{a}\text{,}\\ x_i^{k+1}=\underset{x_i}{\mathrm{argmin}}{f}_i{x}_i+y_i^k,x_i-x_0^{k+1}+\frac{\rho }{2}{x_i-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{x_i-z_i^k}^2\mathrm{b}\text{,}\\ y_i^{k+1}=y_i^k+\rho x_i^{k+1}-x_0^{k+1}+{\tau }_k{x}_i^{k+1}-z_i^k\mathrm{c}\text{,}\end{array}\end{array}$$where$$\begin{array}{}\text{(9)}& \begin{array}{c}{z}_0^k=x_0^k+{\theta }_k{x}_0^k-x_0^{k-1}\text{,}\\ z_i^k=x_i^k+{\theta }_k{x}_i^k-x_i^{k-1}\text{,}\end{array}\end{array}$$associated with $i=\mathrm{1,2},\cdots ,N$.

From the optimality conditions of (8) (a) and (8) (b), we have$$\begin{array}{c}\text{(10)}& 0\in \partial g{x}_0^{k+1}-{\displaystyle \sum }_{i=1}^N{y}_i^k-\rho {\displaystyle \sum }_{i=1}^N{x}_i^k-x_0^{k+1}+{\tau }_k{x}_0^{k+1}-z_0^k\text{,}\text{(11)}& 0={\nabla }_{x_i}{f}_i{x}_i^{k+1}+y_i^k+\rho x_i^{k+1}-x_0^{k+1}+{\tau }_k{x}_i^{k+1}-z_i^k\text{,}i=\mathrm{1,2},\cdots ,N\text{.}\end{array}$$

Remark 1.

Compared with the inertial ADMM in [10], each subproblem in our algorithm has the inertial term, and we handle multiblock case here.

Subsequently, we will discuss the convergence of Algorithm 1 under the following assumptions.

Assumption 1.

(i) $gx$ is proper lower semicontinuous, and ${\nabla }_{x_i}{f}_i{x}_i$ is $l_{f_i}$ Lipschitz continuous; i.e.,$$\begin{array}{}\text{(12)}& {\nabla }_{x_i}{f}_i{x}_i^{k+1}-{\nabla }_{x_i}{f}_i{x}_i^k\le l_{f_i}{x}_i^{k+1}-x_i^k\text{.}\end{array}$$

(ii) $\rho$ is large enough, such that $0\le {\theta }_k<\rho -l_f^2/2\rho +2,{\tau }_k>2l_f^2/\rho -2\rho {\theta }_k-l_f^2-2{\theta }_k$.

Lemma 1.

For each $k\in \mathrm{{\rm N}}$, define $l_f=\max {l_{f_i}}_{i=\mathrm{1,2},\cdots ,N}$, we have$$\begin{array}{}\text{(13)}& {y_i^{k+1}-y_i^k}^2\le l_{f_i}^2{x_i^{k+1}-x_i^k}^2\le l_f^2{x_i^{k+1}-x_i^k}^2\text{.}\end{array}$$

Proof.

Since $y_i^{k+1}=y_i^k+\rho x_i^{k+1}-x_0^{k+1}+{\tau }_k{x}_i^{k+1}-z_i^k\text{,}$ from (11), one has$$\begin{array}{}\text{(14)}& y_i^{k+1}=-{\nabla }_{x_i}{f}_i{x}_i^{k+1}\text{.}\end{array}$$

Thus,$$\begin{array}{c}\text{(15)}& {y_i^{k+1}-y_i^k}^2={{\nabla }_{x_i}{f}_i{x}_i^{k+1}-{\nabla }_{x_i}{f}_i{x}_i^k}^2\le l_{f_i}^2{x_i^{k+1}-x_i^k}^2\\ \le l_f^2{x_i^{k+1}-x_i^k}^2\text{.}\end{array}$$

Hence, the result is obtained.

Lemma 2.

Select $\rho$ large enough, suppose that Assumption 1 holds. Then, for each $k\in \mathrm{{\rm N}}$,$$\begin{array}{c}\text{(16)}& L_{\rho }{w}^{k+1}+{\displaystyle \sum }_{i=1}^N{\gamma }_1{x_i^{k+1}-x_i^k}^2+{\gamma }_1{x_0^{k+1}-x_0^k}^2\le L_{\rho }{w}^k+{\displaystyle \sum }_{i=1}^N{\gamma }_2{x_i^k-x_i^{k-1}}^2+{\gamma }_2{x_0^k-x_0^{k-1}}^2\text{,}\end{array}$$where ${\gamma }_1={\tau }_k/21-{\theta }_k-1/\rho +{\tau }_k/2\rho l_f^2-{\tau }_k/2\rho \text{\hspace{0.17em}and}{\gamma }_2={\tau }_k{\theta }_k/2+{\tau }_k{\theta }_k/\rho$.

Proof.

By the definition of the augmented Lagrangian function, (8) (c) and (15), we have$$\begin{array}{c}\text{(17)}& L_{\rho }{x}_i^{k+1},x_0^{k+1},y^{k+1}-L_{\rho }{x}_i^{k+1},x_0^{k+1},y^k\text{,}={\displaystyle \sum }_{i=1}^N{y}_i^{k+1}-y_i^k,x_i^{k+1}-x_0^{k+1}\text{,}\\ =\frac{1}{\rho }{\displaystyle \sum }_{i=1}^N{y}_i^{k+1}-y_i^k,y_i^{k+1}-y_i^k-{\tau }_k{x}_i^{k+1}-z_i^k\\ \le \frac{1}{\rho }+\frac{{\tau }_k}{2\rho }{\displaystyle \sum }_{i=1}^N{y_i^{k+1}-y_i^k}^2+\frac{{\tau }_k}{2\rho }{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\\ \le \frac{1}{\rho }+\frac{{\tau }_k}{2\rho }{l}_f^2{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+\frac{{\tau }_k}{2\rho }{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\text{.}\end{array}$$

From (8) (a) and (8) (b), we obtain$$\begin{array}{c}\text{(18)}& g{x}_0^{k+1}+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^k-x_0^{k+1}+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{x_0^{k+1}-z_0^k}^2\le g{x}_0^k+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^k-x_0^k+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^k}^2+\frac{{\tau }_k}{2}{x_0^k-z_0^k}^2,\text{and}\\ {\displaystyle \sum }_{i=1}^N{f}_i{x}_i^{k+1}+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^{k+1}-x_0^{k+1}+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\\ \le {\displaystyle \sum }_{i=1}^N{f}_i{x}_i^k+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^k-x_0^{k+1}+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^k-z_i^k}^2\text{,}\end{array}$$respectively. Then, it is easy to get$$\begin{array}{c}\text{(19)}& g{x}_0^{k+1}-g{x}_0^k+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_0^k-x_0^{k+1}-\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^k}^2\le \frac{{\tau }_k}{2}{x_0^k-z_0^k}^2-\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^{k+1}}^2-\frac{{\tau }_k}{2}{x_0^{k+1}-z_0^k}^2,\text{and}\\ {\displaystyle \sum }_{i=1}^N{f}_i{x}_i^{k+1}-{\displaystyle \sum }_{i=1}^N{f}_i{x}_i^k+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^{k+1}-x_i^k+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_0^{k+1}}^2\\ \le \frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^k-z_i^k}^2-\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\text{.}\end{array}$$

Therefore, we have$$\begin{array}{c}\text{(20)}& L_{\rho }{x}_i^{k+1},x_0^{k+1},y^k-L_{\rho }{x}_i^k,x_0^k,y^k=L_{\rho }{x}_i^{k+1},x_0^{k+1},y^k-L_{\rho }{x}_i^k,x_0^{k+1},y^k+L_{\rho }{x}_i^k,x_0^{k+1},y^k-L_{\rho }{x}_i^k,x_0^k,y^k\\ ={\displaystyle \sum }_{i=1}^N{f}_i{x}_i^{k+1}-{\displaystyle \sum }_{i=1}^N{f}_i{x}_i^k+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^{k+1}-x_i^k+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_0^{k+1}}^2\\ +g{x}_0^{k+1}-g{x}_0^k-\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^k}^2+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_0^k-x_0^{k+1}\\ \le \frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^k-z_i^k}^2-\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\\ +g{x}_0^{k+1}-g{x}_0^k-\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0^k}^2+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_0^k-x_0^{k+1}\\ \le \frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^k-z_i^k}^2-\frac{{\tau }_k}{2}{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2+\frac{{\tau }_k}{2}{x_0^k-z_0^k}^2-\frac{{\tau }_k}{2}{x_0^{k+1}-z_0^k}^2\\ \le -\frac{{\tau }_k}{2}1-{\theta }_k{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+\frac{{\tau }_k}{2}{\theta }_k{\displaystyle \sum }_{i=1}^N{x_i^k-x_i^{k-1}}^2-\frac{{\tau }_k}{2}1-{\theta }_k{x_0^{k+1}-x_0^k}^2\\ +\frac{{\tau }_k}{2}{\theta }_k{x_0^k-x_0^{k-1}}^2\text{.}\end{array}$$

Adding up (17) and (20), by the Assumption 1 (ii), we have$$\begin{array}{c}\text{(21)}& L_{\rho }{w}^{k+1}\le L_{\rho }{w}^k-\frac{{\tau }_k}{2}1-{\theta }_k{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+\frac{{\tau }_k}{2}{\theta }_k{\displaystyle \sum }_{i=1}^N{x_i^k-x_i^{k-1}}^2-\frac{{\tau }_k}{2}1-{\theta }_k{x_0^{k+1}-x_0^k}^2+\frac{{\tau }_k}{2}{\theta }_k{x_0^k-x_0^{k-1}}^2+\frac{1}{\rho }+\frac{{\tau }_k}{2\rho }{\displaystyle \sum }_{i=1}^N{y_i^{k+1}-y_i^k}^2+\frac{{\tau }_k}{2\rho }{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-z_i^k}^2\\ \le L_{\rho }{w}^k-\frac{{\tau }_k}{2}1-{\theta }_k-\frac{1}{\rho }+\frac{{\tau }_k}{2\rho }{l}_f^2-\frac{{\tau }_k}{\rho }{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+\frac{{\tau }_k{\theta }_k}{2}+\frac{{\tau }_k{\theta }_k}{\rho }{\displaystyle \sum }_{i=1}^N{x_i^k-x_i^{k-1}}^2\\ -\frac{{\tau }_k}{2}1-{\theta }_k{x_0^{k+1}-x_0^k}^2+\frac{{\tau }_k}{2}{\theta }_k{x_0^k-x_0^{k-1}}^2\text{,}\end{array}$$which implies that$$\begin{array}{c}\text{(22)}& L_{\rho }{w}^{k+1}+{\displaystyle \sum }_{i=1}^N{\gamma }_1{x_i^{k+1}-x_i^k}^2+{\gamma }_1{x_0^{k+1}-x_0^k}^2\le L_{\rho }{w}^k+{\displaystyle \sum }_{i=1}^N{\gamma }_2{x_i^k-x_i^{k-1}}^2+{\gamma }_2{x_0^k-x_0^{k-1}}^2\text{.}\end{array}$$

Then, the results are obtained.

Remark 2.

From Assumption 1 (ii), we know that ${\gamma }_1>{\gamma }_2$. Define the following potential regularized augmented Lagrangian function:$$\begin{array}{}\text{(23)}& {\widehat{L}}_{\rho }{x}_i,x_0,y,{\widehat{x}}_i,{\widehat{x}}_0=L_{\rho }{x}_i,x_0,y+{\displaystyle \sum }_{i=1}^N{\gamma }_2{x_i-{\widehat{x}}_i}^2+{\gamma }_2{x_0-{\widehat{x}}_0}^2\text{,}\end{array}$$where $\widehat{w}=x_i,x_0,y,{\widehat{x}}_i,{\widehat{x}}_0\text{.}$

If we take $\eta ={\gamma }_1-{\gamma }_2>0,{\widehat{w}}^k=x_i^k,x_0^k,y^k,x_i^{k-1},x_0^{k-1}\text{,}$ then$$\begin{array}{}\text{(24)}& {\widehat{L}}_{\rho }{\widehat{w}}^k=L_{\rho }{w}^k+{\displaystyle \sum }_{i=1}^N{\gamma }_2{x_i^k-x_i^{k-1}}^2+{\gamma }_2{x_0^k-x_0^{k-1}}^2\text{.}\end{array}$$

From Lemma 2, we have$$\begin{array}{}\text{(25)}& {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}+{\displaystyle \sum }_{i=1}^N\eta {x_i^{k+1}-x_i^k}^2+\eta {x_0^{k+1}-x_0^k}^2\le {\widehat{L}}_{\rho }{\widehat{w}}^k\text{,}\end{array}$$which implies that the whole sequence ${{\widehat{L}}_{\rho }{\widehat{w}}^k}_{k\ge 1}$ is monotonically nonincreasing. It is importance for our convergence analysis.

Lemma 3.

If the sequence $w^k={x_i^k,x_0^k,y^k}^T$ is bounded, then ${\sum }_{k=0}^{+\infty }{w^{k+1}-w^k}^2<+\infty$.

Proof.

Since the sequence $w^k$ is bounded, there exists a subsequence ${\widehat{w}}^{k_j}$ such that $\lim {}_{j⟶+\infty }{{\widehat{w}}^{k_j}}^{j⟶+\infty }={\widehat{w}}^{\ast }$. Since $gx$ is lower semicontinuous, $f_i:R^n⟶R\cup +\infty$ is Lipschitz differentiable, and the function ${\widehat{L}}_{\rho }\cdot$ is lower semicontinuous, which leads to ${\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}_{j⟶+\infty }{\widehat{L}}_{\rho }{\widehat{w}}^{k_j}\ge {\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$; thus, ${\widehat{L}}_{\rho }{\widehat{w}}^{k_j}$ is bounded from below. From Lemma 2, we know that ${\widehat{L}}_{\rho }{\widehat{w}}^k$ is nonincreasing; thus, ${\widehat{L}}_{\rho }{\widehat{w}}^{k_j}$ is convergent and ${\widehat{L}}_{\rho }{\widehat{w}}^k\ge {\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$ for each k.

From Lemma 2, it yields$$\begin{array}{}\text{(26)}& \eta {\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2\le {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\text{.}\end{array}$$

Hence,$$\begin{array}{}\text{(27)}& {\displaystyle \sum }_{k=1}^t\eta {\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2\le {\widehat{L}}_{\rho }{\widehat{w}}^1-{\widehat{L}}_{\rho }{\widehat{w}}^{t+1}\le {\widehat{L}}_{\rho }{\widehat{w}}^1-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{.}\end{array}$$

Consequently, ${\sum }_{k=0}^{+\infty }{w^{k+1}-w^k}^2<+\infty$.

Lemma 4.

There exists $\delta >0$ such that $d0,\partial {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\le \delta {\beta }_k$ for each $k\in \mathrm{{\rm N}}$, where$$\begin{array}{}\text{(28)}& {\beta }_k={\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k+{\displaystyle \sum }_{i=1}^N{x}_i^k-x_i^{k-1}+x_0^k-x_0^{k-1}\text{.}\end{array}$$

Proof.

From the definition of ${\widehat{L}}_{\rho }\widehat{w}$, we have$$\begin{array}{}\text{(29)}& \begin{array}{c}{\partial }_{x_i}{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}={\nabla }_{x_i}{f}_i{x}_i^{k+1}+y_i^{k+1}+\rho x_i^{k+1}-x_0^{k+1}+2{\gamma }_2{x}_i^{k+1}-x_i^k\text{,}\\ {\partial }_{x_0}{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}=\partial g{x}_0^{k+1}-{\displaystyle \sum }_{i=1}^N{y}_i^{k+1}+\rho x_i^{k+1}-x_0^{k+1}+2{\gamma }_2{x}_0^{k+1}-x_0^k\text{,}\\ {\partial }_y{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}=\frac{1}{\rho }{\displaystyle \sum }_{i=1}^N{y}_i^{k+1}-y_i^k-\frac{{\tau }_k}{\rho }{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+\frac{{\tau }_k}{\rho }{\theta }_k{\displaystyle \sum }_{i=1}^N{x}_i^k-x_i^{k-1}\text{,}\\ {\partial }_{{\widehat{x}}_i}{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}=-2{\gamma }_2{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k\text{,}\\ {\partial }_{{\widehat{x}}_0}{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}=-2{\gamma }_2{x}_0^{k+1}-x_0^k\text{.}\end{array}\end{array}$$

From Lemma 1 and the optimality conditions, we get$$\begin{array}{}\text{(30)}& \begin{array}{c}0={\nabla }_{x_i}{f}_i{x}_i^{k+1}+y_i^k+\rho x_i^{k+1}-x_0^{k+1}+{\tau }_k{x}_i^{k+1}-z_i^k\text{,}\\ 0\in \partial g{x}_0^{k+1}-{\displaystyle \sum }_{i=1}^N{y}_i^k-\rho {\displaystyle \sum }_{i=1}^N{x}_i^k-x_0^{k+1}+{\tau }_k{x}_0^{k+1}-z_0^k\text{,}\\ y_i^{k+1}=y_i^k+\rho x_i^{k+1}-x_0^{k+1}+{\tau }_k{x}_i^{k+1}-z_i^k\text{.}\end{array}\end{array}$$

From (29) and (30), we obtain$$\begin{array}{}\text{(31)}& {{\alpha }_1^k,{\alpha }_2^k,{\alpha }_3^k,{\alpha }_4^k,{\alpha }_5^k}^{\mathrm{{\rm T}}}\in \partial {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\text{,}\end{array}$$where$$\begin{array}{}\text{(32)}& \begin{array}{c}{\alpha }_1^k=y_i^{k+1}-y_i^k+2{\gamma }_2-{\tau }_k{x}_i^{k+1}-x_i^k+{\tau }_k{\theta }_k{x}_i^k-x_i^{k-1}\text{,}\\ {\alpha }_2^k=-{\displaystyle \sum }_{i=1}^N{y}_i^{k+1}-y_i^k-\rho {\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+2{\gamma }_2-{\tau }_k{x}_0^{k+1}-x_0^k+{\tau }_k{\theta }_k{x}_0^k-x_0^{k-1}\text{,}\\ {\alpha }_3^k=\frac{1}{\rho }{\displaystyle \sum }_{i=1}^N{y}_i^{k+1}-y_i^k-\frac{{\tau }_k}{\rho }{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+\frac{{\tau }_k}{\rho }{\theta }_k{\displaystyle \sum }_{i=1}^N{x}_i^k-x_i^{k-1}\text{,}\\ {\alpha }_4^k=-2{\gamma }_2{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k\text{,}\\ {\alpha }_5^k=-2{\gamma }_2{x}_0^{k+1}-x_0^k\text{.}\end{array}\end{array}$$

Thus,$$\begin{array}{}\text{(33)}& d0,\partial {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\le {{\alpha }_1^k,{\alpha }_2^k,{\alpha }_3^k,{\alpha }_4^k,{\alpha }_5^k}^{\mathrm{{\rm T}}}\text{.}\end{array}$$

It follows from Assumption 1 and Lemma 1 that there exists $\delta >0$ such that $d0,\partial {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\le \delta {\beta }_k$, for each $k\in \mathrm{{\rm N}}$.

Lemma 5.

Let $\mathrm{\Gamma }{\widehat{w}}^k$ denote the cluster point set of ${\widehat{w}}^k$. Then, $\mathrm{\Gamma }{\widehat{w}}^k$ is a nonempty compact set, and ${\lim }_{k⟶+\infty }d{\widehat{w}}^k,\mathrm{\Gamma }{\widehat{w}}^k=0$.

And if ${\widehat{w}}^{\ast }={x_i^{\ast },x_0^{\ast },y^{\ast },{\widehat{x}}_i^{\ast },{\widehat{x}}_0^{\ast }}^{\mathrm{{\rm T}}}\in \mathrm{\Gamma }{\widehat{w}}^k$, then $w^{\ast }={x_i^{\ast },x_0^{\ast },y^{\ast }}^{\mathrm{{\rm T}}}$ is a critical point of the Lagrangian function $L$ of the problem (2). Moreover, ${\widehat{L}}_{\rho }\cdot$ is finite and constant on $\mathrm{\Gamma }{\widehat{w}}^k$ and ${\inf }_{k\in \mathrm{{\rm N}}}{\widehat{L}}_{\rho }{\widehat{w}}^k={\lim }_{k⟶+\infty }{\widehat{L}}_{\rho }{\widehat{w}}^k$.

Proof.

In view of the definition of $\mathrm{\Gamma }{\widehat{w}}^k$, it is true that $\mathrm{\Gamma }{\widehat{w}}^k$ is nonempty and compact, and ${\lim }_{k⟶+\infty }d{\widehat{w}}^k,\mathrm{\Gamma }{\widehat{w}}^k=0$.

Let ${\widehat{w}}^{\ast }={x_i^{\ast },x_0^{\ast },y^{\ast },{\widehat{x}}_i^{\ast },{\widehat{x}}_0^{\ast }}^{\mathrm{{\rm T}}}\in \mathrm{\Gamma }{\widehat{w}}^k$. Then, there exists a subsequence ${\widehat{w}}^{k_j+1}$ of ${\widehat{w}}^k$ converging to ${\widehat{w}}^{\ast }$. Since $w^{k+1}-w^k⟶0k⟶+\infty$, we have ${\lim }_{j⟶+\infty }{\widehat{w}}^{k_j+1}={\widehat{w}}^{\ast }$.

Since $y_i^{k_j+1}=y_i^{k_j}+\rho x_i^{k_j+1}-x_0^{k_j+1}+{\tau }_k{x}_i^{k_j+1}-z_i^{k_j}$, we have $x_i^{\ast }-x_0^{\ast }=0$.

Let $m_k{x}_0=L_{\rho }{x}_i^k,x_0,y^k+{\tau }_k/2{x_0-z_0^k}^2$. From Lemma 2, we have$$\begin{array}{c}\text{(34)}& g{x}_0^{k_{\mathrm{j}}+1}+{\displaystyle \sum }_{i=1}^N{y}_i^{k_j},x_i^{k_j}-x_0^{k_{\mathrm{j}}+1}+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^{k_j}-x_0^{k_{\mathrm{j}}+1}}^2+\frac{{\tau }_k}{2}{x_0^{k_{\mathrm{j}}+1}-z_0^{k_{\mathrm{j}}}}^2\le g{x}_0^{\ast }+{\displaystyle \sum }_{i=1}^N{y}_i^{k_j},x_i^{k_j}-x_0^{\ast }+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^{k_j}-x_0^{\ast }}^2+\frac{{\tau }_k}{2}{x_0^{\ast }-z_0^{k_{\mathrm{j}}}}^2\text{.}\end{array}$$

That is, $m_{k_j}{x}_0^{k_j+1}\le m_{k_j}{x}_0^{\ast }$.

Thus,$$\begin{array}{c}\text{(35)}& \underset{j⟶+\infty }{\mathrm{limsup}}{m}_{k_j}{x}_0^{k_j+1}=\underset{j⟶+\infty }{\mathrm{limsup}}g{x}_0^{k_{\mathrm{j}}+1}\le \underset{j⟶+\infty }{\mathrm{limsup}}{m}_{k_j}{x}_0^{\ast }=g{x}_0^{\ast }\text{.}\end{array}$$

Since $gx$ is proper lower semicontinuous, we obtain$$\begin{array}{}\text{(36)}& \underset{j⟶+\infty }{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}}g{x}_0^{k_{\mathrm{j}}+1}\ge g{x}_0^{\ast }\text{.}\end{array}$$

From above, we get$$\begin{array}{}\text{(37)}& \underset{j⟶+\infty }{\lim }g{x}_0^{k_{\mathrm{j}}+1}=g{x}_0^{\ast }\text{.}\end{array}$$

Together with the continuity of $f_{i}i=\mathrm{1,2},\dots ,N$ and the closeness of $\partial g$, we obtain$$\begin{array}{}\text{(38)}& \begin{array}{c}{\nabla }_{x_i}{f}_i{x}_i^{\ast }=-y_i^{\ast }\text{,}\\ {\displaystyle \sum }_{i=1}^N{y}_i^{\ast }\in \partial g{x}^{\ast }\text{,}\\ x_i^{\ast }-x_0^{\ast }=0\text{.}\end{array}\end{array}$$

Thus, ${\widehat{w}}^{\ast }$ is a critical point of the Lagrange function L of the problem (2).

From (37) and Lemma 5, we have$$\begin{array}{c}\text{(39)}& \underset{j⟶+\infty }{\lim }{\widehat{L}}_{\rho }{\widehat{w}}^{k_j+1}={\widehat{L}}_{\rho }{\widehat{w}}^{\ast }=L{w}^{\ast }\text{.}\end{array}$$

Therefore, from (39) and the descent of ${{\widehat{L}}_{\rho }{\widehat{w}}^k}_{k\in N}$, we obtain$$\begin{array}{}\text{(40)}& \underset{k⟶+\infty }{\lim }{\widehat{L}}_{\rho }{\widehat{w}}^k={\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{.}\end{array}$$

Thus, ${\widehat{L}}_{\rho }\cdot$ is constant on $\mathrm{\Gamma }{\widehat{w}}^k$. Moreover, ${\inf }_{k\in N}{\widehat{L}}_{\rho }{\widehat{w}}^k={\lim }_{k⟶+\infty }{\widehat{L}}_{\rho }{\widehat{w}}^k$.

Theorem 1.

Let ${\widehat{L}}_{\rho }{\widehat{w}}^k$ be the KL property at each point of $\mathrm{\Gamma }{\widehat{w}}^k$. Then, the bounded sequences $w^k$ converges to a critical point of $L\cdot$. Moreover,$$\begin{array}{}\text{(41)}& {\displaystyle \sum }_{k=0}^{+\infty }{w}^{k+1}-w^k<+\infty \text{.}\end{array}$$

Proof.

By Lemma 5, we have ${\lim }_{k⟶+\infty }{\widehat{L}}_{\rho }{\widehat{w}}^k={\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$, for all $w^{\ast }\in \mathrm{\Gamma }{\widehat{w}}^k$. We consider the following two cases:

(i) If there exist an integer $k_0$ such that ${\widehat{L}}_{\rho }{\widehat{w}}^{k_0}={\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$. From Lemma 2, for all $k>k_0$, we have$$\begin{array}{c}\text{(42)}& \eta {\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2\le {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\\ \le {\widehat{L}}_{\rho }{\widehat{w}}^{k_0}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{.}\end{array}$$

  Thus, for any $k>k_0$, we have $x_i^{k+1}=x_i^k,i=\mathrm{1,2},\cdots ,N,x_0^{k+1}=x_0^k$; therefore, for any $k>k_0+1$, it follows that ${\widehat{w}}^{k+1}={\widehat{w}}^k$ and the assertion holds.

(ii) Assume that ${\widehat{L}}_{\rho }{\widehat{w}}^k>{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$ for all $k\in N$. Since ${\lim }_{k⟶+\infty }d{\widehat{w}}^k,\mathrm{\Gamma }{\widehat{w}}^k=0$, it follows that for any give ${\epsilon }_1>0$, there exists $k_1>0$, such that $d{\widehat{w}}^k,\mathrm{\Gamma }{\widehat{w}}^k<{\epsilon }_1$. Again since ${\lim }_{k⟶+\infty }{\widehat{L}}_{\rho }{\widehat{w}}^k={\widehat{L}}_{\rho }{\widehat{w}}^{\ast }$, for give ${\epsilon }_2>0$, there exists $k_2>0$, such that ${\widehat{L}}_{\rho }{\widehat{w}}^k<{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }+{\epsilon }_2$, for all $k>k_2$.

Thus, when $k>\widehat{k}=\max k_1,k_2$, we have$$\begin{array}{}\text{(43)}& d{\widehat{w}}^k,\mathrm{\Gamma }{\widehat{w}}^k<{\epsilon }_1\text{,}{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }<{\widehat{L}}_{\rho }{\widehat{w}}^k<{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }+{\epsilon }_2\text{.}\end{array}$$

In view of $\mathrm{\Gamma }{\widehat{w}}^k$ is nonempty compact set, ${\widehat{L}}_{\rho }\cdot$ is constant on $\mathrm{\Gamma }{\widehat{w}}^k$. By Definition 2, we have ${\phi }^{\prime }Cd0,\partial {\widehat{L}}_{\rho }{\widehat{w}}^k\ge 1$, for all $k>\widehat{k}$.$$\begin{array}{}\text{(44)}& \frac{1}{\phi \prime C}\le d0,\partial {\widehat{L}}_{\rho }{\widehat{w}}^k\text{.}\end{array}$$

From the concavity of $\varphi$, we have$$\begin{array}{c}\text{(45)}& \phi {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }-\phi {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\ge \phi \prime {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }{\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\text{.}\end{array}$$

Since $\phi \prime {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }>0$ and Lemma 2, we obtain$$\begin{array}{c}\text{(46)}& {\gamma }_1-{\gamma }_2{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2\le {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{k+1}\\ \le \frac{\phi {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }-\phi {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }}{{\phi }^{\prime }{\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }}\\ \le \delta {\beta }_k\phi {\widehat{L}}_{\rho }{\widehat{w}}^k-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }-\phi {\widehat{L}}_{\rho }{\widehat{w}}^{k+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{.}\end{array}$$

Let ${\mathrm{\Phi }}_{a,b}=\phi {\widehat{L}}_{\rho }{\widehat{w}}^a-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }-\phi {\widehat{L}}_{\rho }{\widehat{w}}^b-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{.}$ Thus,$$\begin{array}{}\text{(47)}& {\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2\le \frac{\delta }{\eta }{\beta }_k{\mathrm{\Phi }}_{k,k+1}\text{,}\end{array}$$for all $k>\widehat{k}$. That is,$$\begin{array}{c}\text{(48)}& N+1{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k\le N+1\sqrt{N+1}{{\displaystyle \sum }_{i=1}^N{x_i^{k+1}-x_i^k}^2+{x_0^{k+1}-x_0^k}^2}^{\frac{1}{2}}\\ \le 2\sqrt{{\beta }_k}\sqrt{\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}{\mathrm{\Phi }}_{k,k+1}}\text{,}\end{array}$$for all $k>\widehat{k}$.

Since $a+b\ge 2\sqrt{ab}a,b>0$, we have$$\begin{array}{}\text{(49)}& 2\sqrt{{\beta }_k}\sqrt{\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}{\mathrm{\Phi }}_{k,k+1}}\le {\beta }_k+\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}{\mathrm{\Phi }}_{k,k+1}\text{.}\end{array}$$

From (48) and (49), we obtain$$\begin{array}{}\text{(50)}& N+1{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k\le {\beta }_k+\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}{\mathrm{\Phi }}_{k,k+1}\text{.}\end{array}$$

Summing up the above formula for $k=\widehat{k}+1,\dots ,p$, we have$$\begin{array}{}\text{(51)}& {\displaystyle \sum }_{k=\widehat{k}+1}^{p}N+1{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k\le {\displaystyle \sum }_{k=\widehat{k}+1}^p{\beta }_k+\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}{\mathrm{\Phi }}_{k,k+1}\text{.}\end{array}$$

Notice that $\varphi \widehat{L}{\widehat{w}}^{p+1}-\widehat{L}{\widehat{w}}^{\ast }>0$, it is easy to get$$\begin{array}{c}\text{(52)}& {\displaystyle \sum }_{k=\widehat{k}+1}^p{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k\le {\gamma }_k+\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}\phi {\widehat{L}}_{\rho }{\widehat{w}}^{\widehat{k}+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }-\phi {\widehat{L}}_{\rho }{\widehat{w}}^{p+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\\ \le {\gamma }_k+\frac{{N+1}^3\delta }{4{\gamma }_1-{\gamma }_2}\phi {\widehat{L}}_{\rho }{\widehat{w}}^{\widehat{k}+1}-{\widehat{L}}_{\rho }{\widehat{w}}^{\ast }\text{,}\end{array}$$where$$\begin{array}{}\text{(53)}& {\gamma }_k={\displaystyle \sum }_{i=1}^N{x}_i^{\widehat{k}+1}-x_i^{\widehat{k}}+x_0^{\widehat{k}+1}-x_0^{\widehat{k}}\text{.}\end{array}$$

Thus,$$\begin{array}{}\text{(54)}& {\displaystyle \sum }_{k=0}^{+\infty }{\displaystyle \sum }_{i=1}^N{x}_i^{k+1}-x_i^k+x_0^{k+1}-x_0^k\le +\infty \text{.}\end{array}$$

From Lemma 1, we get$$\begin{array}{}\text{(55)}& {\displaystyle \sum }_{k=0}^{+\infty }{w}^{k+1}-w^k<+\infty \text{.}\end{array}$$

By Lemma 5, we conclude that the sequences $w^k$ converge to a critical point of $L\cdot$.

4. Numerical Experiment

In this section, we present the results of a simple numerical example to verify the effectiveness of Algorithm 1. We consider the following compressive sense problem, which takes the following form:$$\begin{array}{c}\text{(56)}& \min \lambda {x_1}_0+\lambda {x_2}_1+\frac{1}{2}{A{x}_0-b}^2\text{,}\mathrm{s}.\mathrm{t}.x_i-x_0=0,\forall i=1,2,x_0\in X\text{,}\end{array}$$where $A$ is a $m\times n$ feature matrix, $b\in R^m$ is a response vector, and $\lambda$ is a regular parameter. In general, problem (56) is NP-hard. In order to overcome this difficulty, one may relax $l_0$ norm to the $l_{1/2}$ norm, considering the following nonconvex problem:$$\begin{array}{c}\text{(57)}& \min \lambda {x_1}_{1/2}^{1/2}+\lambda {x_2}_1+\frac{1}{2}{A{x}_0-b}^2\text{,}\mathrm{s}.\mathrm{t}.x_i-x_0=0,\forall i=1,2,x_0\in X\text{.}\end{array}$$

Let $f_1{x}_1=\lambda {x_1}_{1/2}^{1/2}$_,$f_2{x}_2=\lambda {x_2}_1$ and $g{x}_0=1/2{A{x}_0-b}^2$, $X={\mathrm{R}}^{\mathrm{N}}$. We now focus on applying Algorithm 1 to solve problem (57) with the suitable parameters. The iterative processes are as follows:$$\begin{array}{}\text{(58)}& \begin{array}{c}{x}_0^{k+1}=\underset{x_0\in X}{\mathrm{argmin}}g{x}_0+{\displaystyle \sum }_{i=1}^N{y}_i^k,x_i^k-x_0+\frac{\rho }{2}{\displaystyle \sum }_{i=1}^N{x_i^k-x_0}^2+\frac{{\tau }_k}{2}{x_0-z_0^k}^2\text{,}\\ x_1^{k+1}=\underset{x_1}{\mathrm{argmin}}{f}_1{x}_1+y_1^k,x_1-x_0^{k+1}+\frac{\rho }{2}{x_1-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{x_1-z_1^k}^2\text{,}\\ x_2^{k+1}=\underset{x_2}{\mathrm{argmin}}{f}_2{x}_2+y_2^k,x_2-x_0^{k+1}+\frac{\rho }{2}{x_2-x_0^{k+1}}^2+\frac{{\tau }_k}{2}{x_2-z_2^k}^2\text{,}\\ y_1^{k+1}=y_1^k+\rho x_1^{k+1}-x_0^{k+1}+{\tau }_k{x}_1^{k+1}-z_1^k\text{,}\\ y_2^{k+1}=y_2^k+\rho x_2^{k+1}-x_0^{k+1}+{\tau }_k{x}_2^{k+1}-z_2^k\text{.}\end{array}\end{array}$$

Simplifying the procedures (58), we obtain the closed-form iterative formulas:$$\begin{array}{}\text{(59)}& \begin{array}{c}{x}_0^{k+1}={A^{T}A+{\tau }_k+\rho NI}^{-1}{A}^{T}b+\rho {\displaystyle \sum }_{i=1}^N{x}_i^k+{\displaystyle \sum }_{i=1}^N{y}_i^k+{\tau }_k{z}_0^k\text{,}\\ x_1^{k+1}=H\frac{{\tau }_k{z}_1^k-y_1^k+\rho x_0^{k+1}}{\rho +{\tau }_k},\frac{2\lambda }{\rho +{\tau }_k}\text{,}\\ x_2^{k+1}=S\frac{{\tau }_k{z}_2^k-y_2^k+\rho x_0^{k+1}}{\rho +{\tau }_k},\frac{\lambda }{\rho +{\tau }_k}\text{,}\\ y_1^{k+1}=y_1^k+\rho x_1^{k+1}-x_0^{k+1}+{\tau }_k{x}_1^{k+1}-z_1^k\text{,}\\ y_2^{k+1}=y_2^k+\rho x_2^{k+1}-x_0^{k+1}+{\tau }_k{x}_2^{k+1}-z_2^k\text{,}\end{array}\end{array}$$where $z_0^k=x_0^k+{\theta }_k{x}_0^k-x_0^{k-1},z_i^k=x_i^k+{\theta }_k{x}_i^k-x_i^{k-1},i=\mathrm{1,2}$, $H\cdot ,\cdot$ is the half shrinkage operator^[16], and $SA,\cdot$ indicates the soft shrinkage operator imposed on the entries of $A$.

The experimental data are generated as follows. We use distributed computing toolbox in MATLAB, and the purpose is to achieve simple distributed computing. Suppose the feature matrix $A$ is standard normal distribution N (0, 1) m ${}^{\ast }$ n. Select sparse vector $a\in R^n$ from the N (0, 1) distribution. The parameters $b$ and $\lambda$ are set as $b_i=A_{i}a+\epsilon$ and $\lambda =0.01A_i^T\ast b_i$, where the noise vector $\epsilon \in N\mathrm{0,0.01}I\text{.}$ The variables $x_0,x_i,y_i$ were initialized to be zero. The primal residual is defined as $r^k={\sum }_{i=1}^N{x}_i^k\text{.}$ We employ $r^k\le \epsilon$ as the stopping criteria, where $\epsilon ={10}^{-4}$. The numerical results are reported in Table 1. We report the number of iterations (“Iter.”) and the computing time in seconds (“Time”) for the algorithms with different parameters under the dimension m = 2500, n = 1000.

Table 1

Comparison among two algorithms under different parameters.

$\theta$	Iter.	Time (s)	$\rho$	${\tau }_k$
Case 1 (ADMM)0	191	22.725124	600	$3l_f^2/\rho -2\theta \rho -l_f^2-2\theta$
Case 2 (IADMM)$1/2-l_f^2+1/\rho$	137	16.41164
Case 3 (IADMM)$1/3-l_f^2+1/\rho$	159	18.777039
Case 4 (ADMM)0	191	22.926591	500	$3l_f^2/\rho -2\theta \rho -l_f^2-2\theta$
Case 5 (IADMM)$1/2-l_f^2+1/\rho$	163	19.139843
Case 6 (IADMM)$1/3-l_f^2+1/\rho$	178	21.54476

The values of $r^k$ with the iterations are plotted in Figures 1 and 2.

[figure(s) omitted; refer to PDF]

where $l_f=\max {l_{f_i}}_{i=\mathrm{1,2},\cdots ,N}$.

From Table 1, and Figures 1 and 2, we can see that ADMM converges more slowly than IADMM since “Iter.” of ADMM bigger than that of IADMM under the same conditions. Finally, numerical results show that the algorithm is feasible and effective.

5. Conclusion

In this paper, inspired by the application of nonconvex global consensus problem with regularization, we propose multiblock inertial ADMM algorithm for solving certain nonconvex global consensus problems. We have proven its convergence under some suitable conditions, and it turns out that any cluster point of the sequence generated by the proposed algorithm is a critical point. Numerical experiment is conducted to illustrate the effectiveness of the multiblock inertial ADMM (IADMM) algorithm. Its potential of the flexible multiblock inertial ADMM to analyze and design other types of nonconvex case, as well as a more thorough computational study, are topics of our further research.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (72071130; 71901145); National Social Science Fund Major Project of China (21&ZD200; 20&ZD199); Humanities and Social Sciences Research Project of the Ministry of Education (20YJC820030) and China Postdoctoral Science Foundation (2021M692047).

References

[1] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, "Distributed optimization and statistical learning via the alternating direction method of multipliers," Foundations and Trends in Machine Learning, vol. 3,DOI: 10.1561/2200000016, 2010.

[2] G. Li, T. K. Pong, "Global convergence of splitting methods for nonconvex composite optimization," SIAM Journal on Optimization, vol. 25 no. 4, pp. 2434-2460, DOI: 10.1137/140998135, 2015.

[3] R. Glowinski, A. Marroco, "Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires," Revue française d'automatique, informatique, recherche opérationnelle. Analyse numérique, vol. 9 no. 2, pp. 41-76, DOI: 10.1051/m2an/197509r200411, 1975.

[4] D. Gabay, B. Mercier, "A dual algorithm for the solution of nonlinear variational problems via finite element approximation," Computers & Mathematics with Applications, vol. 2 no. 1, pp. 17-40, DOI: 10.1016/0898-1221(76)90003-1, 1976.

[5] L. Yang, T. K. Pong, X. Chen, "Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction," SIAM Journal on Imaging Sciences, vol. 10 no. 1, pp. 74-110, DOI: 10.1137/15m1027528, 2017.

[6] M. Hong, Z. Q. Luo, M. Razaviyayn, "Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems," SIAM Journal on Optimization, vol. 26 no. 1, pp. 337-364, DOI: 10.1137/140990309, 2016.

[7] K. Guo, D. Han, D. Z. W. Wang, T. Wu, "Convergence of ADMM for multi-block nonconvex separable optimization models," Frontiers of Mathematics in China, vol. 12 no. 5, pp. 1139-1162, DOI: 10.1007/s11464-017-0631-6, 2017.

[8] C. H. Chen, R. H. Chan, S. Q. Ma, J. F. Yang, "Inertial proximal ADMM for linearly constrained separable convex optimization," SIAM Journal on Imaging Sciences, vol. 8 no. 4, pp. 2239-2267, DOI: 10.1137/15100463x, 2015.

[9] A. Moudafi, E. Elissabeth, "Approximate inertial proximal methods using the enlargement of maximal monotone operators," International Journal of Pure and Applied Mathematics, vol. 5 no. 3, pp. 283-299, 2003.

[10] M. Chao, Y. Zhang, J. Jian, "An inertial proximal alternating direction method of multipliers for nonconvex optimization," International Journal of Computer Mathematics, vol. 98, 2021.

[11] K. Kurdyka, "On gradients of functions definable in o-minimal structures," Annales de l'Institut Fourier, vol. 48 no. 3, pp. 769-783, DOI: 10.5802/aif.1638, 1998.

[12] S. Lojasiewicz, "Sur la geométrie semi-et sous-analytique," Annales de l'Institut Fourier, vol. 43 no. 5, pp. 1575-1595, DOI: 10.5802/aif.1384, 1993.

[13] S. Lojasiewicz, "Une propriété topologique des sous-ensembles analytiques réels," Les Équations Aux Dérivées Partielles, 1963.

[14] J. Bolte, A. Daniilidis, O. Ley, L. Mazet, "Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity," Transactions of the American Mathematical Society, vol. 362 no. 6, pp. 3319-3363, DOI: 10.1090/s0002-9947-09-05048-x, 2009.