Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method

I Introduction

Distributed optimization methods are becoming popular options for solving several engineering problems, including parameter estimation, detection and localization problems in sensor networks , resource allocation problems in peer-to-peer/multi-cellular communication networks , and distributed learning and regression problems in control and machine learning , to name a few. In these applications, rather than pooling together all the relevant parameters that define the optimization problem, distributed agents, which have access to a local subset of such parameters, collaborate with each other to minimize a global cost function, subject to local variable constraints. Specifically, since it is not always efficient for the agents to exchange across the network the local cost and constraint functions, owing to the large size of network, time-varying network topology, energy constraints and/or privacy issues, distributed optimization methods that utilize only local information and messages exchanged between connecting neighbors have been of great interest; see and references therein.

Contributions: Different from the existing works where the local variable constraints are usually simple (in the sense that they can be handled via simple projection) and independent among agents, in this paper, we consider a problem formulation that has a general set of convex inequality constraints that couple all the agents’ optimization variables. In addition, similar to , the considered problem has a global (non-separable) convex cost function that is a function of the sum of local mapping functions of the local optimization variabless. Such a problem formulation appears, for example, in the classical regression problems which have a wide range of applications. In addition, the considered formulation also arises in the demand response control and power flow control problems in the emerging smart grid systems . More discussions about applications are presented in Section II-B.

In this paper, we assume that each agent knows only the local mapping function and local constraint function. To solve this problem in a distributed fashion, in this paper, we develop a novel distributed consensus-based primal-dual perturbation (PDP) algorithm, which combines the ideas of the primal-dual perturbed (sub-)gradient method and the average consensus techniques . In each iteration of the proposed algorithm, agents exchange their local estimates of the global cost and constraint functions with their neighbors, followed by performing one-step of primal-dual variable (sub-)gradient update. Instead of using the primal-dual iterates computed at the preceding iteration as in most of the existing primal-dual subgradient based methods , the (sub-)gradients in the proposed distributed PDP algorithm are computed based on some perturbation points which can be efficiently computed using the messages exchanged from neighbors. In particular, we provide two efficient ways to compute the perturbation points that can respectively handle the smooth and non-smooth constraint functions. More importantly, we build convergence analysis results showing that the proposed distributed PDP algorithm ensures a strong convergence of the local primal-dual iterates to a global optimal primal-dual solution of the considered problem. The proposed algorithm is applied to a distributed sparse regression problem and a distributed demand response control problem in smart grid. Numerical results for the two applications are presented to demonstrate the effectiveness of the proposed algorithm.

Related works: Distributed dual subgradient method (e.g., dual decomposition) is a popular approach to solving a problem with coupled inequality constraints in a distributed manner. However, given the dual variables, this method requires the agents to globally solve the local subproblems, which may require considerable computational efforts if the local cost and constraint functions have some complex structure. Consensus-based distributed primal-dual (PD) subgradient methods have been developed recently in for solving a problem with an objective function which is the sum of local convex cost functions, and with global convex inequality constraints. In addition to having a different cost function from our problem formulation, the works in assumed that all the agents in the network have global knowledge of the inequality constraint function; the two are in sharp contrast to our formulation where a non-separable objective function is considered and each agent can access only its local constraint function. Moreover, these works adopted the conventional PD subgradient updates without perturbation. Numerical results will show that these methods do not perform as well as the proposed algorithm with perturbation. Another recent development is the Bregman-distance based PD subgradient method proposed in for solving an epigraph formulation of a min-max problem. The method in , however, assumes that the Lagrangian function has a unique saddle point, in order to guarantee the convergence of the primal-dual iterates. In contrast, our proposed algorithm, which uses the perturbed subgradients, does not require such assumption.

Synopsis: Section II presents the problem formulation, applications, and a brief review of the centralized PD subgradient methods. Section III presents the proposed distributed consensus-based PDP algorithm. The assumptions and convergence analysis results are given in Section IV. Numerical results are presented in Section V. Finally, the conclusions and discussion of future extensions are drawn in Section VI.

II Problem Formulation, Applications and Brief Review

We assume that each agent $i$ can access $\mathcal{F}(\cdot)$, ${\bm{f}}_{i}(\cdot)$, ${\bm{g}}_{i}(\cdot)$ and $\mathcal{X}_{i}$ only, for all $i=1,\ldots,N$. Under this local knowledge constraint, the agents seek to cooperate with each other to minimize the total network cost $\bar{}\mathcal{F}({\bm{x}}_{1},\ldots,{\bm{x}}_{N})$ (or maximize the network utility $-\bar{}\mathcal{F}({\bm{x}}_{1},\ldots,{\bm{x}}_{N})$). Mathematically, the optimization problem can be formulated as follows

The goal of this paper is to develop a distributed algorithm for solving (2) with each agent communicating with their neighbors only.

II-B Application to Smart Grid Control

In this subsection, we discuss some smart grid control problems where the problem formulation (2) may arise. Consider a power grid system where a retailer (e.g., the utility company) bids electricity from the power market and serves a residential/industrial neighborhood with $N$ customers. In addition to paying for its market bid, the retailer has to pay additional cost if there is a deviation between the bid purchased in earlier market settlements and the real-time aggregate load of the customers. Any demand excess or shortfall results in a cost for the retailer that mirrors the effort to maintain the power balance. In the smart grid, thanks to the advances in communication and sensory technologies, it is envisioned that the retailer can observe the load of customers and can even control the power usage of some of the appliances (e.g., controlling the charging rate of electrical vehicles and turning ON/OFF air conditioning systems), which is known as the demand side management (DSM); see for a recent review.

which belongs to the considered formulation in (2). Similar problem formulations also arise in the microgrid control problems where the microgrid controller requires not only to control the loads but also to control the local power generation and local power storage (i.e., power flow control), in order to maintain power balance within the microgrid; see for detailed formulations. Distributed control methods are appealing to the smart grid application since all the agents are identical and failure of one agent would not have significant impact on the performance of the whole system . Besides, it also spares the retailer/microgrid controller from the task of collecting real-time information of customers, which not only infringes on the customer’s privacy but also is not easy for a large scale neighborhood. In Section V, the proposed distributed algorithm will be applied to a DSM problem as in (4).

