A Modified Distributed Optimization Algorithm via Alternating Direction Method of Multipliers

Optimization in networked multi-agent systems has widespread applications including wireless sensor nerworks [1], internet of things [2], distributed privacy preservation [3], distributed Nash Equilibrium seeking [4, 5] and machine learning [6]. Such a problem was initially handled in a centralized manner [7, 8, 9], which means that a centralized fusion is required to collect and process the information of all the agents through an underlying communication network. Clearly, tremendous communication and computation resources need to be consumed to implement the centralized optimization methods [10]. For instance, in linear regression problems, it is often prohibitive to gather all the data from different applications of interest [9]. In economic dispatch (ED) problems [11, 12], centralized manner cannot satisfy the plug-to-play demand.

To remove the mentioned limitations, distributed optimization problem(DOP) is considered. A common DOP is illustrated as follows,

$\displaystyle\min_{x\in\mathbb{R}^{d}}\quad\sum_{i=1}^{n}f_{i}(x).$

(1)

where $x\in\mathbb{R}^{d}$ is the global variable to be optimized, $f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the local cost function privately known by agent $i$, while unknown by other agents for $j\neq i$. In each agent, an estimate of the optimal solution, which is also known as the state, will be generated by applying an iterative algorithm. Then the states need often to be transmitted among networked agents for the purpose of reaching a consensus as the algorithm runs. Finally, the global optimization problem (1) can be solved through collaborations among different agents.

To solve the DOP, two main classes of distributed optimization algorithms have been proposed, namely the subgradient-based methods and dual-based methods. In the former class, a subgradient computation needs to be conducted in each iteration [13]. Each agent updates its state with the local subgradient information and states collected from other agents. The subgradient-based methods have been developed for various scenarios [14, 15, 16, 17, 18, 19]. In the dual-based methods, a Lagrangian-related functions need to be constructed in the update steps. Alternating Direction Method of Multipliers (ADMM) is a well-known dual-based method, of which the early works can be traced back to [20, 21, 35]. By treating the states as primal variables, ADMM minimizes an augmented Lagrangian function and updates both primal and dual variables alternately. In recent years, ADMM has become a popular way to solve DOPs in various areas. Compared with the subgradient-based methods, ADMM-based methods can achieve faster convergence rate [7, 25], and improved robustness against Gaussian noises[37].

It is worth noting that for some early works on ADMM-based algorithms developed to solve the optimization problems in a multi-agent systems, the utilization of the centralized fusion units cannot be avoided [7]. In [23], an ADMM-based optimization algorithm named Jacobi-Proximal ADMM is proposed. It adds a proximal term for each primal variable and a damping parameter for the update step of dual variable. Though the method shows a satisfactory performance, the dual variables need to be handled in a centralized manner. To avoid the need of centralized data processing, some distributed ADMM-based algorithms have been proposed. A sequential ADMM is proposed in [22], in which each agent updates its states by following a predefined order. Both primal and dual variables are computed in a distributed manner. However, the predefined updating order may cost more computational resources, which makes it not well suited for large-scaled systems. A novel algorithm named parallel ADMM is proposed in [8]. It reduplicates dual variables for each edge and doubles the dimension of edge-node incidence matrix to make parallelism amenable, hence the algorithm may need extra storage space.

In this paper, the sequential ADMM algorithm in [22] will be modified by adding extra terms are added in the primal variable updating rule. And then the primal variables of different iterations are adopted to update the dual variable for each agent. Main features of the newly presented algorithm are summarized as follows,

1. 1)

   The presented algorithm is fully distributed, in the sense that a central unit for data collection and processing is not needed for solving the optimization problem. The update of both primal and dual variables for each agent only depends on its local and neighboring information.

2. 2)

   The algorithm is suitable for parallel computing. By modifing the existing algorithm in [22], each agent updates primal variable in a parallel manner rather than a preset sequential order.

The remainder of our paper is organized as follows. In Section II, the considered unconstrained DOP is presented and the sequential ADMM algorithm in [22] is reviewed. In Section III, the modified ADMM for solving Probmen (1) with distributed and paralle manner is developed. In Section IV, numerical simulation results are provided to validate the effectiveness of the proposed method, followed by the conclusion drawn in Section V.

