Distributed approximate Newton algorithms and weight design for constrained optimization

DOI10.1016/J.AUTOMATICA.2019.108538zbMATH Open1429.93016arXiv1804.06238OpenAlexW2971936862MaRDI QIDQ2280935FDOQ2280935

Authors: Tor Anderson, Chin-Yao Chang, Sonia Martínez 

Publication date: 19 December 2019

Published in: Automatica (Search for Journal in Brave)

Abstract: Motivated by economic dispatch and linearly-constrained resource allocation problems, this paper proposes a class of novel Distributed-Approx Newton algorithms that approximate the standard Newton optimization method. We first develop the notion of an optimal edge weighting for the communication graph over which agents implement the second-order algorithm, and propose a convex approximation for the nonconvex weight design problem. We next build on the optimal weight design to develop a discrete Distributed Approx-Newton algorithm which converges linearly to the optimal solution for economic dispatch problems with unknown cost functions and relaxed local box constraints. For the full box-constrained problem, we develop a continuous Distributed Approx-Newton algorithm which is inspired by first-order saddle-point methods and rigorously prove its convergence to the primal and dual optimizers. A main property of each of these distributed algorithms is that they only require agents to exchange constant-size communication messages, which lends itself to scalable implementations. Simulations demonstrate that the Distributed Approx-Newton algorithms with our weight design have superior convergence properties compared to existing weighting strategies for first-order saddle-point and gradient descent methods.

Full work available at URL: https://arxiv.org/abs/1804.06238

Recommendations

• Distributed Newton Optimization With Maximized Convergence Rate
• Distributed Newton Method for Large-Scale Consensus Optimization
• Network Newton Distributed Optimization Methods
• Newton-Raphson Consensus for Distributed Convex Optimization
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
• Distributed Newton's Method for Network Cost Minimization
• Distributed Newton methods for strictly convex consensus optimization problems in multi-agent networks
• scientific article; zbMATH DE number 7306895
• Approximations in Distributed Optimization
• Distributed Newton algorithm for a special quadratic programming problem

zbMATH Keywords

multi-agent systemsnetworked systemsresource allocationsecond-order methodsdistributed optimization

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25) Multi-agent systems (93A16) Networked control (93B70)

Cites Work

• Title not available (Why is that?)
• The Schur complement and its applications
• Parallel iterative methods for sparse linear systems
• Nonlinear systems.
• A Distributed Newton Method for Network Utility Maximization–I: Algorithm
• Optimal scaling of a gradient method for distributed resource allocation
• Fast Distributed Gradient Methods
• Title not available (Why is that?)
• Newton-Raphson Consensus for Distributed Convex Optimization
• Initialization-free distributed coordination for economic dispatch under varying loads and generator commitment
• Optimal Load-Side Control for Frequency Regulation in Smart Grids
• The Role of Convexity in Saddle-Point Dynamics: Lyapunov Function and Robustness
• Distributed Optimization-Based Control of Multi-Agent Networks in Complex Environments
• Network Newton Distributed Optimization Methods
• A Distributed Newton Method for Network Utility Maximization—Part II: Convergence

Cited In (16)

• Surplus-based accelerated algorithms for distributed optimization over directed networks
• Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization
• Distributed resource allocation via multi-agent systems under time-varying networks
• Consensus of general linear multi-agent systems based on second-order neighbours' information: directed topology case
• Convergence analysis of first-order discrete multi-agent systems with cooperative-competitive mechanisms
• Distributed resource allocation with binary decisions via Newton-like neural network dynamics
• Group consensus for multi-agent systems based on acyclic partition and generational partition under DoS attack
• Adaptive backstepping for distributed optimization
• Distributed strategy for constrained resource allocation problems of autonomous second-order nonlinear agents and its application to smart grids
• Distributed Adaptive Optimization With Weight-Balancing
• Distributed Newton Methods for Deep Neural Networks
• Distributed Newton methods for strictly convex consensus optimization problems in multi-agent networks
• Distributed Design for Nuclear Norm Minimization of Linear Matrix Equations With Constraints
• Projected subgradient based distributed convex optimization with transmission noises
• Distributed optimal resource allocation over strongly connected digraphs: a surplus-based approach
• Complex group consensus of multi-agent systems with cooperative-competitive mechanisms: acyclic partition method

This page was built for publication: Distributed approximate Newton algorithms and weight design for constrained optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2280935)