Primal recovery from consensus-based dual decomposition for distributed convex optimization
From MaRDI portal
Publication:255083
DOI10.1007/S10957-015-0758-0zbMATH Open1332.90203arXiv1503.07678OpenAlexW1540376964MaRDI QIDQ255083FDOQ255083
Hadi Jamali-Rad, Andrea Simonetto
Publication date: 9 March 2016
Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)
Abstract: Dual decomposition has been successfully employed in a variety of distributed convex optimization problems solved by a network of computing and communicating nodes. Often, when the cost function is separable but the constraints are coupled, the dual decomposition scheme involves local parallel subgradient calculations and a global subgradient update performed by a master node. In this paper, we propose a consensus-based dual decomposition to remove the need for such a master node and still enable the computing nodes to generate an approximate dual solution for the underlying convex optimization problem. In addition, we provide a primal recovery mechanism to allow the nodes to have access to approximate near-optimal primal solutions. Our scheme is based on a constant stepsize choice and the dual and primal objective convergence are achieved up to a bounded error floor dependent on the stepsize and on the number of consensus steps among the nodes.
Full work available at URL: https://arxiv.org/abs/1503.07678
Recommendations
- Primal-dual stochastic distributed algorithm for constrained convex optimization
- A randomized incremental primal-dual method for decentralized consensus optimization
- Primal-dual algorithm for distributed constrained optimization
- On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
- Inexact dual averaging method for distributed multi-agent optimization
consensus algorithmdistributed convex optimizationdual decompositionepsilon-subgradientergodic convergenceprimal recoverysubgradient optimization
Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Approximation methods and heuristics in mathematical programming (90C59) Nonlinear programming (90C30)
Cites Work
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Subgradient methods for saddle-point problems
- Ergodic, primal convergence in dual subgradient schemes for convex programming
- Primal convergence from dual subgradient methods for convex optimization
- Fast linear iterations for distributed averaging
- Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs
- Convergence analysis of approximate primal solutions in dual first-order methods
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization
- Multiuser Optimization: Distributed Algorithms and Error Analysis
- Title not available (Why is that?)
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- Sensor Selection via Convex Optimization
- Distributed Maximum Likelihood Sensor Network Localization
- Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
- Trace bounds on the solution of the algebraic matrix Riccati and Lyapunov equation
- Application of a Smoothing Technique to Decomposition in Convex Optimization
- Constrained Consensus and Optimization in Multi-Agent Networks
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- A Distributed Newton Method for Network Utility Maximization–I: Algorithm
- An <formula formulatype="inline"><tex Notation="TeX">$O(1/k)$</tex> </formula> Gradient Method for Network Resource Allocation Problems
- A decentralized algorithm for spectral analysis
- Optimal scaling of a gradient method for distributed resource allocation
Cited In (20)
- Composite optimization with coupling constraints via dual proximal gradient method with applications to asynchronous networks
- An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs
- Primal-dual stochastic distributed algorithm for constrained convex optimization
- Initialization-free privacy-guaranteed distributed algorithm for economic dispatch problem
- Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs
- Decentralized Strongly-Convex Optimization with Affine Constraints: Primal and Dual Approaches
- A Decentralized Primal-Dual Method for Constrained Minimization of a Strongly Convex Function
- A distributed methodology for approximate uniform global minimum sharing
- Distributed event-triggered algorithm for convex optimization with coupled constraints
- Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
- Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
- A dual approach for optimal algorithms in distributed optimization over networks
- A unitary distributed subgradient method for multi-agent optimization with different coupling sources
- Distributed dual subgradient methods with averaging and applications to grid optimization
- Dual decomposition for multi-agent distributed optimization with coupling constraints
- Tracking-ADMM for distributed constraint-coupled optimization
- Decentralized online strongly convex optimization with general compressors and random disturbances
- Parallel subgradient algorithm with block dual decomposition for large-scale optimization
- Distributed Stochastic Approximation with Local Projections
- Principled analyses and design of first-order methods with inexact proximal operators
Uses Software
This page was built for publication: Primal recovery from consensus-based dual decomposition for distributed convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q255083)