Notation: For a column vector $x$, $x^{\rm T}$ denotes the transpose of $x$. $||x||$ denotes the standard Euclidean norm, $||x||^{2}=x^{\rm T}x$. For a matrix $A$, $A^{\rm T}$ denotes the transpose of $A$. $A_{ij}$ denotes the entry located on the $i$th row and $j$th column of matrix $A$. $[A]_{i}$ and $[A]^{j}$ denotes the $i$th column and $j$th row of $A$, respectively. For matrices $A=[A_{ij}]\in\mathbb{R}^{m\times n}$ and $B=[B_{ij}]\in\mathbb{R}^{m\times n}$, $A\pm B=[A_{ij}\pm B_{ij}]$ and $\max\{A,B\}\triangleq[\max\{A_{ij},B_{ij}\}]$. $\mathbb{0}$ represents a matrix of all zeros. $\partial f(x)$ represents the set of all subgradient of function $f(x)$ at $x$. For a nonempty and finite set $F$, $|F|$ denotes the cardinality of the set.

In this paper, we shall revise the distributed ADMM algorithm in [22], such that it can be implemented in a parallel manner. Before we present the details of our proposed algorithm, some necessary preliminaries are provided in this section.

To remove the limitation of distributed sequential ADMM algorithm [22] as summarized in Section II, a new distributed ADMM algorithm is presented in this section. We first present the updating rules of each agent $i$ in the $k$th iteration:

	$\displaystyle x_{i}^{k+1}=$	$\displaystyle\underset{x_{i}}{\operatorname{argmin}}\Big{\{}f_{i}(x_{i})$
		$\displaystyle+(\sum_{j\in P_{i}}\lambda_{ji}^{k}-\sum_{j\in S_{i}}\lambda_{ij}^{k})x_{i}+\frac{\rho}{2}\sum_{j\in N_{i}}\|x_{i}-x_{j}^{k}\|^{2}$
		$\displaystyle-\rho(\sum_{j\in P_{i}}x_{j}^{k}-|S_{i}|x_{i}^{k})x_{i}+\frac{T\rho}{2}|S_{i}|\|x_{i}-x_{i}^{k}\|^{2}\Big{\}},$		(6)
	$\displaystyle\lambda_{ij}^{k+1}=$	$\displaystyle\lambda_{ij}^{k}-\rho(x_{i}^{k+1}-x_{j}^{k})$		(7)

where $\rho$ is a positive penalty parameter. $T$ is a constant satisfying $T\geqslant 3$. $P_{i}$ and $S_{i}$ are defined the same as mentioned above in Section II. $\lambda_{ij}$ denotes the dual variable associated with the constraint on edge $e_{ij}$ stored in agent $i$. Notice that according to the subscript, dual variable $\lambda_{ij}$ is stored in different agents in the two algorithm. The detailed procedure of the newly presented distributed ADMM algorithm is summarized below.

The proposed algorithm changes the sequential updating manner to a parallel way. As observed from (6), no terms related to $x_{j}^{k+1}$ are needed to update $x_{i}^{k+1}$. Hence all the $n$ agents can update both primal and dual variables simultaneously, rather than waiting for its predecessors to complete their updating procedures. For easier understanding the major difference between Algorithms 1 and 2, the parallel updating manner of $x_{i}^{k+1}$ for the considered group of 4 agents is plotted in Fig. 3.

In this section, we shall firstly show that all the agents’ states $x_{i}^{k}$ will converge to a unique optimal solution $\bar{x}^{\ast}$ as the number of iterations approaches infinity. Then the convergence rate will be analyzed.

Denote the global cost function by $F({x})=\sum_{i=1}^{n}f_{i}({x_{i})}$, where $x=[x_{1},x_{2},...,x_{n}]^{\rm T}\in\mathbb{R}^{n}$, and the optimal solution vector by $\bar{x}^{*}=[x^{*},x^{*},...,x^{*}]^{\rm T}\in\mathbb{R}^{n}$.

Let the vector $\lambda$ be the Lagrange multiplier vector. For clarity, $\lambda$ is stacked by dual variables with subscript numbers arranged in the ascending lexicographical order. Next an edge-node incidence matrix $A=[A_{pq}]\in\mathbb{R}^{m\times n}$ as defined in [22] is reintroduced to describe the existence of edges among two distinct agents for a given graph. Suppose that $\lambda_{pq}$ is the $r$th element of $\lambda$. $\lambda_{pq}$ corresponds to the $r$th row of $A$ (denoted by $[A]^{r}$). Note that the elements in $[A]^{r}$ satisfy that $A_{rp}=1,A_{rq}=-1$ and other entries are $0$. For example, the vector $\lambda$ can be written as $\lambda=[\lambda_{12},\lambda_{13},\lambda_{14},\lambda_{24},\lambda_{34}]^{\rm T}$, then the edge-incidence matrix $A$ of Fig. 1 is shown as follows,

