Accelerated Gradient Methods for Networked Optimization

Abstract

We develop multi-step gradient methods for network-constrained optimization of strongly convex functions with Lipschitz-continuous gradients. Given the topology of the underlying network and bounds on the Hessian of the objective function, we determine the algorithm parameters that guarantee the fastest convergence and characterize situations when significant speed-ups can be obtained over the standard gradient method. Furthermore, we quantify how the performance of the gradient method and its accelerated counterpart are affected by uncertainty in the problem data, and conclude that in most cases our proposed method outperforms gradient descent. Finally, we apply the proposed technique to three engineering problems: resource allocation under network-wide budget constraints, distributed averaging, and Internet congestion control. In all cases, we demonstrate that our algorithm converges more rapidly than alternative algorithms reported in the literature.

Cited by in corpus (13)

• Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Analysis of Distributed ADMM Algorithm for Consensus Optimization in Presence of Node Error
• Uncertain Multi-Agent Systems with Distributed Constrained Optimization Missions and Event-Triggered Communications: Application to Resource Allocation
• Global convergence of the Heavy-ball method for convex optimization
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Accelerated Consensus via Min-Sum Splitting
• Distributed Resource Allocation Over Random Networks Based on Stochastic Approximation
• Cloud-aided collaborative estimation by ADMM-RLS algorithms for connected vehicle prognostics
• Adding a single state memory optimally accelerates symmetric linear maps
• Fast-Convergent Dynamics for Distributed Allocation of Resources Over Switching Sparse Networks with Quantized Communication Links
• Newton-Raphson Consensus for Distributed Convex Optimization