A two-level distributed algorithm for nonconvex constrained optimization

Abstract

This paper aims to develop distributed algorithms for nonconvex optimization problems with complicated constraints associated with a network. The network can be a physical one, such as an electric power network, where the constraints are nonlinear power flow equations, or an abstract one that represents constraint couplings between decision variables of different agents. Despite the recent development of distributed algorithms for nonconvex programs, highly complicated constraints still pose a significant challenge in theory and practice. We first identify some difficulties with the existing algorithms based on the alternating direction method of multipliers (ADMM) for dealing with such problems. We then propose a reformulation that enables us to design a two-level algorithm, which embeds a specially structured three-block ADMM at the inner level in an augmented Lagrangian method (ALM) framework. Furthermore, we prove the global and local convergence as well as iteration complexity of this new scheme for general nonconvex constrained programs, and show that our analysis can be extended to handle more complicated multi-block inner-level problems. Finally, we demonstrate with computation that the new scheme provides convergent and parallelizable algorithms for various nonconvex applications, and is able to complement the performance of the state-of-the-art distributed algorithms in practice by achieving either faster convergence in optimality gap or in feasibility or both.

References in corpus (7)

• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• Penalty Dual Decomposition Method For Nonsmooth Nonconvex Optimization
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Extending the ergodic convergence rate of the proximal ADMM
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization

Cited by in corpus (6)

• Fast and Stable Nonconvex Constrained Distributed Optimization: The ELLADA Algorithm
• Improved Hierarchical ADMM for Nonconvex Cooperative Distributed Model Predictive Control
• A Two-level ADMM Algorithm for AC OPF with Global Convergence Guarantees
• Dual Descent ALM and ADMM
• Decomposition Methods for Global Solutions of Mixed-Integer Linear Programs
• A Proximal Linearization-based Decentralized Method for Nonconvex Problems with Nonlinear Constraints