Back to Search
Start Over
Distributed nonconvex constrained optimization over time-varying digraphs
- Source :
- Mathematical Programming. 176:497-544
- Publication Year :
- 2019
- Publisher :
- Springer Science and Business Media LLC, 2019.
-
Abstract
- This paper considers nonconvex distributed constrained optimization over networks, modeled as directed (possibly time-varying) graphs. We introduce the first algorithmic framework for the minimization of the sum of a smooth nonconvex (nonseparable) function--the agent's sum-utility--plus a Difference-of-Convex (DC) function (with nonsmooth convex part). This general formulation arises in many applications, from statistical machine learning to engineering. The proposed distributed method combines successive convex approximation techniques with a judiciously designed perturbed push-sum consensus mechanism that aims to track locally the gradient of the (smooth part of the) sum-utility. Sublinear convergence rate is proved when a fixed step-size (possibly different among the agents) is employed whereas asymptotic convergence to stationary solutions is proved using a diminishing step-size. Numerical results show that our algorithms compare favorably with current schemes on both convex and nonconvex problems.<br />Comment: Submitted June 3, 2017, revised June 5, 2108. Part of this work has been presented at the 2016 Asilomar Conference on System, Signal and Computers and the 2017 IEEE ICASSP Conference
- Subjects :
- FOS: Computer and information sciences
Mathematical optimization
Sublinear function
General Mathematics
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Convergence (routing)
FOS: Mathematics
Computer Science - Multiagent Systems
0101 mathematics
Mathematics - Optimization and Control
Mathematics
021103 operations research
Numerical analysis
Regular polygon
Constrained optimization
Function (mathematics)
Computer Science - Distributed, Parallel, and Cluster Computing
Rate of convergence
Optimization and Control (math.OC)
Distributed, Parallel, and Cluster Computing (cs.DC)
Minification
Software
Multiagent Systems (cs.MA)
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 176
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....79819d366d23f00662defbf56c78a8f3