# Distributed Constraint Optimization with Flocking Behavior

Authors: Zhengquan Yang; Qing Zhang; Zengqiang Chen
Journal: Complexity
 (2018)

---

## Abstract

This paper studies distributed optimization having flocking behavior and local constraint set. Multiagent systems with continuous-time and second-order dynamics are studied. Each agent has a local constraint set and a local objective function, which are known to only one agent. The objective is for multiple agents to optimize a sum of the local functions with local interaction and information. First, a bounded potential function to construct the controller is given and a distributed optimization algorithm that makes a group of agents avoid collisions during the evolution is presented. Then, it is proved that all agents track the optimal velocity while avoiding collisions. The proof of the main result is divided into three steps: global set convergence, consensus analysis, and optimal set convergence. Finally, a simulation is included to illustrate the results.


---

## Body

## 1. Introduction

The study of distributed optimization of multiagent has attracted extensive attention in recent years. The objective of distributed optimization is to optimize the sum of local functions with local interaction and information. Both unconstraint and constraint models of distributed optimization problems were researched. Nedic et al. [1] firstly gave a distributed subgradient algorithm to investigate unconstrained distributed optimization problems and proved that all agents optimize the sum of local functions over a time-varying graph. Wang et al. [2] firstly introduced a continuous-time algorithm with undirected topology. Rahili et al. [3] studied a distributed optimization problem with single-order and second-order dynamics, in which the local function is time-varying. Zhao [4] studied a distributed continuous-time optimization problem for general linear multiagent systems. Under edge- and node-based frameworks, respectively, they developed two adaptive algorithms to minimize the team performance function. Yang et al. [5] studied distributed unconstraint optimization with flocking. A distributed adaptive protocol for multiagent was proposed to realise flocking behavior. For distributed constraint optimization problems, there are also some results. Nedic et al. [6] presented a distributed projected subgradient algorithm for the constraint optimization problem and researched its convergence properties. Some modified or extended models of distributed constrain optimization were also given [7–16]. Qiu et al. [8] studied a distributed convex optimization of continuous-time dynamics with a common state set constraint. They noted that if the time-varying gains of the gradients satisfy a persistence condition, the states of all agents converge to the optimal point of the set constraints. Lin et al. [9] proposed a nonuniform gradient gain control method and a finite-time control method for distributed constraint optimization. Zeng et al. [10] studied nonsmooth convex optimization problem and proposed a distributed continuous-time algorithm by combining primal-dual methods for saddle point seeking and projection methods for set constraints. Lin [11] devoted to distributed optimization problems with nonuniform convex constraint sets and nonuniform step-sizes. Liu and Wang [12] proposed a group of coupled two-layer projection networks with bounded constraint. Li et al. [13] gave a distributed discrete-time control law for solving the nonconvex problem with inequality constraints. They transformed the nonconvex problem into a sequence of strongly convex subproblems through continuous convex approximation technique. Zhang et al. [14] optimized a sum of convex functions defined over a graph, where every edge in the graph carried a linear equality constraint. Hong et al. [15] studied two first-order primal-dual based algorithms, the Gradient Primal-Dual Algorithm and the Gradient Alternating Direction Method of Multipliers, for solving a class of linearly constrained nonconvex optimization problems. Gu et al. [16] proposed a solution tool for distributed convex problems with coupling equality constraints. The proposed algorithm was implemented time-changing directed networks.As is known to all, there are a great number of results about distributed optimization. However, the distributed optimization with flocking behavior is rarely considered. Flocking problem is a significant issue considered by many researchers [17–25]. The purpose of flocking problem is to control a group of agents to move by local information while maintaining connectivity, avoiding collisions, and having the same speed. Nevertheless, the above results can not be directly applied to more complex flocking problems. In this paper, a distributed optimization problem while considering the flocking behavior is researched. The aim of this paper is to solve that problem with local constraint set. Due to the coexistence of constraint sets, flocking behavior, and optimization objectives, there are great challenges in the research. There are three major contributions in this manuscript. Firstly, a bounded potential function is used to construct the controller that makes a group of agents avoid collisions during the evolution. Secondly, our proposed control law lets the velocity sate converge to the local constraint set in finite time. Thirdly, the control law is proved to be correct in three aspects.An outline of the paper is as follows. The notations and some essential concepts used in this paper are given in Section2. In Section 3, we formulate the distributed constrained optimization with flocking behavior. In Section 4, we shown the main result and prove the main result in three steps. In Section 5, a simulation example is presented. Finally, conclusions are made in Section 6.


## 2. Notations and Preliminaries

Notations. The identity matrix in Rn×n is denoted by In. The index set {1,2,…,N} is denoted by N. A⊗B is the Kronecker product of A and B. sgn(s) is a component wise sign function of s. The gradient of f(s) at s is denoted by ∇f(s). The Euclidean norm of the vector s is denoted by s. s1 denotes the 1-norm of the vector s. PX(s) denotes the projection of the vector s onto the closed convex set X; i.e., PX(s)=arg⁡mins¯∈Xs-s¯.An a dynamic undirected graphG(t) is considered in this paper, having a node set V={1,2,…,N} and set of links E(t). (i,j)∈E(t) means that node j is a neighbor of node i. The neighbors of vertex i are given by Ni={j:∈V:(i,j)∈E}. The adjacency matrix of the graph G is A(t)=[aij(t)]∈RN×N which is denoted as aii(t)=0, aij(t)=aji(t)=1 if (i,j)∈E(t); otherwise aij(t)=0. By arbitrarily assigning an orientation for the edges in G(t), using D(t)=[dik(t)]∈RN×|E(t)| represents the incidence matrix associated with the graph G(t), where dik(t)=-1 if the edge ek leaves node i and dik(t)=1 if it enters node i, and dik(t)=0 otherwise. The Laplacian of G(t) is denoted by L(t)=Λ-A(t), where Λ(t)=diag{d1(t),d2(t),…,dN(t)}∈RN×N is the degree matrix of G(t) with di(t)=∑j=1,j≠iNaij(t) for i∈N. Note that, for undirected graphs, Laplacian matrix L(t) is a symmetric matrix satisfying L(t)=D(t)DT(t), and when the graph G(t) is connected, the eigenvalues of L(t) have order as λ1(L(t))=0<λ2(L(t))≤…≤λN(L(t)).Lemma 1 (see [26]).
Suppose thatX≠∅ is closed convex set in Rn. Then, for any s∈Rn, s-PX(s) is continuous with respect to y and ∇1/2s-PXs2=s-PX(s).Lemma 2 (see [27]).
Let functionf(s):Rn→R be a differentiable and convex function. For any s1, s2∈Rn(1)fs1-fs2≥∇fs2Ts1-s2


## 3. Problem Formulation

