Distributed nonconvex constrained optimization over time-varying digraphs
From MaRDI portal
Publication:2425183
DOI10.1007/S10107-018-01357-WzbMATH Open1415.90130arXiv1809.01106OpenAlexW2892002891WikidataQ128388005 ScholiaQ128388005MaRDI QIDQ2425183FDOQ2425183
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 (28)
- Distributed convex optimization with coupling constraints over time-varying directed graphs
- Triggered gradient tracking for asynchronous distributed optimization
- Iterative distributed model predictive control for heterogeneous systems with non-convex coupled constraints
- 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
- Decentralized Dictionary Learning Over Time-Varying Digraphs
- DIMIX: Diminishing Mixing for Sloppy Agents
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- Fast Decentralized Nonconvex Finite-Sum Optimization with Recursive Variance Reduction
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- Second-Order Guarantees of Distributed Gradient Algorithms
- Title not available (Why is that?)
- Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
- Distributed Variable Sample-Size Gradient-Response and Best-Response Schemes for Stochastic Nash Equilibrium Problems
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Subgradient averaging for multi-agent optimisation with different constraint sets
- Penalty-based method for decentralized optimization over time-varying graphs
- An event-triggering algorithm for decentralized stochastic optimization over networks
- EFIX: exact fixed point methods for distributed optimization
- 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
- 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)