In addition to the smart grid applications, problem (2) incorporates the important regression problems which widely appear in control , machine learning , data mining and imaging processing applications. Formulation (2) also encompasses the network flow control problems ; see for an example which considered maximizing the network lifetime. The proposed distributed algorithm therefore can be applied to these problem as well. For example, in , we have shown how the proposed distributed algorithm can be applied to handle a distributed sparse regression problem.

II-C Centralized PD Subgradient Method

Let us consider the following Lagrange dual problem of (2):

Throughout the paper, we assume that problem (2) is convex, i.e., ${\mathcal{X}}$ is closed and convex, $\bar{}\mathcal{F}({\bm{x}})$ is convex in ${\bm{x}}$ and each ${\bm{g}}_{i}({\bm{x}}_{i})$ is convex in ${\bm{x}}_{i}$. We also assume that the Slater condition holds, i.e., there is an $(\bar{}{\bm{x}}_{1},\ldots,\bar{}{\bm{x}}_{N})$ that lies in the relative interior of ${\mathcal{X}}_{1}\times\cdots\times{\mathcal{X}}_{N}$ such that $\sum_{i=1}^{N}{\bm{g}}_{i}(\bar{}{\bm{x}}_{i})\prec{\bm{0}}.$ Hence, the strong duality holds for problem (2) , problem (2) can be handled by solving its dual (5). A classical approach is the dual subgradient method . One limitation of such method is that the inner problem $\min_{\begin{subarray}{c}{\bm{x}}\in{\mathcal{X}}\end{subarray}}~{}{\mathcal{L}}({\bm{x}},{\bm{\lambda}})$ needs to be globally solved at each iteration, which, however, is not always easy, especially when ${\bm{f}}_{i}({\bm{x}}_{i})$ and ${\bm{g}}_{i}({\bm{x}}_{i})$ are complex or when the problem is large scale. Another approach is the primal-dual (PD) subgradient method which handles the inner problem inexactly. More precisely, at iteration $k$, the PD subgradient method performs

represent the subgradients of ${\mathcal{L}}$ at $({\bm{x}}^{(k)},{\bm{\lambda}}^{(k)})$ with respect to ${\bm{x}}$ and ${\bm{\lambda}}$, respectively. Each $\nabla{\bm{g}}_{i}({\bm{x}}_{i}^{(k)})$ is a $P\times K$ Jacobian matrix with rows equal to the subgradients $\nabla g^{T}_{ip}({\bm{x}}_{i})$, $p=1,\ldots,P$ (gradients if they are continuously differentiable), and each $\nabla{\bm{f}}_{i}({\bm{x}}_{i}^{(k)})$ is a $M\times K$ Jacobian matrix with rows containing the gradients $\nabla f^{T}_{im}({\bm{x}}_{i})$, $m=1,\ldots,M.$

The idea behind the PD subgradient method lies in the well-known saddle-point relation:

According to Theorem 1, if the PD subgradient method converges to a saddle point of the Lagrangian function (6), then it solves the original problem (2). Convergence properties of the PD method in (7) have been studied extensively; see, for example, . In such methods, typically a subsequence of the sequence $({\bm{x}}^{(k)},{\bm{\lambda}}^{(k)})$ converges to a saddle point of the Lagrangian function in (6). To ensure the convergence of the whole sequence $({\bm{x}}^{(k)},{\bm{\lambda}}^{(k)})$, it is often assumed that the Lagrangian function is strictly convex in ${\bm{x}}$ and strictly concave in ${\bm{\lambda}}$, which does not hold in general however.

One of the approaches to circumventing this condition is the primal-dual perturbed (PDP) subgradient method in . Specifically, suggests to update ${\bm{x}}^{(k-1)}$ and ${\bm{\lambda}}^{(k-1)}$ based on some perturbation points, denoted by $\hat{}{\bm{\alpha}}^{(k)}$ and $\hat{}{\bm{\beta}}^{(k)}$, respectively. The PDP updates are

Note that, in (10a), we have replaced ${\bm{\lambda}}^{(k-1)}$ by $\hat{}{\bm{\beta}}^{(k)}$, and, in (10b), replaced ${\bm{x}}^{(k-1)}$ by $\hat{}{\bm{\alpha}}^{(k)}$, and thus ${\mathcal{L}}_{{\bm{x}}}({\bm{x}}^{(k-1)},\hat{}{\bm{\beta}}^{(k)})$ and ${\mathcal{L}}_{{\bm{\lambda}}}(\hat{}{\bm{\alpha}}^{(k)},{\bm{\lambda}}^{(k-1)})$ are perturbed subgradients. It was shown in that, with carefully chosen $(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\beta}}^{(k)})$ and the step size $a_{k}$, the primal-dual iterates in (10) converge to a saddle point of (5), without any strict convexity and concavity assumptions on ${\mathcal{L}}$.

There are several ways to generate the perturbation points $\hat{}{\bm{\alpha}}^{(k)}$ and $\hat{}{\bm{\beta}}^{(k)}$. Our interests lie specifically on those that are computationally as efficient as the PD subgradient updates in (10). Depending on the smoothness of $\{g_{ip}\}_{p=1}^{P}$, we consider the following two methods:

Gradient Perturbation Points: A simple approach to computing the perturbation points is using the conventional gradient updates exactly as in (7), i.e.,

where $\rho_{1}>0$ and $\rho_{2}>0$ are constants. The PDP subgradient method thus combines (10) and (11), which involve two primal and dual subgradient updates. Even though the updates are relatively simple, this method requires smooth constraint functions $g_{ip}$, $p=1,\ldots,P$.

In cases when $g_{ip}$, $p=1,\ldots,P,$ are non-smooth, we propose to use the following proximal perturbation point approach, which is novel and has not appeared in earlier works .

Proximal Perturbation Points: When $g_{ip}$, $p=1,\ldots,P,$ are non-smooth, we compute the perturbation point $\hat{}{\bm{\alpha}}^{(k)}$ by the following proximal gradient updateIf not mentioned specifically, the norm function $\|\cdot\|$ stands for the Euclidian norm. :

