# Distributed Optimization Methods for Nonconvex Problems with Inequality Constraints over Time-Varying Networks

Authors: Jueyou Li; Chuanye Gu; Zhiyou Wu; Changzhi Wu
Journal: Complexity
 (2017)

---

## Abstract

Network-structured optimization problems are found widely in engineering applications. In this paper, we investigate a nonconvex distributed optimization problem with inequality constraints associated with a time-varying multiagent network, in which each agent is allowed to locally access its own cost function and collaboratively minimize a sum of nonconvex cost functions for all the agents in the network. Based on successive convex approximation techniques, we first approximate locally the nonconvex problem by a sequence of strongly convex constrained subproblems. In order to realize distributed computation, we then exploit the exact penalty function method to transform the sequence of convex constrained subproblems into unconstrained ones. Finally, a fully distributed method is designed to solve the unconstrained subproblems. The convergence of the proposed algorithm is rigorously established, which shows that the algorithm can converge asymptotically to a stationary solution of the problem under consideration. Several simulation results are illustrated to show the performance of the proposed method.


---

## Body

## 1. Introduction

Network-structured problems have drawn recently considerable attention in various applications, such as mobile ad hoc networks, wireless sensor networks, and Internet networks [1–3]. The absence of centralized access to information and time-varying network connectivity are common features of network-structured problems. For this reason, distributed optimization methods associated with multiagent networks should be designed on the base of local communication and computation and the change of network topology. Distributed computing allows each agent to only utilize its own cost function and communicate with its direct neighbors, which has the potential advantage on protecting agents’ privacy. In recent years, there is an increasing trend to develop distributed optimization by integrating the communication and computation cooperation (see, e.g., [4, 5] and references therein).The methods designed to solve distributed convex problems have been widely studied in the literature. Based on the consensus averaging mechanism, there are several useful approaches, including primal consensus distributed methods, dual consensus distributed methods, and primal-dual consensus distributed methods. Nedic and Ozdaglar in [5] originally developed a distributed subgradient-based algorithm, in which every agent optimizes its own objective and locally exchanges information with neighboring agents in a network. The convergence rate of their proposed algorithm has been obtained. But, only unconstrained distributed problems were investigated. In [6], Nedic et al. generalized the distributed method in [5] to solve constrained convex optimization. Later, many researchers proposed various extensions based on primal (sub)gradient-based methods in, for example, [7–12]. In [13], Duchi et al. extended the centralized dual averaging algorithm to the distributed setting and then proposed a distributed dual averaging algorithm. The convergence result of their algorithm shows that the number of iterations is dependent on the underlying network sizes and spectral gaps. The primal-dual consensus distributed method was designed for solving distributed convex problems with global inequality constraints under the framework of Lagrangian duality. By finding the corresponding saddle-points of the Lagrangian function, Zhu and Martinez [14] first proposed a primal-dual consensus distributed algorithm and established the convergence results. The authors in [15] obtained the explicit convergence rate of the algorithm under the strong connectivity of networks.However, the methods mentioned above are not suitable for the general nonconvex distributed optimization problems. Until recently, there are some references designing algorithms for distributed nonconvex problems, such as [16, 17]. In [16], Lorenzo and Scutari developed a novel distributed algorithm for solving unconstrained nonconvex optimization problems which associated a multiagent network with time-varying connectivity. They combined a successive convex approximation technique and a dynamic consensus mechanism to realize distributed computation as well as local information exchange in the network. For nonconvex optimization problems with constraints, Scutari et al. [17] proposed a successive convex approximation method by solving a sequence of strongly convex subproblems while maintaining feasibility. They have shown that their proposed method can converge to a stationary solution of the original constrained nonconvex problem under consideration. However, the method proposed in [17] is not suitable in the distributed setting. Additionally, the Lagrange dual method is utilized to solve the sequence of strongly convex subproblems, which may largely enlarge the dimension of the problem due to introducing the dual variables. Thus, the computational difficulty and cost may be increased.In this paper, we investigate a distributed nonconvex problem with inequality constraints. The main contributions of this paper are twofold: (i) based on the penalty function method, a distributed algorithm for solving the nonconvex problem with global inequality constraints is proposed; (ii) the convergence of the proposed algorithm is rigorously proved. More specifically, we first transform the nonconvex problem to a sequence of strongly convex subproblems based on successive convex approximation techniques. In order to realize distributed computation, we then exploit the exact penalty function method to transform the sequence of strongly convex constrained subproblems into unconstrained ones. Finally, we propose a fully distributed method to solve these unconstrained subproblems. We obtain the convergence results of the proposed algorithm and demonstrate several numerical simulations.The work in this paper is closely related to the previous works [16–19]. Our method is based on the algorithm proposed in [16], but the problem we consider in this paper is different from the one in [16], since we investigate a nonconvex problem with global inequality constraints. The proposed algorithm is different from [17], since our algorithm exploits the exact penalty function method to solve the related subproblems possibly reducing the dimensionality of the problem. However, the algorithm in [17] utilized the Lagrange dual method to solve the subproblems, in which the computation is not implemented in a distributed manner. Our algorithm is an extension of the algorithm in [18] to handle with the nonconvex case. By comparison, we solve a constrained distributed nonconvex optimization in this paper, while the authors in [19] solved the unconstrained one.The remainder of this paper is organized as follows. Section2 provides the problem statement and related preparations. Section 3 gives the algorithm development. Section 4 proposes the distributed algorithm and establishes the results of convergence. Numerical simulations are given in Section 5. Finally, the conclusions are obtained in Section 6.


