Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory

By Gesualdo Scutari, Francisco Facchinei, Lorenzo Lampariello. 2016

297 citations recorded by the source corpus.

In this two-part paper, we propose a general algorithmic framework for the minimization of a nonconvex smooth function subject to nonconvex smooth constraints, and also consider extensions to some structured, nonsmooth problems. The algorithm solves a sequence of (separable) strongly convex problems and maintains feasibility at each iteration. Convergence to a stationary solution of the original nonconvex optimization is established. Our framework is very general and flexible and unifies several existing successive convex approximation (SCA)-based algorithms. More importantly, and differently from current SCA approaches, it naturally leads to distributed and parallelizable implementations for a large class of nonconvex problems. This Part I is devoted to the description of the framework in its generality. In Part II, we customize our general methods to several (multiagent) optimization problems in communications, networking, and machine learning; the result is a new class of centralized and distributed algorithms that compare favorably to existing ad-hoc (centralized) schemes.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “Recently, there have been some works which study non-convex decentralized consensus optimization and establish convergence to a stationary point (Zeng and Yin, 2018; Hong et al., 2017, 2018; Sun and Hong, 2018; Scutari et al., 2017; Scutari and Sun, 2018; Jiang et al., 2017; Lian et al., 2017a).”
Federated Learning Over Wireless Networks: Convergence Analysis and Resource Allocation (2019, methodology): “4) FEDL Solution: Since we can obtain the stationary points of SUB3 using Successive Convex Approximation techniques such as NOVA [34], then we have:”
On the Total Energy Efficiency of Cell-Free Massive MIMO (2017, methodology): “That is, the right hand side of (33) is a proper convex bound in light of SCA [23], [24].”
Joint Task Offloading and Resource Allocation in UAV-Enabled Mobile Edge Computing (2020, methodology): “The convergence of Algorithm 1 is guaranteed if the step size θ( k ) is chosen so that θ( k ) ∈ ( 0 , 1], θ( k ) → 0, and (cid:24) v θ( k ) = ∞ , then ψ ( k ) is bounded and at least one of its limit points is stationary [38].”