where ${\bm{\alpha}}=({\bm{\alpha}}_{1}^{T},\ldots,{\bm{\alpha}}_{N}^{T})^{T}$ and

where ${\bm{b}}={\bm{x}}^{(k-1)}-\rho_{1}\nabla\bar{}\mathcal{F}({\bm{x}}^{(k-1)})$ and $\mathbf{1}$ is an all-one vector.

III Proposed Consensus-Based Distributed PDP Algorithm

Our goal is to develop a distributed counterpart of the PDP subgradient method in (10). Consider the following saddle-point problem

and thus $\hat{}{\bm{\lambda}}^{\star}$ lies in ${\mathcal{D}}$. Here we consider the saddle point problem (15), instead of the original Lagrange dual problem (5), because ${\mathcal{D}}$ bounds the dual variable ${\bm{\lambda}}$ and thus also bounds the subgradient ${\mathcal{L}}_{{\bm{x}}}({\bm{x}}^{(k)},{\bm{\lambda}}^{(k)})$ in (8a). This property is important in building the convergence of the distributed algorithm to be discussed shortly. Both (5) and (15) have the same optimal dual solution $\hat{}{\bm{\lambda}}^{\star}$ and attain the same optimal objective value. One can further verify that any saddle point of (5) is also a saddle point of (15). However, to relate the saddle points of (15) to solutions of problem (2) some conditions are needed, as given in the following proposition.

(Primal-dual optimality conditions) Let the Slater condition hold and let $(\hat{{\bm{x}}}_{1}^{\star},\ldots,\hat{{\bm{x}}}_{N}^{\star},\hat{}{\bm{\lambda}}^{\star})$ be a saddle point of (15). Then $(\hat{{\bm{x}}}_{1}^{\star},\ldots,\hat{{\bm{x}}}_{N}^{\star})$ is an optimal solution for problem (2) if and only if

1) Averaging consensus: For $i=1,\ldots,N$, each agent $i$ sends ${\bm{y}}_{i}^{(k-1)}$, ${\bm{z}}_{i}^{(k-1)}$ and ${\bm{\lambda}}_{i}^{(k-1)}$ to all its neighbors $j$ satisfying $(j,i)\in\mathcal{E}(k)$; it also receives ${\bm{y}}_{j}^{(k-1)}$, ${\bm{z}}_{j}^{(k-1)}$ and ${\bm{\lambda}}_{j}^{(k-1)}$ from its neighbors, and combines the received estimates, as follows:

2) Perturbation point computation: For $i=1,\ldots,N,$ if functions $g_{ip}$, $p=1,\ldots,P,$ are smooth, then each agent $i$ computes the local perturbation points by

3) Primal-dual perturbed subgradient update: For $i=1,\ldots,N$, each agent $i$ updates its primal and dual variables $({\bm{x}}_{i}^{(k)},{\bm{\lambda}}_{i}^{(k)})$ based on the local perturbation point $({\bm{\alpha}}_{i}^{(k)},{\bm{\beta}}_{i}^{(k)})$:

4) Auxiliary variable update: For $i=1,\ldots,N$, each agent $i$ updates variable ${\bm{y}}_{i}^{(k)}$, ${\bm{z}}_{i}^{(k)}$ with the changes of the local argument function ${\bm{f}}_{i}({\bm{x}}_{i}^{(k)})$ and the constraint function ${\bm{g}}_{i}({\bm{x}}_{i}^{(k)})$ :

Algorithm 1 summarizes the above steps. We prove that Algorithm 1 converges under proper problem and network assumptions in the next section. Readers who are interested more in numerical performance of Algorithm 1 may go directly to Section V.

IV Convergence Analysis

Next, in Section IV-A, we present additional assumptions on problem (2) and the network model. The main convergence results are presented in Section IV-B. The proofs are presented in Section IV-C and Section IV-D.

Our results will make use of the following assumption.

(a) The sets ${\mathcal{X}}_{i}$, $i=1,\ldots,N,$ are compact. In particular, for $i=1,\ldots,N$, there is a constant $D_{x}>0$ such that

(b) The functions $f_{i1},\ldots,f_{iM}$, $i=1,\ldots,N$, are continuously differentiable.

Note that Assumption 1(a) and Assumption 1(b) imply that $f_{i1},\ldots,f_{iM}$ have uniformly bounded gradients (denoted by $\nabla f_{im}$, $m=1,\ldots,M$) and are Lipschitz continuous, i.e., for some $L_{f}>0$,

Similarly, Assumption 1(a) and the convexity of functions $g_{i1},\ldots,g_{iP}$ imply that all $g_{ip}$ have uniformly bounded subgradients, which is equivalent to all $g_{ip}$ being Lipschitz continuous. Thus, for some $L_{g}>0$, we have

In addition, by Assumption 1 and the continuity of each $g_{ip}$ (which is implied by the convexity of $g_{ip}$) each ${\bm{f}}_{i}$ and ${\bm{g}}_{i}$ are also bounded on ${\mathcal{X}}$, i.e., there exist constants $C_{f}>0$ and $C_{g}>0$ such that for all $i=1,\ldots,N$,

where $\|{\bm{f}}_{i}({\bm{x}}_{i})\|=\sqrt{\sum_{m=1}^{M}f^{2}_{im}({\bm{x}}_{i})}$ and $\|{\bm{g}}_{i}({\bm{x}}_{i})\|=\sqrt{\sum_{p=1}^{P}g^{2}_{ip}({\bm{x}}_{i})}$.

We also make use of the following assumption on the network utility costs $\mathcal{F}$ and $\bar{}\mathcal{F}$:

(a) The function $\mathcal{F}$ is continuously differentiable and has bounded and Lipschitz continuous gradients, i.e., for some $G_{\mathcal{F}}>0$ and $L_{\mathcal{F}}>0$, we have

(b) The function $\bar{}\mathcal{F}$ has Lipschitz continuous gradients, i.e., for some $G_{\bar{}\mathcal{F}}>0$,

Note that the convexity of $\bar{}\mathcal{F}$ Assumption 1(a) indicate that $\bar{}\mathcal{F}$ is Lipschitz continuous, i.e., for some $L_{\bar{}\mathcal{F}}>0$,