## 2. Problem Statement and Preparations

In the section, we state the optimization problem under consideration and give the assumptions and definitions that will be used in the sequel.


### 2.1. Problem Statement

Consider the following distributed nonconvex optimization problem:(1)minx∈KFx≔∑i=1Nfixs.t.gx≤0,where fix:Rd→R is a nonconvex smooth cost function, only known by agent i for i=1,…,N; g(x)≔(g1(x),…,gpx)T, gsx:Rd→R is a convex smooth function for s=1,…,p; and K⊆Rd is a closed, convex set. The constraint g(x) and the set K are known by all the agents. Let(2)χ≔x∈Rd∣gx≤0,x∈Kbe the feasible set of problem (1). We assume that Slater’s condition [20] is satisfied for problem (1).Problem (1) is ubiquitous that arises in many applications, such as networking, wireless communications, and machine learning. Therefore, it is meaningful to solve the problem.


### 2.2. Assumption and Definition

We first give the description of the network topology. Time is assumed to be discrete. At each time slotk, the network is modeled as a directed graph G[k]=(V,E[k]), where V={1,…,N} is the set of nodes with N agents, and E[k] represents the set of time-varying directed edges. The neighborhood of agent i at time k is defined as Niink=j∣j,i∈Ek∪i. The communication pattern between neighbors is set as follows: agent j≠i in Niink can communicate with node i at time k. We assign time-varying weights aijk to match the digraph Gk and define the weight matrix Ak=(aijk)i,j=1N.Assumption 1 (see [5]).
(A1) The graph sequence{G[k]} isB-strongly connected; that is, there is an integer B>0 such that the graph G[n]=(V,E[n]), with the edge set E[n]=∪k=nB(n+1)B-1E[k], is strongly connected, for all n≥0.
(A2) There is a scalarϑ with 0<ϑ<1, for all i∈{1,2,…,N}: (i) aii[k]≥ϑ for all k≥0; (ii) aij[k]≥ϑ for all k≥0 and all agents j communicate directly with agent i; (iii) otherwise, all agents j cannot communicate directly with agent i, aij[k]=0 for all k≥0.
(A3) Each weight matrixA[k] satisfies(3)Ak1=1,1TAk=1T,∀k≥0.Assumption1 shows that, at any time k, any agent j will receive the information from agent i within the next B time slots. Moreover, the weigh matrix A[k] is double-stochastic.Assumption 2.
(B1) The setK is nonempty, closed, and convex.
(B2) Fori∈{1,…,N}, each local function fi is continuously differentiable on K, and ∇fi is Lipschitz continuous on K with constant Li; let Lmax=maxi{Li}.
(B3)∇F is bounded on K; that is, there is a finite number LF>0 such that ∇F(x)≤LF, for all x∈K.
(B4) Fors∈{1,…,p}, each function ∇gs is bounded on K; that is, there is a finite number Lgs such that ∇gs≤Lgs; let LG=maxs{Lgs}.
(B5)F is coercive on K; that is, limx∈K,x→∞F(x)=+∞.The above assumptions are quite general, which can be satisfied by a large class of problems in practical applications. Assumption (B5) can make sure that problem (1) has a solution.The goal in this paper is to design a method that can find a stationary solution of problem (1). Moreover, the method is implemented in the distributed scenario satisfying Assumptions 1 and 2.Next we introduce several definitions, which will be used in the convergence analysis of our method.Definition 3 (regularity [21]).
A pointx¯∈χ is calledregular for problem (1) if the Mangasarian-Fromovitz Constraint Qualification (MFCQ) holds at x¯, that is, if the following implication is satisfied:(4)0∈∑s∈I¯ρs∇gsx¯+NKx¯,ρs≥0,∀s∈I¯⟹ρs=0,∀s∈I¯,where(5)NKx¯=d∈Rd:dTy-x¯≤0,∀y∈Kis the normal cone to K at x¯ and I¯={s∈{1,2,…,p}:gs(x¯)=0} is the index set of convex constraints that are active at x¯.Definition 4 (stationary point [17]).
A pointx¯∈χ is astationary point of problem (1), if it satisfies the following KKT system:(6)0∈∇Fx¯+∑s∈I¯ρs∇gsx¯+NKx¯,ρs≥0,∀s∈I¯,where ρs∈I¯ are Lagrange multipliers chosen suitably.As pointed out by [17], a regular (local) minimum point of problem (1) is also a stationary point. It is well known that the traditional goal for solving nonconvex problems is actually to find stationary points. To simplify the discussion, we assume that all feasible points of problem (1) are regular throughout the rest of this paper.