$\displaystyle A=\begin{bmatrix}1&-1&0&0\\ 1&0&-1&0\\ 1&0&0&-1\\ 0&1&0&-1\\ 0&0&1&-1\end{bmatrix},$

(8)

Now Problem (3) can be rewritten in the following compact form,

	$\displaystyle\min_{x_{i}\in\mathbb{R}}\quad$	$\displaystyle\sum_{i=1}^{n}f_{i}(x_{i}),$
	$\displaystyle\operatorname{s.t.}\quad$	$\displaystyle Ax=0.$		(9)

next introduce two matrices $B=\max\{\mathbb{0},A\}$ and $E=A-B$ for further illustration.

Denote Lagrangian function of Problem (1) by $L(x,\lambda)=F(x)-\lambda^{\rm T}Ax$, next some typical assumptions are imposed.

Assumption 1: Each cost function $f_{i}:\mathbb{R}\rightarrow\mathbb{R}$ is closed, proper and convex.

The next assumption states the existence of the saddle point.

Assumption 2: The Lagrangian function has a saddle point, i.e., there exists a solution, variable pair$\{x^{*},\lambda^{*}\}$ with

$\displaystyle L(x^{*},\lambda)\leqslant L(x^{*},\lambda^{*})\leqslant L(x,\lambda^{*}).$

(10)

The following lemma shows that Problem (3) can be changed to the form of variational inequality, based on which we can complete the proof of optimality. which is not expressed in [22]. The details are demonstrated in Section IV.

Before establishing the main theorem, we first show three important lemmas. We now recall the following preliminary results.

Lemma 1[23]: Problem (3) is equivalent to variational inequality as follows,

$\displaystyle F(x)-F(x^{*})-(u-u^{*})^{\rm T}\mathscr{F}(u^{*})\geqslant 0,\forall u$

(11)

where $u=(x^{\rm T},\lambda^{\rm T})^{\rm T}\in\mathbb{R}^{n+m}$, $u^{*}=({x^{*}}^{\rm T},{\lambda^{*}}^{\rm T})^{\rm T}\in\mathbb{R}^{n+m}$. $\mathscr{F}(u)=[-[A]_{1}^{T}\lambda,-[A]_{2}^{T}\lambda,...,-[A]_{n}^{T}\lambda,Ax]^{T}$ is the solution of the variational inequality (3).

The classification of neighbors in Section II and Section III serves the convergence proof of our upcoming algorithm and has a special property without losing generality, shown in the next lemma. This property plays a crucial role in the convergence analysis. The proof of this lemma is provided in Appendix.

Lemma 2: In an undirected graph $\mathcal{G}$ with $n$ nodes, the following equation holds for all $n$:

$\displaystyle\sum_{i=1}^{n}|F_{i}|=\sum_{i=1}^{n}|R_{i}|.$

(12)

Next a basic lemma for convergence analysis is established.

Lemma 3: The following inequality holds for all $k$:

		$\displaystyle F(x)-F(x^{k+1})+(x-x^{k+1})^{\rm T}[-A^{\rm T}\lambda^{k+1}$
	$\displaystyle+$	$\displaystyle\rho(B^{\rm T}B+4E^{\rm T}E-A^{\rm T}E)(x^{k+1}-x^{k})]$
	$\displaystyle+$	$\displaystyle(x-x^{k+1})^{\rm T}A^{\rm T}Ex^{k}\geqslant 0.$		(13)

Proof: We define $g_{i}$ as follows,

	$\displaystyle g_{i}^{k}(x_{i})$	$\displaystyle=(\sum_{j\in F_{i}}\lambda_{ji}^{k}-\sum_{j\in R_{i}}\lambda_{ij}^{k})x_{i}+\frac{\rho}{2}\sum_{j\in N_{i}}\|x_{i}-x_{j}^{k}\|^{2}$
		$\displaystyle\quad-\rho(\sum_{j\in F_{i}}x_{j}^{k}-|R_{i}|x_{i}^{k})x_{i}+\frac{3\rho}{2}|R_{i}|\|x_{i}-x_{i}^{k}\|^{2}.$		(14)