We considerN multiagents operating in Rn, with dynamics expressed by double integrators(2)x˙i=viv˙i=ui,i∈Nwhere xi∈Rn is the position vector of agent i, vi∈Rn is the velocity vector, and ui∈Rn is the control input acting on agent i. A local cost function fi(v):Rn→R is assigned to agent i( i∈N), and it is known to only agent i. The global cost function is denoted by(3)fv=∑i=1Nfiv.The topology graph studied in this paper is dynamic. In the remaining parts of this paper, the dynamic undirected graph, the adjacency matrix, the incidence matrix, and the Laplacian matrix on timet are simply remarked as G, A, D, and L, respectively. In the dynamic graph, we assume (i,j)∈E if and only if xi-xj<R, where R>0 is the communication radius of an agent.The aim of this paper is to design the controllerui for system (2) using local function and local information gathered from neighbors such that all agents track the optimal velocity v∗(t) while maintaining connectivity and avoiding collisions. The optimal velocity v∗(t) satisfies(4)minimizefv=∑i=1Nfivsubjectv∈Ω=⋂i=1NΩi⊂Rnwhere Ωi is the local constraint set, and it is closed and convex. Let X⊂Ω denote the optimal set of problem (4).The problem defined in (4) is equivalent to(5)minimize∑i=1Nfivisubjectv1=v2=⋯=vN,vi∈Ωi.To ensure problem (4), the following assumptions are needed.Assumption 3.
Each functionfi(v) is strictly convex and differentiable. Let ∇fi(v)=σv+gi(v),∀i∈N, where σ≥0, gi(v) is a continuous function satisfying gi(t)<g for a certain positive number g and all t.BecauseΩi is a closed convex set, there is a constant s>0, which makes x≤s,∀x∈Ωi. Moreover, if the function f(v) is convex and differentiable, and the constrained set Ω is convex and closed; we can get the optimal solution set X∈Ω of problem (4) is nonempty, closed, and bounded.In order to smooth the controller, we adopt the norm that firstly presented in [21](6)zσ=1+z2-1The function zσ, unlike the norm z which is not differentiable at z=0, is differentiable everywhere. The gradient of zσ is given by(7)∇zσ=z1+z2=z1+zσ2To propose a controller law for collision avoidance, we need to give a smooth collective potential functionVij.Definition 4.
The potential functionVij is a differentiable nonnegative function of xi-xjσ which satisfies the following conditions.
( 1 )   V i j = V j i has a unique minimum in xi-xj=d, where d is a desired distance between agents i and j and 0<d<R, and R>0 is a constant.
( 2 )   ∂ V i j / ∂ ( x i - x j σ ) is continuous, satisfying (8)∂Vij∂xi-xjσ≤0,0≤xi-xjσ<dσ∂Vij∂xi-xjσ≥0,dσ≤xi-xjσ≤Rσ∂Vij∂xi-xjσ=0,Rσ<xi-xjσRemark 5.
There are many potential functions satisfying Definition4, such as the potential functions defined in [21].Remark 6.
From the characteristic of function∂Vij/∂(xi-xjσ), especially the continuity in interval [0,Rσ), we know that function ∂Vij/∂(xi-xjσ)) is bounded. So ∇xiVij=(∂Vij/∂xi-xjσ)((xi-xj)/1+xi-xj2) is also bounded, for xi-xj∈[0,R). Thus, there is a constant Q>0, such that ∇xiVij≤Q,xi-xj∈[0,R).To solve our objective of this paper, we present the algorithm.(9)uit=-∑j∈Ni∇xiVij-α∑j∈Niaijsgnvi-vj-∇fivi-βvi-PΩivivi-PΩivi.where α and β are positive constants and PΩi(·) is the projection onto Ωi. It is worth pointing out that ∇fi(vi) depends on only agent i’s velocity.Remark 7.
In (9), the first term is used to regulate position between agent i and its neighbors; this term is responsible for collision avoidance and cohesion in the group, the second term is to the desired velocity alignment, the third term is a negative gradient fi(vi), and the fourth term is used to pull the velocity vector onto Ωi.


## 4. Main Theorem and Convergence Analysis

We give the main theorem of this paper and propose the convergence of the control law in this subsection. First, we give the main result of this paper as follows.Theorem 8.
Assume that the graphG(t) is connected for all t and Assumption 3 holds. For system (2) with algorithm (9), if all α>4Φ/λ2(L) and β>QN+αN+s+g, the agents’ velocities in the group track the optimal velocity and the agents avoid interagent collisions..In the following, we are interested in proving Theorem8. In order to do so, first, we have to verify global set convergence, second, we have to give consensus analysis, and third we have to prove all agents converge to the optimal set.Proof.
First, to verify global set convergence, let us consider the Lyapunov function candidate:(10)V1t=12∑i=1Nvi-PΩivi2.(11)V˙1t=∑i=1Nvi-PΩiviTvi=∑i=1Nvi-PΩiviT-∑j∈Ni∇xiVij-α∑j∈Niaijsgnvi-vj-∇fivi-βvi-PΩivivi-PΩivi≤NQ+αN-β∑i=1Nvi-PΩivi-∑i=1Nvi-PΩiviTσvi+givi=NQ+αN-β∑i=1Nvi-PΩivi-σ∑i=1Nvi-PΩivi2+∑i=1Nvi-PΩiviTPΩivi+givi≤NQ+αN-β∑i=1Nvi-PΩivi+∑i=1Nvi-PΩivis+g=-β-NQ+αN+s+gV1tIn the above prove, we have used the fact PΩi(vi)∈Ωi and PΩi(vi)≤s. From (11), it follows that (12)V˙1tV1t≤-β-NQ+αN+s+g We integrate on both sides of inequality and get the following inequality (13)V1t-V1t0≤-β-NQ+αN+s+gt-t0Thus, V1(t) converges to zero in finite time. Namely, there is a constant t1>t0, such that for all t>t1, vi-PΩ(vi)=0. That is, under control (9), vi(t)∈Ωi for all t>t1.
Second, we will present the consensus analysis. From the above proof, for allt>t1, we can get vi(t)∈Ωi and(14)x˙it=vitv˙it=-∑j∈Ni∇xiVij-α∑j∈Niaijsgnvi-vj-∇fivi,i=1,2,⋯,N.
From Assumption3 we can get ∇fi(vi) is continuous. When Ω is a bounded closed convex set, from the property of continuous functions on closed bounded sets, we can get ∇fi(vi) is upper bounded on Ωi. So there is a constant M>0, such that(15)∇fivi≤M,∀t>t1
For allt>t1, consider the Lyapunov function candidate(16)V2=12∑i=1N∑j∈NiVij+12∑i=1NviTvi
Note, however, that, due to the symmetric nature ofVij, (17)12∑i=1N∑j∈NiV˙ij=12∑i=1N∑j∈Nix˙ijT∇xijVij=∑i=1N∑j∈NiviT∇xiVij
So, taking time derivative ofV2, we can get(18)V˙2=12∑i=1N∑j∈NiV˙ij+∑i=1NviTv˙i=∑i=1N∑j∈NiviT∇xiVij+∑i=1NviT-∑j∈Ni∇xiVij-α∑j∈Niaijsgnvi-vj-∇fivi=-α∑i=1NviT∑j∈Niaijsgnvi-vj-∑i=1NviT∇fiviBecause aij=aji=1, if (i,j)∈E, we have(19)∑i=1NviT∑j∈Niaijsgnvi-vj=∑i=1N∑j=1NaijviTsgnvi-vj=12∑i=1N∑j=1NaijviTsgnvi-vj+∑i=1N∑j=1NaijviTsgnvi-vj=12∑i=1N∑j=1NaijviTsgnvi-vj+∑i=1N∑j=1NajivjTsgnvj-vi=12∑i=1N∑j=1Naijvi-vjTsgnvi-vjThus, (18) can be rewritten by(20)V˙2=-α2∑i=1N∑j=1Naijvi-vjTsgnvi-vj-∑i=1NviT∇fiviIf we let V=(v1T,v2T,⋯,vNT)T, Φ=(ϕ1T,ϕ2T,⋯,ϕNT)T, then the above equation can be rewritten as(21)V˙1=-α4DTV1-α4DTV1-VTΦ≤-α4DTV1-α4VTDDT⊗ImV+V2Φ2≤-α4DTV1-α4λ2LV2+V2Φ2=-α4DTV1-α4λ2L-Φ2V2
Letϕ=∇fi(vi,t); we know ϕ is upper bounded and Φ2 is upper bounded ∀t>t1. So if α>4Φ/λ2(L), we can get (22)V˙2<-α4DTV1=-α4∑i=1N∑j=1Naijvi-vj1≤0
By LaSalle’s invariance principle, we can getv1(t)=v2(t)=⋯=vN(t)∈Ω=⋂i=1NΩi as t→∞, which implies that the velocities of all agents in system (2) asymptotically become the same.If we letv¯=(1/N)∑i=1Nvi, from the above proof we can get vi(t)=v¯ as t→∞. So for any ε>0, there exists a time tε (tε>t1), such that vi, v¯∈Ω, and(23)vi-v¯<εNM∀t≥tε.From the convexity of the functionfi(vi) and (15), we have(24)∑i=1Nfiv¯-fivi=∑i=1N∇fiviTv¯-v≤∑i=1N∇fiviv¯-v<ε,∀t≥tε.So for allt>tε, (14) and (24) hold.Fort>tε, denote(25)V3t=12∑i=1Nvi-PXv¯2+12∑i=1N∑j∈NiVij.Similar to the proof of above, we have(26)V˙3t=-α∑i=1N∑j∈Niaijvi-vjTsgnvi-vj-∑i=1Nvi-PXv¯T∇fivi≤∑i=1NPXv¯-viT∇fivi≤∑i=1NfiPXv¯-fivi=∑i=1NfiPXv¯-fiv¯+∑i=1Nfiv¯-fivi=fPXv¯-fv¯+∑i=1Nfiv¯-fivi<fPXv¯-fv¯+ε≤εIn view of the arbitrariness of ε, let ε→0; we have V˙3(t)<[f(PX(v¯))-f(v¯)]≤0 for t>t2. By LaSalle’s invariance principle and the unique global minimum of f(v) on Ω, we can get limt→∞vi-PX(v¯)=0. That is, the global cost function (4) is minimized as t→∞.Remark 9.
Compared with the distributed optimization with a common constraint [18–20], we extended the control law to distributed optimization with local constraints. Besides, the result of [8] requires time-varying gains of the gradients to satisfy a persistence condition, and the gains conditions of this paper are relatively easy to satisfy. Compared with the control law in [10, 12], the control law this paper is relatively simple. Moreover this paper addresses the issue of distributed optimization problem having flocking and local constraint set.


## 5. Simulation

In this section, a numerical example is presented to verify the feasibility of the proposed algorithm and correctness of our theoretical analysis.For giving the potential functionVij, we choose the action function ϕ(z) as follows: (27)ϕz=z-dσ1+z-dσ2,0≤z<Rσ0,otherwise which satisfies condition (2) in Definition 4The corresponding repulsive potential function is(28)ψz=∫dσzϕsdsThe following parameters remain fixed through the simulation:d=3 and R=5. The potential function ψ(z) has the shape as in Figure 1.Figure 1
Shape of the bounded potential functionψ(z).Then, we choose the potential functionVij satisfying Definition 4 as follows: (29)Vij=ψxi-xjσ=∫dσxi-xjσϕsdsIn the illustration, we consideredN=8 agents in a 2D plane. The task of the multiagent is to enable their velocities to minimize the total cost function ∑i=18fi(vi(t)), where vi(t)=(vi1(t),vi2(t))T is the coordinate of agent i. We consider the second-order dynamic system (2) with the control algorithm (9). The local cost functions are given by f1(v1)=(1/2)v112+(1/2)v122, f2(v2)=(1/2)(v21+1)2+(1/2)v222, f3(v3)=(1/2)v312+(1/2)(v32+1)2, f4(v4)=(1/2)(v41+1)2+(1/2)(v42+1)2, f5(v5)=(1/2)v512+(1/2)v522, f6(v6)=(1/2)(v61+1)4+(1/2)v624, f7(v7)=(1/2)v714+(1/2)(v72+1)4, and f8(v8)=(1/2)v814+(1/2)(v82+1)4. Those local functions are used in [9]. We assume that the local constraint set is a square, which is given by Ωi={v∈R2:-2-(i-1)∗0.05≤vij≤-0.6-(i-7)∗0.05},i∈N,j=1,2. It is observed from the above local cost functions and local constraint set that Assumption 3 is satisfied. Figures of the local constraint set Ωi and the intersection Ω are plotted in Figure 2. Through simple calculations, we have that the global function f(v)=∑i=18fi(v) is minimized if and only if v=[-0.5-0.5]T. Since v=[-0.5-0.5]T∉Ω, the objection function (4) must have at least one optimal point at the boundary of Ω. By calculating the values of f(v)=∑i=18fi(v) along the constraint set Ω, we have that v∗=[-0.6,-0.6]T is the optimal points of the objective function (4).Figure 2
The local constraint setΩi and the intersection Ω.The simulation results are shown in Figures3–5. For simplicity, we choose the coefficients in algorithm (9) as α=1, β=20. Figure 3 demonstrates the initial state of the group including initial positions and velocities. All initial positions are set on a line and all initial velocities are set with arbitrary directions and magnitudes within the range of [-1,1] m/s. Figure 4 gives the final steady state configuration and the final velocity of the agent group where the solid lines represent the neighboring relations between agents and the dotted arrows represent the velocities of all agents. Figure 5 plots the velocity vi,i∈N. It is easy to see that the flocking motion can be obtained and the velocities of all agents converge to the velocity of the optimal velocity.Figure 3
Initial configuration of all agents.Figure 4
Final configuration of all agents.Figure 5
Velocities of all agents.


## 6. Conclusion

We studied distributed optimization with flocking and constraint set in this paper. Multiagent systems with continuous-time and second-order dynamics are considered. Each agent has a local constraint set and a local objective function which is known to only one agent. The objective is for multiple agents to optimize a sum of the local functions with local interaction and information. First, a bounded potential function to construct the controller is given and the distributed constrained optimization algorithm is presented that make all agents avoid collisions during the evolution. Then, it is proved that all agents can track the optimal velocity while avoiding the interagent collision. The proof of the main result is divided into three steps: global set convergence, consensus analysis, and optimal set convergence. Finally, a simulation is included to illustrate the results.



---

*Source: 1579865-2018-12-11.xml*