## 2.1. Problem Statement

Consider the following distributed nonconvex optimization problem:(1)minx∈KFx≔∑i=1Nfixs.t.gx≤0,where fix:Rd→R is a nonconvex smooth cost function, only known by agent i for i=1,…,N; g(x)≔(g1(x),…,gpx)T, gsx:Rd→R is a convex smooth function for s=1,…,p; and K⊆Rd is a closed, convex set. The constraint g(x) and the set K are known by all the agents. Let(2)χ≔x∈Rd∣gx≤0,x∈Kbe the feasible set of problem (1). We assume that Slater’s condition [20] is satisfied for problem (1).Problem (1) is ubiquitous that arises in many applications, such as networking, wireless communications, and machine learning. Therefore, it is meaningful to solve the problem.


## 2.2. Assumption and Definition

We first give the description of the network topology. Time is assumed to be discrete. At each time slotk, the network is modeled as a directed graph G[k]=(V,E[k]), where V={1,…,N} is the set of nodes with N agents, and E[k] represents the set of time-varying directed edges. The neighborhood of agent i at time k is defined as Niink=j∣j,i∈Ek∪i. The communication pattern between neighbors is set as follows: agent j≠i in Niink can communicate with node i at time k. We assign time-varying weights aijk to match the digraph Gk and define the weight matrix Ak=(aijk)i,j=1N.Assumption 1 (see [5]).
(A1) The graph sequence{G[k]} isB-strongly connected; that is, there is an integer B>0 such that the graph G[n]=(V,E[n]), with the edge set E[n]=∪k=nB(n+1)B-1E[k], is strongly connected, for all n≥0.
(A2) There is a scalarϑ with 0<ϑ<1, for all i∈{1,2,…,N}: (i) aii[k]≥ϑ for all k≥0; (ii) aij[k]≥ϑ for all k≥0 and all agents j communicate directly with agent i; (iii) otherwise, all agents j cannot communicate directly with agent i, aij[k]=0 for all k≥0.
(A3) Each weight matrixA[k] satisfies(3)Ak1=1,1TAk=1T,∀k≥0.Assumption1 shows that, at any time k, any agent j will receive the information from agent i within the next B time slots. Moreover, the weigh matrix A[k] is double-stochastic.Assumption 2.
(B1) The setK is nonempty, closed, and convex.
(B2) Fori∈{1,…,N}, each local function fi is continuously differentiable on K, and ∇fi is Lipschitz continuous on K with constant Li; let Lmax=maxi{Li}.
(B3)∇F is bounded on K; that is, there is a finite number LF>0 such that ∇F(x)≤LF, for all x∈K.
(B4) Fors∈{1,…,p}, each function ∇gs is bounded on K; that is, there is a finite number Lgs such that ∇gs≤Lgs; let LG=maxs{Lgs}.
(B5)F is coercive on K; that is, limx∈K,x→∞F(x)=+∞.The above assumptions are quite general, which can be satisfied by a large class of problems in practical applications. Assumption (B5) can make sure that problem (1) has a solution.The goal in this paper is to design a method that can find a stationary solution of problem (1). Moreover, the method is implemented in the distributed scenario satisfying Assumptions 1 and 2.Next we introduce several definitions, which will be used in the convergence analysis of our method.Definition 3 (regularity [21]).
A pointx¯∈χ is calledregular for problem (1) if the Mangasarian-Fromovitz Constraint Qualification (MFCQ) holds at x¯, that is, if the following implication is satisfied:(4)0∈∑s∈I¯ρs∇gsx¯+NKx¯,ρs≥0,∀s∈I¯⟹ρs=0,∀s∈I¯,where(5)NKx¯=d∈Rd:dTy-x¯≤0,∀y∈Kis the normal cone to K at x¯ and I¯={s∈{1,2,…,p}:gs(x¯)=0} is the index set of convex constraints that are active at x¯.Definition 4 (stationary point [17]).
A pointx¯∈χ is astationary point of problem (1), if it satisfies the following KKT system:(6)0∈∇Fx¯+∑s∈I¯ρs∇gsx¯+NKx¯,ρs≥0,∀s∈I¯,where ρs∈I¯ are Lagrange multipliers chosen suitably.As pointed out by [17], a regular (local) minimum point of problem (1) is also a stationary point. It is well known that the traditional goal for solving nonconvex problems is actually to find stationary points. To simplify the discussion, we assume that all feasible points of problem (1) are regular throughout the rest of this paper.


## 3. Development of Algorithm

Designing an effective distributed method for problem (1), we had to face three main challenges: (i) the nonconvexity of the objective function F; (ii) the unavailability of global knowledge on F; and (iii) the presence of inequality constraints g. In order to deal with the difficulties, we utilize successive convex approximation (SCA) techniques, exact penalty function methods, and dynamic consensus mechanisms to develop our algorithm.


### 3.1. Local SCA Approximation

In a distributed setting, the computational cost for directly solving problem (1) is considerably high and even infeasible. We would prefer to suitably approximate problem (1), in the sense of local convex approximation.By copying the global variablex, each agent i maintains a local estimate xi that needs to be updated at each iteration. We rewrite F(xi)=fi(xi)+∑j≠ifj(xi) and consider a convexification of F as follows: at each iteration, we use a strongly convex function fi~(·;xi[k]) to replace the nonconvex function fi and linearize the ∑j≠ifj(xi) at xi[k]; that is,(7)Fi^xi;xik=fi~xi;xik+πixikTxi-xik,where fi~·;xik:K→R is a strongly convex surrogate of the nonconvex fi and πi(xi[k]) is the gradient for the term ∑j≠ifj(xi) at xi[k]; that is,(8)πixik=∑j≠i∇xfjxik.At each iterationk, a strongly convex problem is solved by agent i(9)x^ixik=arg⁡minxi∈χ⁡Fi^xi;xik.Note that x^i(xi[k]) in (9) is well defined, since subproblem (9) has a unique solution.We give the following assumptions on the approximation offi.Assumption 5.
Eachfi~ satisfies the following:
(C1)fi~(·;x) is uniformly strongly convex on K×χ with a strongly convex parameter τi>0.
(C2)fi~(x;·) is uniformly Lipschitz continuous on K×χ.
(C3)∇fi~(x;x)=∇fi(x), for all x∈χ.Assumption5 is quite natural. The function fi~ is viewed as a strongly convex, local approximation of fi around x that inherits the first-order properties of fi. Assumption 5(C2) is the requirement of Lipschitzianity that is surely satisfied, for example, if the set K is bounded. For a given fi, several feasible choices are provided in [16, 22, 23].