Then the gradient of $g_{i}^{k}(x_{i}^{k+1})$ is

	$\displaystyle\nabla g_{i}^{k}(x_{i}^{k+1})=$	$\displaystyle\sum_{j\in F_{i}}\lambda_{ji}^{k}-\sum_{j\in R_{i}}\lambda_{ij}^{k}+\rho(|N_{i}|x_{i}^{k+1}-\sum_{j\in N_{i}}x_{j}^{k})$
		$\displaystyle+\rho(\sum_{j\in F_{i}}x_{j}^{k}-|R_{i}|x_{i}^{k})+3\rho|R_{i}|(x_{i}^{k+1}-x_{i}^{k})$
	$\displaystyle=$	$\displaystyle\sum_{j\in F_{i}}\lambda_{ji}^{k+1}-\sum_{j\in R_{i}}\lambda_{ij}^{k+1}+\rho[\sum_{j\in F_{i}}(x_{j}^{k+1}-x_{j}^{k})$
		$\displaystyle+|F_{i}|(x_{i}^{k+1}-x_{i}^{k})]-\rho(\sum_{j\in F_{i}}x_{j}^{k}-|R_{i}|x_{i}^{k})$
		$\displaystyle+3\rho|R_{i}|(x_{i}^{k+1}-x_{i}^{k})$		(15)

where the equation holds by utilizing (7) and the relation $(|N_{i}|x_{i}^{k+1}-\sum_{j\in N_{i}}x_{j}^{k})-(|R_{i}|x_{i}^{k+1}-\sum_{j\in R_{i}}x_{j}^{k})=|F_{i}|x_{i}^{k+1}-\sum_{j\in F_{i}}x_{j}^{k}$. Then denote $h_{i}(x_{i}^{k+1})\in\partial f_{i}(x^{k+1})$, thus we have $h_{i}(x_{i}^{k+1})+\nabla g_{i}^{k}(x_{i}^{k+1})=0$ and after that $(x_{i}-x_{i}^{k+1})[h_{i}(x_{i}^{k+1})+\nabla g_{i}^{k}(x_{i}^{k+1})]=0$ holds. For the relation of subgradient holds: $f_{i}(x_{i})\geqslant f_{i}(x_{i}^{k+1})+(x_{i}-x_{i}^{k+1})^{\rm T}h_{i}(x_{i}^{k+1})$, we get the following inequality:

$\displaystyle f_{i}(x_{i})-f_{i}(x_{i}^{k+1})+(x_{i}-x_{i}^{k+1})^{\rm T}\nabla g_{i}^{k}(x_{i}^{k+1})\geqslant 0.$

(16)

By substituting $\nabla g_{i}^{k}(x_{i}^{k+1})$ with (4) we obtain

		$\displaystyle f_{i}(x_{i})-f_{i}(x_{i}^{k})$
	$\displaystyle+$	$\displaystyle(x_{i}-x_{i}^{k})^{\rm T}\cdot(\sum_{j\in F_{i}}\lambda_{ji}^{k+1}-\sum_{j\in R_{i}}\lambda_{ij}^{k+1})$
	$\displaystyle+$	$\displaystyle(x_{i}-x_{i}^{k})^{\rm T}\cdot\{\rho(\sum_{j\in F_{i}}x_{j}^{k+1}-\sum_{j\in F_{i}}x_{j}^{k}+|F_{i}|x_{i}^{k+1}-|F_{i}|x_{i}^{k})$
	$\displaystyle-$	$\displaystyle\rho(\sum_{j\in F_{i}}x_{j}^{k}-|R_{i}|x_{i}^{k})+3\rho|R_{i}|(x_{i}^{k+1}-x_{i}^{k})\}\geqslant 0.$		(17)

