On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems

Sindri Magnússon, Pradeep Chathuranga Weeraddana, Michael Rabbat, Carlo Fischione

Abstract

Nonconvex and structured optimization problems arise in many engineering applications that demand scalable and distributed solution methods. The study of the convergence properties of these methods is in general difficult due to the nonconvexity of the problem. In this paper, two distributed solution methods that combine the fast convergence properties of augmented Lagrangian-based methods with the separability properties of alternating optimization are investigated. The first method is adapted from the classic quadratic penalty function method and is called the Alternating Direction Penalty Method (ADPM). Unlike the original quadratic penalty function method, in which single-step optimizations are adopted, ADPM uses an alternating optimization, which in turn makes it scalable. The second method is the well-known Alternating Direction Method of Multipliers (ADMM). It is shown that ADPM for nonconvex problems asymptotically converges to a primal feasible point under mild conditions and an additional condition ensuring that it asymptotically reaches the standard first order necessary conditions for local optimality are introduced. In the case of the ADMM, novel sufficient conditions under which the algorithm asymptotically reaches the standard first order necessary conditions are established. Based on this, complete convergence of ADMM for a class of low dimensional problems are characterized. Finally, the results are illustrated by applying ADPM and ADMM to a nonconvex localization problem in wireless sensor networks.

Introduction

In the era of large-scale engineering and big data, optimization problems are frequently both structured—allowing for decomposition into smaller, connected sub-problems—and nonconvex. While the Alternating Direction Method of Multipliers (ADMM) has become a standard tool for convex distributed optimization, its application to nonconvex landscapes has historically lacked rigorous theoretical guarantees. This work bridges the gap between the empirical success of Lagrangian-based methods and their mathematical certainty, providing a framework for convergence in complex optimization environments.

Distributed Lagrangian Frameworks

The research focuses on two primary algorithmic approaches to distributed optimization:

  1. Alternating Direction Penalty Method (ADPM): This is a scalable adaptation of the classic quadratic penalty method. Instead of a single-step optimization, ADPM alternates between variable updates (e.g., $x$ and $z$). A penalty parameter $\rho$ is increased over time to enforce feasibility.
  2. Alternating Direction Method of Multipliers (ADMM): Unlike ADPM, ADMM uses a fixed penalty parameter and incorporates a dual variable update to nudge the system toward the optimum.
Visualization of a structured optimization problem with non-convex constraints (green regions) and a linear coupling constraint.

The core challenge in these methods is ensuring that the alternating updates actually lead to a point satisfying First Order Necessary (FON) conditions—the mathematical requirements for local optimality.

Key Theoretical Insights

A major contribution of this work is identifying the conditions under which distributed methods succeed in nonconvex settings:

  • Dual Convergence as a Proxy: For ADMM, the authors demonstrate that if the dual variables converge, the primal variables must satisfy the FON conditions. This provides an "online verifiability" mechanism for researchers to monitor algorithm success in real-time.
  • Constraint Geometry: A surprising finding is that while the objective functions can be nonconvex, maintaining convex constraint sets (the allowed ranges for variables) significantly enhances the stability and convergence of ADPM.
  • Scalability through Alternation: The results confirm that alternating updates provide the necessary scalability for distributed computing without sacrificing the guarantee of reaching a local optimum.

Experimental Evaluation: WSN Localization

The theoretical findings were tested using a simulated Cooperative Localization Problem in Wireless Sensor Networks (WSN). The task involved estimating the positions of 10 sensors relative to 4 anchors using noisy distance measurements. This problem is inherently nonconvex due to the existence of multiple local minima (e.g., "flipped" sensor positions).

The experiments revealed:

  • Superior Stability: Both ADMM and ADPM remained stable and converged to high-quality estimates, whereas standard Distributed Gradient Descent (DGD) was often unstable and prone to divergence.
  • Convergence Speed: ADMM and a dual-update variant of ADPM (ADPM-y) significantly outperformed DGD. ADMM, in particular, showed a much faster decay in residuals, indicating efficient constraint satisfaction.

Conclusion

This paper establishes a mathematical safety net for using ADMM and ADPM in nonconvex optimization. By proving convergence to local optima under specific conditions, the authors provide a foundation for applying these distributed methods to complex systems like power grids and sensor networks. Future research will focus on extending these guarantees to global optimality and higher-dimensional problem spaces.

Summary updated

Abstract

Nonconvex and structured optimization problems arise in many engineering applications that demand scalable and distributed solution methods. The study of the convergence properties of these methods is in general difficult due to the nonconvexity of the problem. In this paper, two distributed solution methods that combine the fast convergence properties of augmented Lagrangian-based methods with the separability properties of alternating optimization are investigated. The first method is adapted from the classic quadratic penalty function method and is called the Alternating Direction Penalty Method (ADPM). Unlike the original quadratic penalty function method, in which single-step optimizations are adopted, ADPM uses an alternating optimization, which in turn makes it scalable. The second method is the well-known Alternating Direction Method of Multipliers (ADMM). It is shown that ADPM for nonconvex problems asymptotically converges to a primal feasible point under mild conditions and an additional condition ensuring that it asymptotically reaches the standard first order necessary conditions for local optimality are introduced. In the case of the ADMM, novel sufficient conditions under which the algorithm asymptotically reaches the standard first order necessary conditions are established. Based on this, complete convergence of ADMM for a class of low dimensional problems are characterized. Finally, the results are illustrated by applying ADPM and ADMM to a nonconvex localization problem in wireless sensor networks.
BibTeX
@article{magnusson2016convergence,
  author = {Sindri Magnússon and Pradeep Chathuranga Weeraddana and Michael Rabbat and Carlo Fischione},
  title = {{On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2016},
  url = {https://openreview.net/forum?id=Twsl-JR-_1h},
}
Figure