ADMM for Multiaffine Constrained Optimization

Abstract

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 endeavored 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.

arXiv commentv3: 37 pages, 7 figures v2: 32 pages, 0 figures. v1: 26 pages, 0 figures

References in corpus (6)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Training Neural Networks Without Gradients: A Scalable ADMM Approach
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting

Cited by in corpus (2)

• Shape Analysis via Functional Map Construction and Bases Pursuit
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization