Distributed Convex Optimization via Continuous time Kia

• Access throughyour institution

Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication☆

Abstract

This paper proposes a novel class of distributed continuous-time coordination algorithms to solve network optimization problems whose cost function is a sum of local cost functions associated to the individual agents. We establish the exponential convergence of the proposed algorithm under (i) strongly connected and weight-balanced digraph topologies when the local costs are strongly convex with globally Lipschitz gradients, and (ii) connected graph topologies when the local costs are strongly convex with locally Lipschitz gradients. When the local cost functions are convex and the global cost function is strictly convex, we establish asymptotic convergence under connected graph topologies. We also characterize the algorithm's correctness under time-varying interaction topologies and study its privacy preservation properties. Motivated by practical considerations, we analyze the algorithm implementation with discrete-time communication. We provide an upper bound on the stepsize that guarantees exponential convergence over connected graphs for implementations with periodic communication. Building on this result, we design a provably-correct centralized event-triggered communication scheme that is free of Zeno behavior. Finally, we develop a distributed, asynchronous event-triggered communication scheme that is also free of Zeno with asymptotic convergence guarantees. Several simulations illustrate our results.

Introduction

An important class of distributed convex optimization problems consists of the (un-)constrained network optimization of a sum of convex functions, each one representing a local cost known to an individual agent. Examples include distributed parameter estimation (Ram et al., 2010, Wan and Lemmon, 2009), statistical learning (Boyd, Parikh, Chu, Peleato, & Eckstein, 2010), and optimal resource allocation over networks (Madan & Lall, 2006). To find the network optimizers, we propose a coordination model where each agent runs a purely local continuous-time evolution dynamics and communicates at discrete instants with its neighbors. We are motivated by the desire of combining the conceptual ease of the analysis of continuous-time dynamics and the practical constraints imposed by real-time implementations. Our design is based on a novel continuous-time distributed algorithm whose stability can be analyzed through standard Lyapunov functions.

Literature review: In distributed convex optimization, most coordination algorithms are time-varying, consensus-based dynamics (Boyd et al., 2010, Duchi et al., 2012, Johansson et al., 2009, Nedić and Ozdaglar, 2009, Zhu and Martínez, 2012) implemented in discrete time. Recent work (Gharesifard and Cortés, 2014, Lu and Tang, 2012, Wang and Elia, 2011, Zanella et al., 2011) has introduced continuous-time dynamical solvers whose convergence properties can be analyzed via classical stability analysis. This has the added advantage of facilitating the characterization of properties such as speed of convergence, disturbance rejection, and robustness to uncertainty. Wang and Elia (2011) establish asymptotic convergence under connected graphs and Gharesifard and Cortés (2014) extend the design and analysis to strongly connected, weight-balanced digraphs. The continuous-time algorithms in Lu and Tang (2012) and Zanella et al. (2011) require twice-differentiable, strictly convex local cost functions to make use of the inverse of their Hessian and need a careful initialization to guarantee asymptotic convergence under undirected connected graphs. The novel class of continuous-time algorithms proposed here (upon which our implementations with discrete-time communication are built) do not suffer from the limitations discussed above and have, under some regularity assumptions, exponential convergence guarantees. Our work here also touches, albeit slightly, on the concept of privacy preservation, see e.g., Weeraddana, Athanasiou, Fischione, and Baras (2013) and Yan, Sundaram, Vishwanathan, and Qi (2013) for recent works in the context of distributed multi-agent optimization. Regarding event-triggered control of networked systems, recent years have seen an increasing body of work that seeks to trade computation and decision making for less communication, sensing or actuator effort, see e.g. Heemels, Johansson, and Tabuada (2012), Mazo and Tabuada (2011) and Wang and Lemmon (2011). Closest to the problem considered here are works that study event-triggered communication laws for average consensus, see e.g., Dimarogonas, Frazzoli, and Johansson (2012), Garcia, Cao, Yuc, Antsaklis, and Casbeer (2013) and Nowzari and Cortés (submitted for publication). The strategies proposed in Wan and Lemmon (2009) save communication effort in discrete-time implementations by using local triggering events but are not guaranteed to avoid Zeno behavior, i.e., an infinite number of triggered events in a finite period of time. Our goal is to combine the best of both approaches by synthesizing provably-correct continuous-time distributed dynamical systems which only require communication with neighbors at discrete instants of time. We are particularly interested in the opportunistic determination of this communication times via event triggering schemes.

