ADMM for multiaffine constrained optimization
Wenbo Gao, Donald Goldfarb, Frank E. Curtis · Optimization methods & software · 2019
We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka–Łojasiewicz (K–Ł) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.
Cited by 40 works. doi:10.1080/10556788.2019.1683553 Open-access PDF
Authors
References
- Reducibility among Combinatorial Problems
- Learning the parts of objects by non-negative matrix factorization
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries
- Algorithms for Non-negative Matrix Factorization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Robust principal component analysis?
- Smooth minimization of non-smooth functions
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation