A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
arXiv:1809.01212 · doi:10.1109/TSP.2019.2951216
Abstract
We introduce the primal-dual quasi-Newton (PD-QN) method as an approximated second order method for solving decentralized optimization problems. The PD-QN method performs quasi-Newton updates on both the primal and dual variables of the consensus optimization problem to find the optimal point of the augmented Lagrangian. By optimizing the augmented Lagrangian, the PD-QN method is able to find the exact solution to the consensus problem with a linear rate of convergence. We derive fully decentralized quasi-Newton updates that approximate second order information to reduce the computational burden relative to dual methods and to make the method more robust in ill-conditioned problems relative to first order methods. The linear convergence rate of PD-QN is established formally and strong performance advantages relative to existing dual and primal-dual methods are shown numerically.
References in corpus (12)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Convex Optimization for Big Data
- DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements
- RES: Regularized Stochastic BFGS Algorithm
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Global Convergence of Online Limited Memory BFGS
- Decentralized Quasi-Newton Methods
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- On the Convergence of Decentralized Gradient Descent
- Superlinearly Convergent Asynchronous Distributed Network Newton Method
Cited by in corpus (8)
- Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
- Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
- A Survey of Distributed Optimization Methods for Multi-Robot Systems
- DISH: A Distributed Hybrid Primal-Dual Optimization Framework to Utilize System Heterogeneity
- Decentralized Approximate Newton Methods for Convex Optimization on Networked Systems
- A Newton Tracking Algorithm with Exact Linear Convergence Rate for Decentralized Consensus Optimization
- Data-driven Design of Context-aware Monitors for Hazard Prediction in Artificial Pancreas Systems
- Newton Method over Networks is Fast up to the Statistical Precision