Assumptions 1 and 2 are used to ensure that the (sub-)gradients of the Lagrangian function ${\mathcal{L}}({\bm{x}},{\bm{\lambda}})$ with respect to ${\bm{x}}$ are well behaved for applying (sub-)gradient-based methods. In cases that $g_{ip}$, $p=1,\ldots,P,$ are smooth, we make use of the following additional assumption:

The functions $g_{ip}$, $p=1,\ldots,P,$ are continuously differentiable and have Lipschitz continuous gradients, i.e., there exists a constant $G_{g}>0$ such that

We also have the following assumption on the network model :

The weighted graphs $\mathcal{G}(k)=\!(\mathcal{V},\mathcal{E}(k),{\bm{W}}(k))$ satisfy:

There exists a scalar $0<\eta<1$ such that $[{\bm{W}}(k)]_{ii}>\eta$ for all $i,k$ and $[{\bm{W}}(k)]_{ij}>\eta$ if $[{\bm{W}}(k)]_{ij}>0$.

${\bm{W}}(k)$ is doubly stochastic: $\sum_{j=1}^{N}[{\bm{W}}(k)]_{ij}=1$ for all $i,k$ and $\sum_{i=1}^{N}[{\bm{W}}(k)]_{ij}=1$ $\forall j,k$.

Assumption 4 ensures that all the agents can sufficiently and equally influence each other in a long run.

IV-B Main Convergence Results

be the running weighted-averages of the primal iterates ${\bm{x}}_{i}^{(0)},\ldots,{\bm{x}}_{i}^{(k-1)}$ generated by agent $i$ until time $k-1$. Our main convergence result for Algorithm 1 is given in the following theorem:

Let Assumptions 1-4 hold, and let $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$. Assume that the step size sequence $\{a_{k}\}$ is non-increasing and such that $a_{k}>0$ for all $k\geq 1$, $\sum_{k=1}^{\infty}a_{k}=\infty$ and $\sum_{k=1}^{\infty}a_{k}^{2}<\infty$. Let the sequences $\{\hat{}{\bm{x}}^{(k)}\}$ and $\{{\bm{\lambda}}_{i}^{(k)}\}$, $i=1,\ldots,N$, be generated by Algorithm 1 using the gradient perturbation points in (19). Then, $\{\hat{{\bm{x}}}^{(k)}\}$ and $\{{\bm{\lambda}}_{i}^{(k)}\}$, $i=1,\ldots,N$, converge to an optimal primal solution ${\bm{x}}^{\star}\in{\mathcal{X}}$ and an optimal dual solution ${\bm{\lambda}}^{\star}$ of problem (2), respectively.

Theorem 2 indicates that the proposed distributed primal-dual algorithm asymptotically yields an optimal primal and dual solution pair for the original problem (2). The same convergence result holds if the constraint functions $g_{ip}$, $p=1,\ldots,P,$ are non-smooth and the perturbation points ${\bm{\alpha}}_{i}^{(k)}$ are computed according to (20).

Let Assumptions 1, 2, and 4 hold, and let $\rho_{1}\leq 1/G_{\bar{}\mathcal{F}}$. Assume that the step size sequence $\{a_{k}\}$ is non-increasing and such that $a_{k}>0$ for all $k\geq 1$, $\sum_{k=1}^{\infty}a_{k}=\infty$ and $\sum_{k=1}^{\infty}a_{k}^{2}<\infty$. Let the sequences $\{\hat{}{\bm{x}}^{(k)}\}$ and $\{{\bm{\lambda}}_{i}^{(k)}\}$, $i=1,\ldots,N$, be generated by Algorithm 1 using the perturbation points in (20) and (19b). Then, $\{\hat{{\bm{x}}}^{(k)}\}$ and $\{{\bm{\lambda}}_{i}^{(k)}\}$, $i=1,\ldots,N$, converge to an optimal primal solution ${\bm{x}}^{\star}\in{\mathcal{X}}$ and an optimal dual solution ${\bm{\lambda}}^{\star}$ of problem (2), respectively.

The proofs of Theorems 2 and 3 are presented in the next two subsections, respectively.

IV-C Proof of Theorem 2

In this subsection, we present the major steps for proving Theorem 2. Three key lemmas that will be used in the proof are presented first. The first is a deterministic version of the lemma in [45, Lemma 11, Chapter 2.2]:

Let $\{b_{k}\}$, $\{d_{k}\}$ and $\{c_{k}\}$ be non-negative sequences. Suppose that $\sum_{{k=1}}^{\infty}c_{k}<\infty$ and

then the sequence $\{b_{k}\}$ converges and $\sum_{{k=1}}^{\infty}d_{k}<\infty$.

Moreover, by extending the results in [17, Theorem 4.2] and [11, Lemma 8(a)], we establish the following result on the consensus of $\{{\bm{\lambda}}_{i}^{(k)}\}$, $\{{\bm{y}}_{i}^{(k)}\}$, and $\{{\bm{z}}_{i}^{(k)}\}$ among agents.

Suppose that Assumptions 1 and 4 hold. If $\{a_{k}\}$ is a positive, non-increasing sequence satisfying $\sum_{k=1}^{\infty}a_{k}^{2}<\infty$, then

The proof is omitted here due to the space limitation; interested readers may refer to the electronic companion . Lemma 2 implies that the local variables ${\bm{\lambda}}_{i}^{(k)}$, ${\bm{y}}_{i}^{(k)}$ and ${\bm{z}}_{i}^{(k)}$ at distributed agents will eventually achieve consensus on the values of $\hat{}{\bm{\lambda}}^{(k)}$ $\hat{{\bm{y}}}^{(k)}$ and $\hat{{\bm{z}}}^{(k)}$, respectively.

The local perturbation points ${\bm{\alpha}}_{i}^{(k)}$ and ${\bm{\beta}}_{i}^{(k)}$ in (19) and (20) will also achieve consensus asymptotically. In particular, following (11), we define

for $i=1,\ldots,N,$ as the ‘centralized’ counterparts of (19); similarly, following (12), we define

for $i=1,\ldots,N,$ as the centralized counterparts of the proximal perturbation point in (20). We show in Appendix A the following lemma:

Let Assumptions 1 and 2 hold. For $\{{\bm{\alpha}}_{i}^{(k)},{\bm{\beta}}_{i}^{(k)}\}_{i=1}^{N}$ in (19) and $(\hat{}{\bm{\alpha}}_{1}^{(k)},\ldots,\hat{}{\bm{\alpha}}_{N}^{(k)},\hat{}{\bm{\beta}}^{(k)})$ in (42), it holds that

$i=1,\ldots,N.$ Equation (44) also holds for the proximal perturbation point ${\bm{\alpha}}_{i}^{(k)}$ in (20) and $\hat{}{\bm{\alpha}}_{i}^{(k)}$ in (43).

Now we are ready to prove Theorem 2. The proof primarily consists of showing two facts: (a) the primal-dual iterate pairs $(\hat{{\bm{x}}}_{1}^{(k)},\ldots,\hat{{\bm{x}}}_{N}^{(k)},\hat{{\bm{\lambda}}}^{(k)})$ will converge to a saddle point of (15), and (b) $(\hat{{\bm{x}}}_{1}^{(k)},\ldots,\hat{{\bm{x}}}_{N}^{(k)},\hat{{\bm{\lambda}}}^{(k)})$ asymptotically satisfies the primal-dual optimality conditions in Proposition 1. Thus, $(\hat{{\bm{x}}}_{1}^{(k)},\ldots,\hat{{\bm{x}}}_{N}^{(k)},\hat{{\bm{\lambda}}}^{(k)})$ is asymptotically primal-dual optimal to problem (2). To show the first fact, we use (21), (22) and Lemma 3 to characterize the basic relations of the primal and dual iterates.

Let Assumptions 1 and 2 hold. Then, for any ${\bm{x}}=({\bm{x}}_{1}^{T},\ldots,{\bm{x}}_{N}^{T})^{T}\in{\mathcal{X}}$ and ${\bm{\lambda}}\in{\mathcal{D}}$, the following two inequalities are true:

The detailed proof is given in the electronic companion . The second ingredient is a relation between the primal-dual iterates $({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})$ and the perturbation points $(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\beta}}^{(k)})$, as given below.

Let Assumptions 1, 2 and 3 hold. For the gradient perturbation points $(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\beta}}^{(k)})$ in (42), it holds true that

Moreover, let $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$, and suppose that ${\mathcal{L}}({\bm{x}}^{(k-1)},\hat{}{\bm{\beta}}^{(k)})-{\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})\rightarrow 0$ and $({\bm{x}}^{(k-1)},{\bm{\lambda}}^{(k-1)})$ converges to some limit point $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})\in{\mathcal{X}}\times{\mathcal{D}}$ as $k\rightarrow\infty$. Then $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ is a saddle point of (15).

The proof is presented in Appendix B. Using the preceding lemmas, we show the first key fact, namely, that $(\hat{{\bm{x}}}_{1}^{(k)},\ldots,\hat{{\bm{x}}}_{N}^{(k)},\hat{{\bm{\lambda}}}^{(k)})$ converges to a saddle point of (15).

Let Assumptions 1-4 hold, and let $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$. Assume that the step size $a_{k}>0$ is a non-increasing sequence satisfying $\sum_{k=1}^{\infty}a_{k}=\infty$ and $\sum_{k=1}^{\infty}a_{k}^{2}<\infty$. Then

where $\hat{}{\bm{x}}^{\star}=((\hat{}{\bm{x}}_{1}^{\star})^{T},\ldots,(\hat{}{\bm{x}}_{N}^{\star})^{T})^{T}\in{\mathcal{X}}$ and $\hat{}{\bm{\lambda}}^{\star}\in{\mathcal{D}}$ form a saddle point of problem (15).

Proof: By the compactness of the set ${\mathcal{X}}$ and the continuity of the functions $\bar{}\mathcal{F}$ and ${\bm{g}}_{i}$, problem (2) has a solution. Due to the Slater condition, the dual problem also has a solution. By construction of the set ${\mathcal{D}}$ in (16), all dual optimal solutions are contained in the set ${\mathcal{D}}$. We let ${\bm{x}}^{\star}=(({\bm{x}}_{1}^{\star})^{T},\ldots,({\bm{x}}_{N}^{\star})^{T})^{T}\in{\mathcal{X}}$ and ${\bm{\lambda}}^{\star}\in{\mathcal{D}}$ be an arbitrary saddle point of (15), and we apply Lemma 4 with ${\bm{x}}=({\bm{x}}_{1}^{T},\ldots,{\bm{x}}_{N}^{T})^{T}={\bm{x}}^{\star}$ and ${\bm{\lambda}}={\bm{\lambda}}^{\star}$. By summing (4) and (47), we obtain the following inequality

implying that ${\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},{\bm{\lambda}}^{\star})-{\mathcal{L}}({\bm{x}}^{\star},{\bm{\beta}}^{(k)})\geq 0$. Hence we deduce from (IV-C) that

According to Lemma 5, the above equation indicates that

Under the premise of $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$, and by (57) and (59), we obtain from Lemma 5 that $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})\in{\mathcal{X}}\times{\mathcal{D}}$ is a saddle point of (15). Moreover, because

we obtain from Lemma 2 and (59) that the sequence $\{\|{\bm{x}}^{(k)}-\hat{}{\bm{x}}^{\star}\|^{2}+\sum_{i=1}^{N}\|{\bm{\lambda}}_{i}^{(k)}-\hat{}{\bm{\lambda}}^{\star}\|^{2}\}$ has a limit value equal to zero. Since the sequence $\{\|{\bm{x}}^{(k)}-{\bm{x}}^{\star}\|^{2}+\sum_{i=1}^{N}\|{\bm{\lambda}}_{i}^{(k)}-{\bm{\lambda}}^{\star}\|^{2}\}$ converges for any saddle point of (15), we conclude that $\{\|{\bm{x}}^{(k)}-\hat{}{\bm{x}}^{\star}\|^{2}+\sum_{i=1}^{N}\|{\bm{\lambda}}_{i}^{(k)}-\hat{}{\bm{\lambda}}^{\star}\|^{2}\}$ in fact converges to zero, and therefore (49) is proved. Finally, relation (50) can also be obtained by (49), (54) and (5), provided that $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$. $\blacksquare$

According to [44, Lemma 3], if ${\bm{x}}^{(k)}\rightarrow{\bm{x}}^{\star}$ as $k\rightarrow\infty$, then its weighted running average ${\bm{x}}^{(k)}$ defined in (36) also converges to ${\bm{x}}^{\star}$ as $k\rightarrow\infty$. What remains is to show the second fact that $(\hat{{\bm{x}}}^{(k)},\hat{{\bm{\lambda}}}^{(k)})$ asymptotically satisfies the optimality conditions given by Proposition 1. We prove in Appendix C that the following lemma holds.

Under the assumptions of Lemma 6, it holds

By Lemma 6, Lemma 7 and Proposition 1, we conclude that Theorem 2 is true. Finally, we remark that when the step size $a_{k}$ has the form of $a/(b+k)$ where $a>0,b\geq 0$, one can simply consider the running average below

instead of the running weighted-average in (36) while Lemma 7 still holds true.

IV-D Proof of Theorem 3

Theorem 3 essentially can be obtained in the same line as the proof of Theorem 2, except for Lemma 5. What we need to show here is that the centralized proximal perturbation point $\hat{}{\bm{\alpha}}^{(k)}$ in (43) and $\hat{}{\bm{\beta}}^{(k)}$ in (42b) and the primal-dual iterates $({\bm{x}}^{(k-1)},{\bm{\lambda}}^{(k-1)})$ satisfy a result similar to Lemma 5. The lemma below is proved in Appendix D:

Let Assumptions 1 and 2 hold. For the centralized perturbation points $\hat{}{\bm{\alpha}}^{(k)}$ in (43) and $\hat{}{\bm{\beta}}^{(k)}$ in (42b), it holds true that

Moreover, let $\rho_{1}\leq 1/G_{\bar{}\mathcal{F}}$, and let ${\mathcal{L}}({\bm{x}}^{(k-1)},\hat{}{\bm{\beta}}^{(k)})-{\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})\rightarrow 0$ and $({\bm{x}}^{(k-1)},{\bm{\lambda}}^{(k-1)})\to(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ as $k\rightarrow\infty$, where $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})\in{\mathcal{X}}\times{\mathcal{D}}$. Then $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ is a saddle point of (15).

V Simulation Results

Analogous to (4), problem (63) can be reformulated as

to which the proposed distributed PDP method can be applied. We consider a scenario with 400 customers ($N=400$), and follow the same methods as in to generate the power bidding ${\bm{p}}$ and coefficients ${\bf\Psi}_{i}$, ${\bm{A}}_{i}$, ${\bm{b}}_{i}$, ${\bm{l}}_{i}$, ${\bm{u}}_{i}$, $i=1,\ldots,N$. The network graph $\mathcal{G}$ was randomly generated. The price parameters $\pi_{\rm p}$ and $\pi_{\rm s}$ were simply set to $1/N$ and $0.8/N$, respectively. In addition to the distributed PD method in , we also compare the proposed distributed PDP method with the distributed dual subgradient (DDS) methodOne can utilize the linear structure to show that (63) is equivalent to the following saddle point problem (by Lagrange dual) \displaystyle\max_{\begin{subarray}{c}{\bm{\lambda}}\succeq{\bm{0}},\\ {\bm{\eta}}\succeq{\bm{0}}\end{subarray}}~{}\bigg{\{}\min_{\begin{subarray}{c}{\bm{x}}_{i}\in{\mathcal{X}}_{i}\\ i=1,\ldots,N\end{subarray}} \displaystyle-\frac{1}{4\pi_{\rm p}}\|{\bm{\lambda}}\|^{2}-\frac{1}{4\pi_{\rm s}}\|{\bm{\eta}}\|^{2}+({\bm{\lambda}}-{\bm{\eta}})^{T}(\sum_{i=1}^{N}{\bf\Psi}_{i}{\bm{x}}_{i}-{\bm{p}})\bigg{\}} (65) to which the method in and the DDS method can be applied. . This method is based on the same idea as the dual decomposition technique , where, given the dual variables, each customer globally solves the corresponding inner minimization problem. The average consensus subgradient technique is applied to the dual domain for distributed dual optimization.

Figure 1(a) shows the convergence curves of the three methods under test. The curves shown in this figure are the corresponding objective values in (63) of the running average iterates of the three methods. The step size of the distributed PD method in was set to $a_{k}=\frac{15}{10+k}$ and that of the DDS method was set to $a_{k}=\frac{0.05}{10+k}$. For the proposed distributed PDP method, $a_{k}$, $\rho_{1}$ and $\rho_{2}$ were respectively set to $a_{k}=\frac{0.1}{10+k}$ and $\rho_{1}=\rho_{2}=0.001$. From this figure, we observe that the proposed distributed PDP method and the DDS method exhibit comparable convergence behavior; both methods converge within 100 iterations and outperform the distributed PD method in . One should note that the DDS method is computational more expensive than the proposed distributed PDP method since, in each iteration, the former requires to globally solve the inner minimization problem while the latter takes two primal gradient updates only. For the proposed PDP Algorithm 1, the complexity order per iteration per customer is given by $\mathcal{O}(4T)$ [see (19), (21) and (22)]. For the DDS method, each customer has to solve the inner linear programming (LP) in (65) $\min_{\begin{subarray}{c}{\bm{x}}_{i}\in{\mathcal{X}}_{i}\end{subarray}}({\bm{\lambda}}-{\bm{\eta}})^{T}{\bf\Psi}_{i}{\bm{x}}_{i}$ per iteration. According to , the worst-case complexity of interior point methods for solving an LP is given by $\mathcal{O}(T^{0.5}(3T^{2}+T^{3}))\approx\mathcal{O}(T^{3.5})$.

In Figure 1(b), we display the load profiles of the power supply and the unscheduled load (without DSM), while, in Figure 1(c), we show the load profiles scheduled by the three optimization methods under consideration. The results were obtained by respectively combining each of the optimization method with the certainty equivalent control (CEC) approach in [18, Algorithm 1] to handle a stochastic counterpart of problem (63). The stopping criterion was set to the maximum iteration number of 500. We can observe from this figure that, for all the three methods, the power balancing can be much improved compared to that without DSM control. However, we still can observe from Figure 1(c) that the proposed PDP method and the DDS method exhibit better results than the distributed PD method in . Specifically, the cost in (63) is $4.49\times 10^{4}$ KW for the unscheduled load whereas that of the load scheduled by the proposed distributed PDP method is $2.44\times 10^{4}$ KW ($45.65\%$ reduction). The cost for the load scheduled by the distributed DDS method is slightly lower which is $2.38\times 10^{4}$ KW; whereas that scheduled by the distributed PD method in has a higher cost of $3.81\times 10^{4}$ KW.

As discussed in Section II-B, problem (2) also incorporates the important regression problems. In , we have applied the proposed PDP method to solving a distributed sparse regression problem (with a non-smooth constraint function). The simulation results can be found in .

VI Conclusions

We have presented a distributed consensus-based PDP algorithm for solving problem of the form (2), which has a globally coupled cost function and inequality constraints. The algorithm employs the average consensus technique and the primal-dual perturbed (sub-) gradient method. We have provided a convergence analysis showing that the proposed algorithm enables the agents across the network to achieve a global optimal primal-dual solution of the considered problem in a distributed manner. The effectiveness of the proposed algorithm has been demonstrated by applying it to a smart grid demand response control problem and a sparse linear regression problem . In particular, the proposed algorithm is shown to have better convergence property than the distributed PD method in which does not have perturbation. In addition, the proposed algorithm performs comparably with the distributed dual subgradient method for the demand response control problem, even though the former is computationally cheaper.

Appendix A Proof of Lemma 3

We first show (45). By definitions in (42b) and (19b), and by the non-expansiveness of projection, we readily obtain

Equation (44) for the ${\bm{\alpha}}_{i}^{(k)}$ in (19a) and $\hat{}{\bm{\alpha}}_{i}^{(k)}$ in (42a) can be shown in a similar line:

where, in the second inequality, we have used the boundedness of gradients (cf. (26), (28)) and the Lipschitz continuity of $\nabla\mathcal{F}$ (Assumption 2).

To show that (44) holds for ${\bm{\alpha}}_{i}^{(k)}$ in (20) and $\hat{}{\bm{\alpha}}_{i}^{(k)}$ in (43), we use the following lemma:

Similarly, applying Lemma 9 to (43), we obtain

where we have used the boundedness of gradients (cf. (26), (28)), the Lipschitz continuity of $\nabla\mathcal{F}$ (Assumption 2) as well as the Lipschitz continuity of ${\bm{g}}_{i}$ (in (29)). The desired result in (44) follows from the preceding relation. $\blacksquare$

Appendix B Proof of Lemma 5

We first prove that relation (5) holds for the perturbation points $\hat{}{\bm{\alpha}}_{i}^{(k)}$ and $\hat{}{\bm{\beta}}^{(k)}$ in (42) assuming that Assumption 3 is satisfied. Note that (42a) is equivalent to

where ${\mathcal{L}}_{{\bm{x}}_{i}}({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})=\nabla{\bm{f}}_{i}^{T}({\bm{x}}_{i}^{(k-1)})\nabla\mathcal{F}(N\hat{}{\bm{y}}^{(k)})+\nabla{\bm{g}}^{T}_{i}({\bm{x}}_{i}^{(k-1)})\hat{}{\bm{\lambda}}^{(k-1)}$. By the optimality condition, we have that, for all ${\bm{x}}_{i}\in\mathcal{X}_{i},$

By choosing ${\bm{x}}_{i}={\bm{x}}_{i}^{(k-1)},$ one obtains

which, by summing over $i=1,\ldots,N$, gives rise to

Further write the above equation as follows

By (8), Assumption 2, Assumption 3 and the boundedness of $\hat{}{\bm{\lambda}}^{(k-1)}\in\mathcal{D}$, we can bound the second term in (B) as

where $\|\cdot\|_{F}$ denotes the Frobenious norm. By combining (B) and (B), we obtain

Since ${\mathcal{L}}({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})-{\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})\geq({\bm{x}}^{(k-1)}-\hat{}{\bm{\alpha}}^{(k)})^{T}{\mathcal{L}}_{{\bm{x}}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})$ by the convexity of ${\mathcal{L}}$ in ${\bm{x}}$, we further obtain

On the other hand, by (42b), we know that $\hat{}{\bm{\beta}}^{(k)}=\arg\min_{\beta\in\mathcal{D}}\|{\bm{\beta}}-\hat{}{\bm{\lambda}}^{(k-1)}-\rho_{2}\sum_{i=1}^{N}{\bm{g}}_{i}({\bm{x}}^{(k-1)}_{i})\|^{2}.$ By the optimality condition and the linearity of ${\mathcal{L}}$ in ${\bm{\lambda}}$, we have

Suppose that ${\mathcal{L}}({\bm{x}}^{(k-1)},\hat{}{\bm{\beta}}^{(k)})-{\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})\rightarrow 0$ and $({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})$ converges to some limit point $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ as $k\rightarrow\infty$. Since $\rho_{1}\leq 1/(G_{\bar{}\mathcal{F}}+D_{\lambda}\sqrt{P}G_{g})$, we infer from (5) that $\|{\bm{x}}^{(k-1)}-\hat{}{\bm{\alpha}}^{(k)}\|\to 0$ and $\|\hat{}{\bm{\lambda}}^{(k-1)}-\hat{}{\bm{\beta}}^{(k)}\|\to 0$, as $k\to\infty$. It then follows from (42) and the fact that projection is a continuous mapping that $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})\in{\mathcal{X}}\times{\mathcal{D}}$ satisfies

which, respectively, imply that $\hat{}{\bm{x}}^{\star}=\arg\min_{{\bm{x}}\in{\mathcal{X}}}{\mathcal{L}}({\bm{x}},\hat{}{\bm{\lambda}}^{\star})$ and $\hat{}{\bm{\lambda}}^{\star}=\arg\max_{{\bm{\lambda}}\in{\mathcal{D}}}{\mathcal{L}}(\hat{}{\bm{x}}^{\star},{\bm{\lambda}})$ i.e., $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ is a saddle point of problem (15). $\blacksquare$

