ADMM for multiaffine constrained optimization

Wenbo Gao, Donald Goldfarb, Frank E. CurtisOptim. Methods Softw 2020 · OpenReview

TL;DR

This paper extends the Alternating Direction Method of Multipliers (ADMM) to a broader class of optimization problems with "multiaffine" constraints, which are more general than the linear constraints typically handled. The authors prove convergence guarantees for ADMM under weak assumptions, even for nonconvex problems, and demonstrate its applicability to various real-world tasks like representation learning and neural network training.

What Problem Does This Paper Address?

The Alternating Direction Method of Multipliers (ADMM) is a powerful optimization technique, but its theoretical guarantees have historically been limited to problems with linear constraints and separable objective functions. Many real-world problems, however, naturally involve more complex, nonlinear (specifically, multiaffine) constraints. Extending ADMM's convergence guarantees to these more general settings is crucial for its wider applicability. This paper tackles this challenge by developing a framework for ADMM that can handle multiaffine constraints, even when the objective functions are nonconvex.

Methods

The core contribution is the theoretical analysis of ADMM applied to problems of the form:

$$ \begin{aligned} \min_{x_1, \dots, x_n} \quad & f_1(x_1) + \dots + f_n(x_n) \\ \text{s.t.} \quad & A_1x_1 + \dots + A_nx_n - b = 0 \end{aligned} $$

where the constraint $A_1x_1 + \dots + A_nx_n - b = 0$ is multiaffine (a generalization of linear constraints). The authors introduce a generalized augmented Lagrangian and adapt the standard ADMM algorithm. They establish convergence to constrained stationary points under weak assumptions, including conditions for global convergence to a unique point when the augmented Lagrangian satisfies the Kurdyka-Łojasiewicz (K-Ł) property. The analysis is carefully structured to handle both convex and nonconvex objective functions and constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development, with examples illustrating applications rather than presenting empirical results on specific datasets.

Key Insights and Ideas

  • Generalizing ADMM: The paper successfully extends ADMM's convergence theory to multiaffine constraints, significantly broadening its applicability beyond linear constraints. This is a key theoretical advancement.
  • Weak Assumptions: The convergence proofs rely on remarkably weak assumptions, making the results applicable to a wide range of problems, including those with nonconvex objectives and constraints.
  • Multiaffine Constraints are Natural: The paper highlights that multiaffine constraints arise naturally in various applications, such as representation learning (NMF, dictionary learning), non-convex reformulations of convex problems (RPCA), and neural network training.
  • Subproblem Solvability: A significant practical aspect is that many of the multiaffine problems considered, when formulated appropriately (often with auxiliary variables), lead to subproblems with closed-form solutions, making ADMM efficient in practice.
  • K-Ł Property for Uniqueness: The Kurdyka-Łojasiewicz (K-Ł) property of the augmented Lagrangian is shown to be a powerful tool for guaranteeing convergence to a unique constrained stationary point, a desirable property for optimization algorithms.

Key Results

  • Convergence to Stationary Points: Under mild assumptions, ADMM applied to multiaffine constrained problems is shown to produce a bounded sequence of iterates, and every limit point is a constrained stationary point.
  • Global Convergence: When the augmented Lagrangian satisfies the K-Ł property and certain other conditions, ADMM is proven to converge to a unique constrained stationary point.
  • Practical Applicability: The paper demonstrates that various challenging problems, including those in representation learning and neural network training, can be formulated with multiaffine constraints and solved efficiently by the proposed ADMM framework, often with subproblems having closed-form solutions.

Limitations and Future Work

  • Assumption Tightness: While the assumptions are weak, the authors acknowledge that some, like the Im(Q) ⊃ Im(A) condition, are tight for general problems and might limit the scope of ADMM's applicability in certain scenarios.
  • Proximal ADMM Connection: The paper notes a connection between Assumption 2 and proximal ADMM, suggesting that further exploration of proximal variants could be beneficial for structured problems where standard ADMM assumptions might not hold.
  • Numerical Experiments: While examples are provided, the paper focuses on theoretical convergence. Further numerical studies comparing the proposed ADMM with other methods on a wider range of real-world problems would be valuable.
  • General Nonlinear Constraints: The current framework is for multiaffine constraints. Extending ADMM convergence guarantees to more general nonlinear constraints remains an open and challenging area.

Summary updated

BibTeX
@inproceedings{gao2020admm,
  author = {Wenbo Gao and Donald Goldfarb and Frank E. Curtis},
  title = {{ADMM for multiaffine constrained optimization}},
  booktitle = {Optim. Methods Softw},
  year = {2020},
  url = {https://openreview.net/forum?id=wjOaUoRtj0},
}
Figure