Statement of contributions: We propose a novel class of continuous-time, gradient-based distributed algorithms for network optimization where the global objective function is the sum of local cost functions, one per agent. We prove that these algorithms converge exponentially under strongly connected and weight-balanced agent interactions when the local cost functions are strongly convex and their gradients are globally Lipschitz. Under connected, undirected graphs, we establish exponential convergence when the local gradients are just locally Lipschitz, and asymptotic convergence when the local cost functions are simply convex and the global cost function is strictly convex. We also study convergence under networks with time-varying topologies and characterize the topological requirements on the communication graph, algorithm parameters, and initial conditions necessary for an agent to reconstruct the local gradients of local cost functions of other agents. Our technical approach builds on the identification of strict Lyapunov functions. The availability of these functions enable our ensuing design of provably-correct continuous-time implementations with discrete-time communication. In particular, for networks with connected graph topologies, we obtain an upper bound on the suitable stepsizes that guarantee exponential convergence under periodic communication. Building on this result, we design a centralized, synchronous event-triggered communication scheme with an exponential convergence guarantees and Zeno-free behavior. Finally, we develop a Zeno-free asynchronous event-triggered communication scheme whose execution only requires agents to interchange information with their neighbors and establish its exponential convergence to a neighborhood of the network optimizer. Several simulations illustrate our results.

Section snippets

Preliminaries

In this section, we introduce our notation and some basic concepts from convex functions and graph theory. Let $\mathbb{R}$ and ${\mathbb{Z}}_{\ge 0}$ denote, respectively, the set of real and nonnegative integer numbers. We use $\Re (\cdot )$ to represent the real part of a complex number. The transpose of a matrix $A$ is $A^{\top }$ . We let $1_n$ (resp. $0_n$ ) denote the vector of $n$ ones (resp. $n$ zeros), and denote by $I_n$ the $n\times n$ identity matrix. We let ${\Pi }_n=I_n-\frac{1}{n}{1}_n{1}_n^{\top }$ . When clear from the context, we do not specify the matrix dimensions. For $A\in {\mathbb{R}}^{n\times m}$

Problem definition

Consider a network of $N$ agents interacting over a strongly connected and weight-balanced digraph $\mathcal{G}$ . Each agent $i\in \mathcal{V}$ has a differentiable local cost function $f^i:{\mathbb{R}}^d\to \mathbb{R}$ . The global cost function of the network, which we assume to be strictly convex, is $f={\Sigma }_{i=1}^N{f}^i\left(x\right)$ . Our aim is to design a distributed algorithm such that each agent solves $\underset{x\in {\mathbb{R}}^d}{min}f\left(x\right)$ using only its own local data and exchanged information with its neighbors. We assume the above optimization problem is feasible (which, together with

Distributed continuous-time algorithm for convex optimization

In this section, we provide a novel continuous-time distributed coordination algorithm to solve the problem stated in Section  3 and analyze in detail its convergence properties. For $i\in \mathcal{V}$ and with $\alpha ,\beta >0$ , consider ${\dot{v}}^i=\alpha \beta \sum _{j=1}^N{a}_{ij}(x^i-x^j)\text{,}$ ${\dot{x}}^i=-\alpha \nabla f^i\left(x^i\right)-\beta \sum _{j=1}^N{a}_{ij}(x^i-x^j)-v^i\text{.}$ In network variables $x,v\in {\left({\mathbb{R}}^d\right)}^N$ , the algorithm reads as $\dot{v}=\alpha \beta Lx\text{,}$ $\dot{x}=-\alpha \nabla \tilde{f}\left(x\right)-\beta Lx-v\text{.}$ Here, $\tilde{f}:{\left({\mathbb{R}}^d\right)}^N\to \mathbb{R}$ is defined by $\tilde{f}\left(x\right)={\Sigma }_{i=1}^N{f}^i\left(x^i\right)$ . This algorithm is distributed because each agent only needs to receive information from its

Continuous-time evolution with discrete-time communication

Here, we investigate the design of continuous-time coordination algorithms with discrete-time communication to solve the distributed optimization problem of Section  3. The implementation of (3) requires continuous-time communication among the agents. While this abstraction is useful for analysis, in practical scenarios communication is only available at discrete instants of time. This observation motivates our study here. Throughout the section, we deal with communication topologies described

Simulations

Here, we illustrate the performance of the algorithm (3) and its implementation with discrete-time communication (17). We consider a network of 10 agents, with strongly convex local cost functions on $\mathbb{R}$ given by $f^1\left(x\right)=0.5e^{-0.5x}+0.4e^{0.3x}\text{,}{f}^2\left(x\right)={(x-4)}^2\text{,}$ $f^3\left(x\right)=0.5x^{2}ln(1+x^2)+x^2\text{,}{f}^4\left(x\right)=x^2+e^{0.1x}\text{,}$ $f^5\left(x\right)=ln(e^{-0.1x}+e^{0.3x})+0.1x^2\text{,}{f}^6\left(x\right)=x^2/ln(2+x^2)\text{,}$ $f^7\left(x\right)=0.2e^{-0.2x}+0.4e^{0.4x}\text{,}{f}^8\left(x\right)=x^4+2x^2+2\text{,}$ $f^9\left(x\right)=x^2/\sqrt{x^2+1}+0.1x^2\text{,}{f}^{10}\left(x\right)={(x+2)}^2\text{.}$ The gradient of the cost function of agents 1, 4, 7, 8 are locally Lipschitz, while the

Conclusions

We have presented a novel class of distributed continuous-time coordination algorithms that solve network optimization problems where the objective function is strictly convex and equal to a sum of local agent cost functions. For strongly connected and weight-balanced agent interactions, we have shown that our algorithms converge exponentially to the solution of the optimization problem when the local cost functions are strongly convex and their gradients are globally Lipschitz. This property

Acknowledgments

The second author is thankful to Cameron Nowzari for discussions on event-triggered control and distributed optimization. This work was supported by L3 Communications through the UCSD Cymer Center for Control Systems and Dynamics and NSF award ECCS-1307176.

Solmaz S. Kia is an Assistant Professor in the Department of Mechanical and Aerospace Engineering, University of California, Irvine (UCI). She obtained her Ph.D. degree in Mechanical and Aerospace Engineering from UCI, in 2009, and her M.Sc. and B.Sc. in Aerospace Engineering from the Sharif University of Technology, Iran, in 2004 and 2001, respectively. She was a senior research engineer at SySense Inc., El Segundo, CA from Jun. 2009–Sep. 2010. She held postdoctoral positions in the Department

References (25)

• et al.

  Decentralized estimation and control of graph connectivity for mobile sensor networks

  Automatica

  (2010)

• S. Boyd et al.

  Distributed optimization and statistical learning via the alternating direction method of multipliers

  Foundations and Trends in Machine Learning

  (2010)

• F. Bullo et al.
• D.V. Dimarogonas et al.

  Distributed event-triggered control for multi-agent systems

  IEEE Transactions on Automatic Control

  (2012)

• M.C.F. Donkers et al.

  Output-based event-triggered control with guaranteed ${\mathcal{L}}_{\infty }$ -gain and improved and decentralized event-triggering

  IEEE Transactions on Automatic Control

  (2012)

• J. Duchi et al.

  Dual averaging for distributed optimization: convergence analysis and network scaling

  IEEE Transactions on Automatic Control

  (2012)

• E. Garcia et al.

  Decentralised event-triggered cooperative control with limited communication

  International Journal of Control

  (2013)

• B. Gharesifard et al.

  Distributed continuous-time convex optimization on weight-balanced digraphs

  IEEE Transactions on Automatic Control

  (2014)

• Heemels, W.P.M.H., Johansson, K.H., & Tabuada, P. (2012). An introduction to event-triggered and self-triggered...
• B. Johansson et al.

  A randomized incremental subgradient method for distributed optimization in networked systems

  SIAM Journal on Optimization

  (2009)

H.K. Khalil

Nonlinear systems

(2002)

J. Lu et al.

Zero-gradient-sum algorithms for distributed convex optimization: the continuous-time case

IEEE Transactions on Automatic Control

(2012)

Cited by (456)

Recommended articles (6)

Solmaz S. Kia is an Assistant Professor in the Department of Mechanical and Aerospace Engineering, University of California, Irvine (UCI). She obtained her Ph.D. degree in Mechanical and Aerospace Engineering from UCI, in 2009, and her M.Sc. and B.Sc. in Aerospace Engineering from the Sharif University of Technology, Iran, in 2004 and 2001, respectively. She was a senior research engineer at SySense Inc., El Segundo, CA from Jun. 2009–Sep. 2010. She held postdoctoral positions in the Department of Mechanical and Aerospace Engineering at the UC San Diego and UCI. She was the recipient of UC President's Postdoctoral Fellowship from 2012–2014. Dr. Kia's main research interests, in a broad sense, include distributed optimization/coordination/estimation, nonlinear control theory and probabilistic robotics.

Jorge Cortés received the Licenciatura degree in mathematics from Universidad de Zaragoza, Zaragoza, Spain, in 1997, and the Ph.D. degree in engineering mathematics from Universidad Carlos III de Madrid, Madrid, Spain, in 2001. He held postdoctoral positions with the University of Twente, Twente, The Netherlands, and the University of Illinois at Urbana–Champaign, Urbana, IL, USA. He was an Assistant Professor with the Department of Applied Mathematics and Statistics, University of California, Santa Cruz, CA, USA, from 2004 to 2007. He is currently a Professor in the Department of Mechanical and Aerospace Engineering, University of California, San Diego, CA, USA. He is the author of Geometric, Control and Numerical Aspects of Nonholonomic Systems (Springer-Verlag, 2002) and co-author (together with F. Bullo and S. Martinez) of Distributed Control of Robotic Networks (Princeton University Press, 2009). He is an IEEE Fellow and an IEEE Control Systems Society Distinguished Lecturer. His current research interests include distributed control, networked games, power networks, distributed optimization, spatial estimation, and geometric mechanics.

Sonia Martínez is a Professor with the Department of Mechanical and Aerospace Engineering at the University of California, San Diego. Dr. Martinez received her Ph.D. degree in Engineering Mathematics from the Universidad Carlos III de Madrid, Spain, in May 2002. Following a year as a Visiting Assistant Professor of Applied Mathematics at the Technical University of Catalonia, Spain, she obtained a Postdoctoral Fulbright Fellowship and held appointments at the Coordinated Science Laboratory of the University of Illinois, Urbana–Champaign during 2004, and at the Center for Control, Dynamical systems and Computation (CCDC) of the University of California, Santa Barbara during 2005. In a broad sense, Dr Martínez' main research interests include the control of networked systems, multi-agent systems, nonlinear control theory, and robotics. For her work on the control of underactuated mechanical systems she received the Best Student Paper award at the 2002 IEEE Conference on Decision and Control. She was the recipient of a NSF CAREER Award in 2007. For the paper "Motion coordination with Distributed Information", co-authored with Jorge Cortés and Francesco Bullo, she received the 2008 Control Systems Magazine Outstanding Paper Award. She has served on the editorial boards of the European Journal of Control (2011–2013), and currently serves on the editorial board of the Journal of Geometric Mechanics and IEEE Transactions on Control of Networked Systems.

View full text

Copyright © 2015 Elsevier Ltd. All rights reserved.

halebusucher.blogspot.com

Source: https://www.sciencedirect.com/science/article/pii/S0005109815001053