### 3.2. Exact Penalty Function Method

Subproblem (9) is not easy to solve due to the presence of the global constraints g and the local accessibility of fi; thus, the exact penalty function method is utilized to transform subproblem (9) into an unconstrained problem, given by(10)x^ixik=arg⁡minxi∈K⁡Fi^xi;xik+cipxi,where p(xi)=max{0,g1(xi),…,gp(xi)}, ci>0 is a penalty parameter. We can obtain that p(xi) is convex on K, and Spxi≤LG for all Spxi∈∂pxi, where Spxi stands for the subgradient of p at xi.Under suitable conditions [24],the solution set of the penalized problem (10) coincides with the solution set of the constrained problem (9). In order to explain the fact in detail, we introduce the Lagrangian function of problem (9):(11)Lixi;λi=Fi^xi;xik+λiTgxi,where λi=(λi1,λi2,…,λip)T∈R+p is the vector of dual variable corresponding to the constraints g(xi)≤0. The dual problem of problem (9) is(12)maxλi∈R+p⁡dλiwithdλi=minxi∈K⁡Lixi;λi.It can be proved that no duality gap exists between subproblem (9) and its dual problem (12) if Slater’s condition is satisfied (see Proposition  5.3.1 in [20]). In addition, the set of dual optimal solutions is nonempty bounded. Thus, based on Proposition  1 in [24], there is a penalty parameter satisfied ci>∑s=1pλi,s such that the solutions of penalized problem (10) are the same as those of subproblem (9). Thus, throughout the rest of this paper, we can always select a finite penalty parameter c¯i such that c¯i≥ci.


### 3.3. Consensus Update

We now introduce a consensus mechanism to ensure that each local estimatexi gradually coincides among all agents. A consensus-based step is used on x^i(xi[k]) and each agent i updates its state as follows:(13)xik+1=∑j∈Niinkaijkx^jxjk,where aij[k] is the weight satisfying Assumption 1.Since the evaluation ofπixik in (8) requires the quantity of all ∇fjxik, j≠i, which is not feasible at agent i. In order to deal with the issue, we need a local estimation of πixik in (8), eventually converging to ∑j≠i∇fjxik. We rewrite πixik in (8) as follows:(14)πixik=N·1N∑j=1N∇fjxik-∇fixik,and let ∇f¯xik=(1/N)∑j=1N∇fj(xi[k]). Then, we replace πixik in (14) by πi~xik(15)πi~xik=N·yik-∇fixik,where yi[k] is a locally auxiliary variable updated by agent i, asymptotically tracking ∇f¯(xi[k]). By using the dynamic averaging consensus strategy [25], we can update yi[k] in (15) via the following formula:(16)yik+1=∑j=1Naijkyjk+∇fixik+1-∇fixik,where yi[0]=∇fi(xi[0]).Note that the update ofyi[k] in (16), and thus π~i(xi[k])) in (15), can be now performed locally with message exchanges with the agents in the neighborhood Niin[k]. By the above description, problem (10) can be converted into the following problem:(17)x~ik=arg⁡minxi∈K⁡U~ixi;xik,π~ixik,where U~i(xi;xi[k],π~i(xi[k]))=f~i(xi;xi[k])+π~i(xi[k])T(xi-xi[k])+cip(xi).


## 3.1. Local SCA Approximation

In a distributed setting, the computational cost for directly solving problem (1) is considerably high and even infeasible. We would prefer to suitably approximate problem (1), in the sense of local convex approximation.By copying the global variablex, each agent i maintains a local estimate xi that needs to be updated at each iteration. We rewrite F(xi)=fi(xi)+∑j≠ifj(xi) and consider a convexification of F as follows: at each iteration, we use a strongly convex function fi~(·;xi[k]) to replace the nonconvex function fi and linearize the ∑j≠ifj(xi) at xi[k]; that is,(7)Fi^xi;xik=fi~xi;xik+πixikTxi-xik,where fi~·;xik:K→R is a strongly convex surrogate of the nonconvex fi and πi(xi[k]) is the gradient for the term ∑j≠ifj(xi) at xi[k]; that is,(8)πixik=∑j≠i∇xfjxik.At each iterationk, a strongly convex problem is solved by agent i(9)x^ixik=arg⁡minxi∈χ⁡Fi^xi;xik.Note that x^i(xi[k]) in (9) is well defined, since subproblem (9) has a unique solution.We give the following assumptions on the approximation offi.Assumption 5.
Eachfi~ satisfies the following:
(C1)fi~(·;x) is uniformly strongly convex on K×χ with a strongly convex parameter τi>0.
(C2)fi~(x;·) is uniformly Lipschitz continuous on K×χ.
(C3)∇fi~(x;x)=∇fi(x), for all x∈χ.Assumption5 is quite natural. The function fi~ is viewed as a strongly convex, local approximation of fi around x that inherits the first-order properties of fi. Assumption 5(C2) is the requirement of Lipschitzianity that is surely satisfied, for example, if the set K is bounded. For a given fi, several feasible choices are provided in [16, 22, 23].


## 3.2. Exact Penalty Function Method

Subproblem (9) is not easy to solve due to the presence of the global constraints g and the local accessibility of fi; thus, the exact penalty function method is utilized to transform subproblem (9) into an unconstrained problem, given by(10)x^ixik=arg⁡minxi∈K⁡Fi^xi;xik+cipxi,where p(xi)=max{0,g1(xi),…,gp(xi)}, ci>0 is a penalty parameter. We can obtain that p(xi) is convex on K, and Spxi≤LG for all Spxi∈∂pxi, where Spxi stands for the subgradient of p at xi.Under suitable conditions [24],the solution set of the penalized problem (10) coincides with the solution set of the constrained problem (9). In order to explain the fact in detail, we introduce the Lagrangian function of problem (9):(11)Lixi;λi=Fi^xi;xik+λiTgxi,where λi=(λi1,λi2,…,λip)T∈R+p is the vector of dual variable corresponding to the constraints g(xi)≤0. The dual problem of problem (9) is(12)maxλi∈R+p⁡dλiwithdλi=minxi∈K⁡Lixi;λi.It can be proved that no duality gap exists between subproblem (9) and its dual problem (12) if Slater’s condition is satisfied (see Proposition  5.3.1 in [20]). In addition, the set of dual optimal solutions is nonempty bounded. Thus, based on Proposition  1 in [24], there is a penalty parameter satisfied ci>∑s=1pλi,s such that the solutions of penalized problem (10) are the same as those of subproblem (9). Thus, throughout the rest of this paper, we can always select a finite penalty parameter c¯i such that c¯i≥ci.


## 3.3. Consensus Update

We now introduce a consensus mechanism to ensure that each local estimatexi gradually coincides among all agents. A consensus-based step is used on x^i(xi[k]) and each agent i updates its state as follows:(13)xik+1=∑j∈Niinkaijkx^jxjk,where aij[k] is the weight satisfying Assumption 1.Since the evaluation ofπixik in (8) requires the quantity of all ∇fjxik, j≠i, which is not feasible at agent i. In order to deal with the issue, we need a local estimation of πixik in (8), eventually converging to ∑j≠i∇fjxik. We rewrite πixik in (8) as follows:(14)πixik=N·1N∑j=1N∇fjxik-∇fixik,and let ∇f¯xik=(1/N)∑j=1N∇fj(xi[k]). Then, we replace πixik in (14) by πi~xik(15)πi~xik=N·yik-∇fixik,where yi[k] is a locally auxiliary variable updated by agent i, asymptotically tracking ∇f¯(xi[k]). By using the dynamic averaging consensus strategy [25], we can update yi[k] in (15) via the following formula:(16)yik+1=∑j=1Naijkyjk+∇fixik+1-∇fixik,where yi[0]=∇fi(xi[0]).Note that the update ofyi[k] in (16), and thus π~i(xi[k])) in (15), can be now performed locally with message exchanges with the agents in the neighborhood Niin[k]. By the above description, problem (10) can be converted into the following problem:(17)x~ik=arg⁡minxi∈K⁡U~ixi;xik,π~ixik,where U~i(xi;xi[k],π~i(xi[k]))=f~i(xi;xi[k])+π~i(xi[k])T(xi-xi[k])+cip(xi).


## 4. Algorithm and Convergence Results

Based on the previous algorithm development, we propose an exact penalty function based distributed algorithm (EPDA, for short) to solve problem (1), presented in Algorithm 1.Algorithm 1:Exact penalty function based distributed algorithm.
(1) Initialization: xi[0]∈K, yi[0]=∇fi[0], πi~(xi[0])=N⋅yi[0]-∇fi[0], for all i=1,…,N.
Choose the weigh matrix (aij[k]) satisfied Assumption 1 and the step-size α[k] satisfied (20).
Select a penalty parameter ci>0. Set k≔0;
(2)repeat
(3) for each agent i=1,…,Ndo
(4) Local SCA optimization: compute x~i[k] by solving problem (17);
(5) Update zi[k]=xi[k]+α[k](x~i[k]-xi[k]);
(6) Consensus update:
(a) xi[k+1]=∑j=1Naij[k]zj[k];
(b) yi[k+1]=∑j=1Naij[k]yj[k]+(∇fi(x[k+1])-∇fi(x[k]));
(c) π~i(xi[k+1])=N⋅yi[k+1]-∇fi(x[k+1]);
(7) end for
(8) Set k≔k+1;
(9) untilxi[k] satisfies a termination criterion.In order to obtain the convergence results of the proposed algorithm, we first give Lemma6, which shows the relationship between the solutions of problem (1) and the solutions of subproblem (9). Note that the following conditions (18) and (19) can be satisfied; please see the proof of relation (A.32).Lemma 6.
Suppose that Assumptions1, 2, and 5 hold. Let {xi[k]} be the sequence generated by Algorithm 1; the following results hold:
(i) If(18)lim⁡infk→∞⁡x^ixik-xik=0,∀i=1,…,N,then at least one regular limit point of {xi[k]} is a stationary solution of problem (1).
(ii) If(19)limk→∞⁡x^ixik-xik=0,∀i=1,…,N,then every regular limit point of {xi[k]} is a stationary solution of problem (1).Proof.
See Appendix(2).We are now in the position to give the convergence properties of Algorithm1.Theorem 7.
Let{x[k]}={(xi[k])i=1N} be the sequence generated by Algorithm 1 and let {x¯[k]}={(1/N)∑i=1Nxi[k]} be the average. Suppose that (a) Assumptions 1, 2, and 5 hold; and (b) the step-size sequence {α[k]} is selected such that α[k]∈0,1, for all k,(20)∑k=0∞αk=∞,∑k=0∞αk2<∞.Then, (i) the sequence {x¯[k]} is bounded and all its limit points are stationary solutions of problem (1); (ii) all the sequences {xi[k]} asymptotically agree; that is, xi[k]-x¯[k]→0 as k→∞, for all i=1,…,N.Proof.
See Appendix(3).Remark 8.
(1) On the choice of surrogate functions, we only present several instances to show how to choose the surrogate functionfi~; also see [16, 19, 22, 23].
(i) If any convex structure offi is unavailable, the linearization of fi at xi[k] is the most plain choice; that is,(21)fi~xi;xik=fixik+∇fixikTxi-xik+τi2xi-xik2.
(ii) Iffi is convex, one can just set(22)fi~xi;xik=fixik+τi2xi-xik2.
(iii) Consider the case wherefi can be decomposed as fi(xi)=fi(1)(xi)+fi(2)(xi), where fi(1) is convex and fi(2) is nonconvex. We can only linearize fi(2) and preserve the convex fi(1) as follows:(23)fi~xi;xik=fi1xi+fi2xik+τi2xi-xik2+∇fi2xikTxi-xik.
(2) On the choice of step-sizes, condition (20) in Theorem 7 requires that the step-size sequence reduces to zero, but not too fast. The choice of the step-size α[k] meeting (20) is quite flexible [1, 23]. The following two choices of step-size are very effective in our simulations:(i)α[k]=α0/(k+1)β, α0>0,0.5<β≤1;(ii)α[k]=α[k-1](1-μα[k-1]), α[0]∈(0,1], μ∈(0,1).(3) On the choice of weigh matrices, Assumption1 requires that each communication weigh matrix A[k] is doubly stochastic. References [4, 5] provided several choices of weigh matrices, such as the maximum degree weigh matrix, the Metropolis-Hastings weigh matrix, and the least-mean square consensus weight matrix.


## 5. Numerical Simulations

We consider a distributed nonconvex quadratic problem with quadratic inequality constraints (also see Example  C in [22]):(24)minx∈KFx≔∑i=1NAix-ai2-qix2s.t.xTBx-b≤0,where Ai∈Rd×d, ai∈Rd, B∈Rd×d, qi and b are nonnegative constants, and K is a box constraint in Rd. Note that the function fi(x)≔Aix-ai2-qix2 is locally accessible, only known by agent i. The local function fi is differentiable, and its gradient ∇fi is Li-Lipschitz continuous with Li=(AiTAi-qi·I)T(AiTAi-qi·I), where I is a unit matrix.The corresponding penalized problem for problem (24) is given by(25)minx∈KFcx≔∑i=1NAix-ai2-qix2+c·max⁡0,xTBx-b,where the penalty parameter c>0 is chosen suitably. In general, there are two ways to choose c such that it satisfies the requirement. One way is by solving the unconstrained optimization problem defined in (12), and the other one is by heuristic. In order to imitate the time-varying weight matrix, a pool of 50 weight matrices from connected random graphs are generated, in which each weight matrix is satisfied (Assumption 1). The time-varying weight matrices required in Steps  6(a) and 6(b) of Algorithm 1 are randomly drawn from the above pool. To compare, we use the distributed Lagrangian primal-dual subgradient (DLPDS, for short) algorithm proposed in [14] to solve the corresponding subproblem (9).For simplicity, we assume that eachAi is a diagonal matrix with elements generated randomly in (0,1], ai is a vector with elements generated randomly in (0,1], qi is generated randomly in [1,2], B is a diagonal matrix with elements generated randomly in (0,1], b is generated randomly in (0,10], and the initial points xi[0] are generated randomly in K, where the box constraint is set as K=[-2,2]d. In the numerical experiments, we heuristically select the penalty parameter c=10.Some experimental results are presented to illustrate the convergence behavior of the proposed Algorithm EPDA. All the curves are averaged over 20 independent realizations. Some comparisons with existing Algorithm DLPDS are also given.Figures1(a) and 2(a) depict the value of max error maxi{xik-x~ik/x~ik} versus the number of iterations with different nodes and dimensions. It can be observed that both algorithms have the potential to converge to the same stationary solution. However, our Algorithm EPDA is much faster than Algorithm DLPDS [14]. As can be seen from Figure 1(a), Algorithm EPDA can reach higher precision than Algorithm DLPDS after 400 iterations. Figure 2(a) shows the similar results when N=100 and d=10.Figure 1
Numerical results for nodes of the networkN=50 and dimensions of the problem d=5.
(a)
Max error versus number of iterations
(b)
Function value versus number of iterationsFigure 2
Numerical results for nodes of the networkN=100 and dimensions of problem d=10.
(a)
Max error versus number of iterations
(b)
Function value versus number of iterationsFigures1(b) and 2(b) depict the value of function F(x[k]) versus the number of iterations with different nodes and dimensions. For two tested cases, the value of the objective function gradually decreases when the number of iterations increases, but the value of the objective function for Algorithm EPDA reduces faster than that of Algorithm DLPDS.


## 6. Conclusions

In this paper, a distributed algorithm was proposed to solve the nonconvex distributed optimization with global inequality constraints over time-varying multiagent networks. The proposed algorithm was based on the successive convex approximation technique, exact penalty function method, and dynamic averaging consensus. The convergence of the proposed algorithm was proved. Several numerical results showed the effectiveness of the proposed method.



---

*Source: 3610283-2017-12-05.xml*