Noting that the following relations hold for all $k$:

		$\displaystyle\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}(\sum_{j\in F_{i}}\lambda_{ji}^{k+1}-\sum_{j\in R_{i}}\lambda_{ij}^{k+1})$
	$\displaystyle=$	$\displaystyle\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}(-[A]_{i}^{\rm T}\lambda^{k+1})$
	$\displaystyle=$	$\displaystyle(x-x^{k+1})^{\rm T}A^{\rm T}\lambda^{k+1},$		(18)

		$\displaystyle\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}(\sum_{j\in F_{i}}x_{j}^{k+1}-\sum_{j\in F_{i}}x_{j}^{k}+|F_{i}|x_{i}^{k+1}-|F_{i}|x_{i}^{k})$
	$\displaystyle=$	$\displaystyle(x-x^{k+1})^{\rm T}(B^{\rm T}B+E^{\rm T}E-A^{\rm T}E)(x^{k+1}-x^{k}),$		(19)

		$\displaystyle\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}(\sum_{j\in F_{i}}x_{j}^{k}-|R_{i}|x_{i}^{k})$
	$\displaystyle=$	$\displaystyle(x-x^{k+1})(-A^{\rm T}E)x^{k},$		(20)

		$\displaystyle\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}|R_{i}|(x_{i}^{k+1}-x_{i}^{k})$
	$\displaystyle=$	$\displaystyle(x-x^{k+1})^{\rm T}E^{\rm T}E(x^{k+1}-x^{k})$		(21)

where relations (19) and (20) hold due to the matrix relation $A=B+E$.

Now summing over $1,2,...,n$, substituting the terms in (4) and using (18)-(21) we complete the proof. $\hfill\blacksquare$

The following theorem illustrates the main result in our algorithm that all agents’ states converge to the optimal point.

Theorem 1: The state $x_{i}$ generated by Algorithm 2 in each agent $i$ converges to the optimal solution of Problem (1), and global cost function converges to the optimal value with $k\rightarrow\infty$. i.e.,

	$\displaystyle\lim_{k\rightarrow\infty}x_{i}^{k}=\bar{x}^{*},i=1,2,...n,$		(22)
	$\displaystyle\lim_{k\rightarrow\infty}F(x^{k})=F(x^{*})$		(23)

where $\bar{x}^{*}$ and $F(x^{*})$ is the optimal solution and the optimal value, respectively.

Proof: According to $\lambda^{k+1}=\lambda^{k}-\rho(A-E)x^{k+1}-\rho Ex^{k}$ derived from (7) and $Ax^{*}=0$, where $x^{*}$ is the optimal solution, these following relations hold as follows,

		$\displaystyle\rho(x^{*}-x^{k+1})^{\rm T}B^{\rm T}B(x^{k+1}-x^{k})$
	$\displaystyle=$	$\displaystyle\frac{\rho}{2}(\|Bx^{k}-Bx^{*}\|^{2}-\|Bx^{k+1}-Bx^{*}\|^{2})$
		$\displaystyle-\frac{\rho}{2}\|Bx^{k+1}-Bx^{k}\|^{2},$		(24)

		$\displaystyle 4\rho(x^{*}-x^{k+1})’E^{\rm T}E(x^{k+1}-x^{k})$
	$\displaystyle=$	$\displaystyle 2\rho(\|Ex^{k}-Ex^{*}\|^{2}-\|Ex^{k+1}-Ex^{*}\|^{2})$
		$\displaystyle-2\rho\|E(x^{k+1}-x^{k})\|^{2},$		(25)

		$\displaystyle 2\rho(x^{k+1})^{\rm T}A^{\rm T}Ex^{k+1}-2\rho(x^{k+1})^{\rm T}A^{\rm T}Ex^{k}$
	$\displaystyle=$	$\displaystyle\frac{\rho}{2}\|Ax^{k+1}\|^{2}+2\rho\|E(x^{k+1}-x^{k})\|^{2}$
		$\displaystyle-\frac{\rho}{2}\|2E(x^{k+1}-x^{k})-A^{k+1}\|^{2},$		(26)

		$\displaystyle\rho(x^{k+1})^{\rm T}A^{\rm T}(\lambda^{k+1}-\lambda^{*})-\rho(x^{k+1})^{\rm T}A^{\rm T}Ex^{k+1}$
	$\displaystyle=$	$\displaystyle\frac{1}{2\rho}(\|\lambda^{k}-\lambda^{*}-Ex^{k}\|^{2}-\|\lambda^{k+1}-\lambda^{*}-Ex^{k+1}\|^{2})$
		$\displaystyle-\frac{\rho}{2}\|Ax^{k+1}\|^{2}.$		(27)

Then the following relation hold:

		$\displaystyle\rho(x^{k+1})^{\rm T}A^{\rm T}(\lambda^{k+1}-\lambda^{*})$
		$\displaystyle+\rho(x^{*}-x^{k+1})^{\rm T}(B^{\rm T}B+4E^{\rm T}E-A^{\rm T}E)(x^{k+1}-x^{k})$
		$\displaystyle-x^{k+1}A^{\rm T}Ex^{k}$
	$\displaystyle=$	$\displaystyle\rho(x^{k+1})^{\rm T}A^{\rm T}(\lambda^{k+1}-\lambda^{*})$
		$\displaystyle+\rho(x^{*}-x^{k+1})^{\rm T}(B^{\rm T}B+4E^{\rm T}E)\cdot(x^{k+1}-x^{k}),$
		$\displaystyle+(x^{k+1})^{\rm T}A^{\rm T}Ex^{k+1}-2(x^{k+1})^{\rm T}A^{\rm T}Ex^{k}$
	$\displaystyle=$	$\displaystyle-\frac{\rho}{2}\|2E(x^{k+1}-x^{k})-Ax^{k+1}\|^{2}-\frac{\rho}{2}\|B(x^{k+1}-x^{k})\|^{2}$
		$\displaystyle+\frac{1}{2\rho}(\|\lambda^{k}-\lambda^{*}-Ex^{k}\|^{2}-\|\lambda^{k+1}-\lambda^{*}-Ex^{k+1}\|^{2})$
		$\displaystyle+\frac{\rho}{2}(\|Bx^{k}-Bx^{*}\|^{2}-\|Bx^{k+1}-Bx^{*}\|^{2})$
		$\displaystyle+2\rho(\|Ex^{k}-Ex^{*}\|^{2}-\|Ex^{k+1}-Ex^{*}\|^{2}).$		(28)

Recall (4), set $x=x^{*}$ in and rearrange the terms, the following inequality is established:

		$\displaystyle(x^{k+1})^{\rm T}A^{\rm T}(\lambda^{k+1}-\lambda^{*})$
		$\displaystyle+(x^{*}-x^{k+1})\rho(B^{\rm T}B+4E^{\rm T}E)\cdot(x^{k+1}-x^{k})$
		$\displaystyle+(x^{k+1})^{\rm T}A^{\rm T}Ex^{k+1}-2x^{k+1}A^{\rm T}Ex^{k}$
	$\displaystyle\geqslant$	$\displaystyle F(x^{k+1})-(x^{k+1})^{\rm T}A^{\rm T}\lambda^{*}-F(x^{*})\geqslant 0$		(29)

where in the second inequality we use the relation of the saddle point of Lagrangian function relation $F(x^{*})-\lambda^{\rm T}Ax^{*}\leq F(x^{*})-(\lambda^{*})^{\rm T}Ax^{*}$.

Let $V^{k}=\frac{1}{2\rho}\|\lambda^{k}-\lambda^{*}-Ex^{k}\|^{2}+\frac{\rho}{2}\|Bx^{k}-Bx^{*}\|^{2}+2\rho\|Ex^{k}-Ex^{*}\|^{2}$, and we have that $V^{k}$ is a nonnegative term. By combining (4) and (4), we obtain

	$\displaystyle V^{k}-V^{k+1}-\frac{\rho}{2}\|2E(x^{k+1}-$	$\displaystyle x^{k})-Ax^{k+1}\|^{2}$
		$\displaystyle-\frac{\rho}{2}\|B(x^{k+1}-x^{k})\|^{2}\geqslant 0.$		(30)

Then rearranging and summing preceding relation over $0,1,...,k$ yields

	$\displaystyle V^{0}-V^{k}\geqslant$	$\displaystyle\sum_{k=0}^{s}(\frac{\rho}{2}\|2E(x^{k+1}-x^{k})-Ax^{k+1}\|^{2}$
		$\displaystyle+\frac{\rho}{2}\|B(x^{k+1}-x^{k})\|^{2})$
	$\displaystyle\geqslant$	$\displaystyle 0.$		(31)

Inequality (4) implies $V^{k}$ is bounded because $V_{0}$ is bounded and left side of (4) is nonnegative. Thus the following equation holds for any arbitrary constant $\rho$.

	$\displaystyle\lim_{k\rightarrow\infty}\frac{\rho}{2}(\|2E(x^{k+1}-x^{k})-$	$\displaystyle Ax^{k+1}\|^{2}$
		$\displaystyle+\|B(x^{k+1}-x^{k})\|^{2})=0.$		(32)

Equation (4) implies that that states of agents converge to the same point when the number of iterations goes to infinity. We now show that this point is the optimal point of the mentioned optimization Problem (1).

It is trivial to obtain that $\lambda^{k+1}=\lambda^{k}$ and $x_{1}^{k+1}=x_{2}^{k+1}=\ldots=x_{n}^{k+1}$ from $Ax^{k+1}=0$ and $x^{k+1}=x^{k}$. By summing up (4) over $1,2,...,n$, for $k\rightarrow\infty$, $\lambda^{k+1}=\lambda^{k}$ and $x_{1}^{k+1}=x_{2}^{k+1}=\ldots=x_{n}^{k+1}$, we obtain that

	$\displaystyle F(x)-F(x^{k+1})$	$\displaystyle+\sum_{i=1}^{n}(x_{i}-x_{i}^{k+1})^{\rm T}$
	$\displaystyle\cdot$	$\displaystyle\Big{\{}(-[A]_{i}\lambda-\rho(\sum_{j\in F_{i}}x_{j}^{k}-\sum_{j\in R_{i}}x_{i}^{k})\Big{\}}\geqslant 0.$		(33)

Notice that the optimal solution vector ${x}^{*}$ satisfies $Ax^{*}=0$, which implies the optimal solution $\bar{x}^{*}$ is the consensual value for all $x_{i}$, i.e., $(x_{1}^{*},x_{2}^{*},...,x_{n}^{*})^{\rm T}=(\bar{x}^{*},\bar{x}^{*},...,\bar{x}^{*})^{\rm T}$. For relation (4), now we let $x_{1}=x_{2}=...=x_{n}=\hat{x}$, then denote $\hat{u}=[\hat{x}\textbf{1}^{\rm T},\lambda^{\rm T}]^{\rm T}\in\mathbb{R}^{n+m}$ and $u^{k+1}=[{x^{k+1}}^{\rm T},{\lambda^{k+1}}^{\rm T}]^{\rm T}\in\mathbb{R}^{n+m}$. Then for arbitrary $\hat{x}\in\mathbb{R}$, inequality (4) can be written as

	$\displaystyle F(x)$	$\displaystyle-F(x^{k+1})+(\hat{u}-u^{k+1})^{\rm T}\mathscr{F}(u^{k+1})$
		$\displaystyle-\rho(\hat{u}-u^{k+1})\cdot(\sum_{i=1}^{n}|F_{i}|-\sum_{i=1}^{n}|R_{i}|)x\geqslant 0.$		(34)

By applying Lemma 2, (4) can be simplified as

$\displaystyle F(x)-F(x^{k+1})+(\hat{u}-u^{k+1})^{\rm T}\mathscr{F}(u^{k+1})\geqslant 0.$

(35)

Relation (35) indicates that for sufficiently large $k$, vector $u^{k+1}$ is the solution to (11). Then recall that Lemma 1 implies that the solution of the preceding VI is equivalent to the solution of our primary optimization problem. By using this lemma and the foregoing details we complete the proof of Theorem 1. $\hfill\blacksquare$

The next theorem reveals the convergence rate for our algorithm and shows the same rate as mentioned in [22, 10].

Theorem 2: Algorithm 2 converges at a rate of $O(\frac{1}{k})$.

Proof: By adding (4) into (4), we obtain

		$\displaystyle F(x^{*})-F(x^{k+1})$
	$\displaystyle-$	$\displaystyle\frac{\rho}{2}\|2E(x^{k+1}-x^{k})-Ax^{k+1}\|^{2}-\frac{\rho}{2}\|Bx^{k+1}-Bx^{k}\|^{2}$
	$\displaystyle+$	$\displaystyle\frac{1}{2\rho}(\|\lambda^{k}-Ex^{k}\|^{2}-\|\lambda^{k+1}-Ex^{k+1}\|^{2})$
	$\displaystyle+$	$\displaystyle\frac{\rho}{2}(\|Bx^{k}-Bx^{*}\|^{2}-\|Bx^{k+1}-Bx^{*}\|^{2})$
	$\displaystyle+$	$\displaystyle 2\rho(\|Ex^{k}-Ex^{*}\|^{2}-\|Ex^{k+1}-Ex^{*}\|^{2})\geqslant 0.$		(36)