Distributed nonconvex constrained optimization over time-varying digraphs
From MaRDI portal
Publication:2425183
DOI10.1007/S10107-018-01357-WzbMATH Open1415.90130arXiv1809.01106OpenAlexW2892002891WikidataQ128388005 ScholiaQ128388005MaRDI QIDQ2425183FDOQ2425183
Authors: Gesualdo Scutari, Ying Sun 
Publication date: 26 June 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1809.01106
Recommendations
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs
- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Optimal Distributed Convex Optimization on Slowly Time-Varying Graphs
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Online Convex Optimization on Time-Varying Directed Graphs
- Distributed Continuous-Time Algorithms for Time-Varying Constrained Convex Optimization
- Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
- Distributed continuous‐time constrained convex optimization with general time‐varying cost functions
Numerical optimization and variational techniques (65K10) Applications of mathematical programming (90C90) Noncooperative games (91A10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Decomposition methods (49M27) Numerical methods for variational inequalities and related problems (65K15)
Cites Work
- ADD-OPT: Accelerated Distributed Directed Optimization
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- An affine scaling methodology for best basis selection
- Title not available (Why is that?)
- Constrained Consensus and Optimization in Multi-Agent Networks
- Gradient Convergence in Gradient methods with Errors
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Distributed Subgradient Methods for Multi-Agent Optimization
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Fast Distributed Gradient Methods
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Coordinate descent algorithms
- Cooperative Convex Optimization in Networked Systems: Augmented Lagrangian Algorithms With Directed Gossip Communication
- On Distributed Averaging Algorithms and Quantization Effects
- 10.1162/153244303322753751
- DC approximation approaches for sparse optimization
- Distributed Optimization Over Time-Varying Directed Graphs
- Adaptation, learning, and optimization over networks
- Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications
- Diffusion LMS Strategies for Distributed Estimation
- Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
- Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Optimization methods for large-scale machine learning
- An Approximate Dual Subgradient Algorithm for Multi-Agent Non-Convex Optimization
- Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- A Proximal Gradient Algorithm for Decentralized Composite Optimization
- Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory
- Non-Convex Distributed Optimization
- Harnessing Smoothness to Accelerate Distributed Optimization
- Difference-of-convex learning: directional stationarity, optimality, and sparsity
- Minimization of transformed \(L_1\) penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
- A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
- Feasible methods for nonconvex nonsmooth problems with applications in green communications
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
Cited In (37)
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Triggered gradient tracking for asynchronous distributed optimization
- A distributed continuous-time method for non-convex QCQPs
- Iterative distributed model predictive control for heterogeneous systems with non-convex coupled constraints
- A distributed asynchronous method of multipliers for constrained nonconvex optimization
- Decentralized optimization with affine constraints over time-varying networks
- Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs
- Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
- DIMIX: Diminishing Mixing for Sloppy Agents
- Proximal ADMM for nonconvex and nonsmooth optimization
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- Title not available (Why is that?)
- Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
- Decentralized optimization over tree graphs
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Localization and approximations for distributed non-convex optimization
- Parallel and distributed successive convex approximation methods for big-data optimization
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- Subgradient averaging for multi-agent optimisation with different constraint sets
- Decentralized dictionary learning over time-varying digraphs
- Penalty-based method for decentralized optimization over time-varying graphs
- Second-order guarantees of distributed gradient algorithms
- Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
- An event-triggering algorithm for decentralized stochastic optimization over networks
- EFIX: exact fixed point methods for distributed optimization
- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems
- A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- A two-level distributed algorithm for nonconvex constrained optimization
- Proximal nested primal-dual gradient algorithms for distributed constraint-coupled composite optimization
- Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
- Linear convergence rate analysis of a class of exact first-order distributed methods for weight-balanced time-varying networks and uncoordinated step sizes
- ExtraPush for convex smooth decentralized optimization over directed networks
- Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
- Decentralized Gradient Descent Maximization Method for Composite Nonconvex Strongly-Concave Minimax Problems
Uses Software
This page was built for publication: Distributed nonconvex constrained optimization over time-varying digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425183)