Appendix C Proof of Lemma 7

By (47) in Lemma 4 and the fact of ${\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},{\bm{\lambda}})={\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{{\bm{\lambda}}}^{(k-1)})+({\bm{\lambda}}-\hat{{\bm{\lambda}}}^{(k-1)})^{T}{\mathcal{L}}_{{\bm{\lambda}}}(\hat{}{\bm{\alpha}}^{(k)},\hat{{\bm{\lambda}}}^{(k-1)})$, we have

where ${\bm{g}}(\hat{}{\bm{\alpha}}^{(k)})=\sum_{i=1}^{N}{\bm{g}}_{i}(\hat{}{\bm{\alpha}}^{(k)}_{i})$ and

By following a similar argument as in [27, Proposition 5.1] and by (A.11), (16), (29) and (30), one can show that

By taking the weighted running average of (A.12), we obtain

where the first inequality is owing to the fact that ${\bm{g}}({\bm{x}})$ is convex, and the last inequality is obtained by dropping $-\!\sum_{i=1}^{N}\!\|{\bm{\lambda}}_{i}^{(k)}\!-\!{\bm{\lambda}}\|^{2}$ followed by applying (16). We claim that

Now let ${\bm{\lambda}}=\hat{{\bm{\lambda}}}^{\star}+\delta~{}\frac{\left({\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\right)^{+}}{\|\left({\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\right)^{+}\|}$ which lies in ${\mathcal{D}}$, since $\|{\bm{\lambda}}\|\leq\|\hat{{\bm{\lambda}}}^{\star}\|+\delta\leq D_{\lambda}$ by (17). Substituting ${\bm{\lambda}}$ into (A.13) gives rise to

As a result, the first term in (60) is obtained by taking $k\rightarrow\infty$ in (A.15) and by (A.14).

To show that the second limit in (60) holds true, we first let ${\bm{\lambda}}=\hat{{\bm{\lambda}}}^{\star}+\delta~{}\frac{\hat{{\bm{\lambda}}}^{(k-1)}}{\|\hat{{\bm{\lambda}}}^{(k-1)}\|}\in{\mathcal{D}}.$ By substituting it into (A.13) and by (16), we obtain $(\hat{{\bm{\lambda}}}^{(k-1)})^{T}{\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\leq\left(\frac{D_{\lambda}}{\delta}\right)\xi^{(k-1)}$ which, by taking $k\rightarrow\infty$, leads to

On the other hand, by letting ${\bm{\lambda}}={\bm{0}}\in{\mathcal{D}}$, from (A.13) we have $-(\hat{{\bm{\lambda}}}^{(k-1)})^{T}{\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\leq\xi^{(k-1)}+(\hat{{\bm{\lambda}}}^{\star}-\hat{{\bm{\lambda}}}^{(k-1)})^{T}{\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\leq\xi^{(k-1)}+NC_{g}\|\hat{{\bm{\lambda}}}^{(k-1)}-\hat{{\bm{\lambda}}}^{\star}\|.$ Since $\lim_{k\rightarrow\infty}\xi^{(k-1)}=0$ and $\lim_{k\rightarrow\infty}\|\hat{{\bm{\lambda}}}^{(k)}-\hat{}{\bm{\lambda}}^{\star}\|=0$ by Lemma 6, it follows that $\liminf_{k\rightarrow\infty}~{}(\hat{{\bm{\lambda}}}^{(k-1)})^{T}{\bm{g}}(\hat{{\bm{x}}}^{(k-1)})\geq 0,$ which along with (A.16) yields the second term in (60). $\blacksquare$

Appendix D Proof of Lemma 8

The definition of $\hat{}{\bm{\alpha}}^{(k)}$ in (43) implies that

which, by summing over $i=1,\ldots,N,$ yields

where ${\bm{g}}(\hat{}{\bm{\alpha}}^{(k)})=\sum_{i=1}^{N}{\bm{g}}_{i}^{T}(\hat{}{\bm{\alpha}}_{i}^{(k)})$. By substituting the decent lemma in [49, Lemma 2.1]

which, after combining with (B), yields (8).

To show the second part of this lemma, let us recall (A.3) that $\hat{}{\bm{\alpha}}_{i}^{(k)}$ in (43) can be alternatively written as

which implies that, for all ${\bm{x}}_{i}\in{\mathcal{X}}_{i}$, we have

By summing the above inequality over $i=1,\ldots,N,$ one obtains, for all ${\bm{x}}\in{\mathcal{X}},$

where we have utilized the convexity of $\bar{}\mathcal{F}$, boundedness of ${\mathcal{X}}_{i}$ and the constraint functions (cf. Assumption 1 and (30)) in obtaining the last inequality. By applying (A.18) to the above inequality and by the premise of $1/\rho_{1}\geq G_{\bar{}\mathcal{F}}>G_{\bar{}\mathcal{F}}/2$, we further obtain, for all ${\bm{x}}\in{\mathcal{X}},$

in which one can bound the last term, using (34), (27), (29) and (16), by

Suppose that ${\mathcal{L}}({\bm{x}}^{(k-1)},\hat{}{\bm{\beta}}^{(k)})-{\mathcal{L}}(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\lambda}}^{(k-1)})\rightarrow 0$ and $({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})$ converges to some limit point $(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})$ as $k\rightarrow\infty$. Then, by (8) and since $1/\rho_{1}\geq G_{\bar{}\mathcal{F}}$, we have $\|({\bm{x}}^{(k-1)},\hat{}{\bm{\lambda}}^{(k-1)})-(\hat{}{\bm{\alpha}}^{(k)},\hat{}{\bm{\beta}}^{(k)})\|\to 0$, as $k\rightarrow\infty.$ Therefore,

Thus, it follows from (D), (A.20) and the above equation that ${\mathcal{L}}(\hat{}{\bm{x}}^{\star},\hat{}{\bm{\lambda}}^{\star})\leq{\mathcal{L}}({\bm{x}},\hat{}{\bm{\lambda}}^{\star})$ for all ${\bm{x}}\in{\mathcal{X}}$. The rest of the proof is similar to that of Lemma 5. $\blacksquare$

References