Optimization Online


A two-level distributed algorithm for nonconvex constrained optimization

Kaizhao Sun (ksun46***at***gatech.edu)
X. Andy Sun (andy.sun***at***isye.gatech.edu)

Abstract: This paper is motivated by the desire 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 di fferent agents. Thus, this type of problems are ubiquitous in applications. Despite the recent development of distributed algorithms for nonconvex programs, highly complicated constraints still pose a signifi cant challenge in theory and practice. We fi rst 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 show the global convergence and convergence rate of this new scheme for general nonsmooth and nonconvex constrained programs, which builds on and extends the classic and recent works on ALM and ADMM. Finally, we demonstrate with computation that the new scheme provides convergent and parallelizable algorithms for nonlinear network flow problems and minimization over compact manifold. The proposed algorithmic framework provides a new principled way for parallel computation of constrained nonconvex optimization.

Keywords: Distributed Optimization, Global Convergence, Augmented Lagrangian Method, Alternating Direction Method of Multipliers

Category 1: Nonlinear Optimization

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Network Optimization

Citation: Address: H. Milton Stewart School of Industrial & Systems Engineering, 755 Ferst Dr NW, Atlanta, GA 30318

Download: [PDF]

Entry Submitted: 02/20/2019
Entry Accepted: 02/20/2019
Entry Last Modified: 08/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society