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

KEYWORDS:

• ADMM
• nonconvex optimization
• multilinear functions

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 90C26
• 90C30

Acknowledgements

We thank Qing Qu, Yuqian Zhang and John Wright for helpful discussions about applications of multiaffine ADMM. We thank Wotao Yin for his feedback, and for bringing the paper [23] to our attention. We thank Yenson Lau for discussions about numerical experiments.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Frank E. Curtis http://orcid.org/0000-0001-7214-9187

Notes

1 [23] shows that every limit point of ADMM for the problem (NMF) is a constrained stationary point, but does not show that such limit points necessarily exist.

2 See Section 5.4 for the definition of ${\lambda }_{min}$ and ${\lambda }_{++}$.

3 Note that we have deliberately excluded $\ell =0$. 4.2.2 is not required to hold for $X_0$.

4 That is, either (1a) and (1b) hold, or (2a) and (2b) hold.

5 As an illustrative example, a problem may be formulated with constraints $X_0{X}_1+Z_1=0,X_0+P_1\left(X_1\right)+Z_2=0,X_0{X}_2+Z_3=0,P_2\left(X_2\right)+Z_4=0$, where $P_1,P_2$ are injective linear maps. The notation $A(\mathcal{X},Z_0)+Q\left({\mathcal{Z}}_{>}\right)$ denotes the concatenation of these equations, which can also be seen naturally as a system of four constraints. In this case, the indices $r\left(\ell \right)\in \{1,2,3,4\}$, and 4.2.2(2a) is satisfied by the second constraint $X_0+P_1\left(X_1\right)+Z_2=0$ for the variables $X_0,X_1$ (i.e. $r\left(0\right)=r\left(1\right)=2$ and $R_0=I,R_1=P_1$), and by the fourth constraint $P_2\left(X_2\right)+Z_4=0$ for $X_2$.

6 Note that $X_0$ is included here, unlike in Assumption 4.2.

7 For linear constraints $A_1{x}_1+\cdots +A_n{x}_n=b$, the equivalent statement is that $\mathrm{I}\mathrm{m}\left(A_n\right)\supseteq \bigcup _{i=1}^{n-1}\mathrm{I}\mathrm{m}\left(A_i\right)$.

8 In the sense that this exact assumption is always necessary and cannot be replaced.

9 When $j>m_1$, ${\theta }_j\left(X\right)$ is a constant map of Y.

10 To see this, define the prox-Lagrangian ${\mathcal{L}}^P(U,Y,W,O)=\mathcal{L}(U,Y,W)+\parallel Y-O{\parallel }_S^2$. By definition, $Y^{+}$ decreases the prox-Lagrangian, so ${\mathcal{L}}^P(U,Y^{+},W,Y^k)\le {\mathcal{L}}^P(U,Y^k,W,Y^k)=\mathcal{L}(U,Y,W)$ and the desired result follows.

11 To motivate the sub-blocks $(Y_0,Y_1)$ in 6.13, one should look to the decomposition of $\psi \left(\mathcal{Z}\right)$ in Assumption 4.1, where we can take $Y_0=\left\{Z_0\right\}$ and $Y_1={\mathcal{Z}}_{>}$. Intuitively, $Y_1$ is a sub-block such that ψ is a smooth function of $Y_1$, and which is ‘absorbing’ in the sense that for any $U^{+}$ and $Y_0^{+}$, there exists $Y_1$ making the solution feasible.

12 (2) is assumed to hold for the iterates $U^{+}$ and $Y^{+}$ generated by ADMM as the minimal required condition, but one should not, in general, think of this property as being specifically related to the iterates of the algorithm. In the cases we consider, it will be a property of the function f and the constraint C that for any point $(\tilde{U},\tilde{Y})$, there exists ${\hat{Y}}_1\in {\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{Y_1}\left\{f_{\tilde{U}}\right({\tilde{Y}}_0,Y_1):C_{\tilde{U}}({\tilde{Y}}_0,Y_1)=b_{\tilde{U}}\}$ such that $\parallel {\hat{Y}}_1-{\tilde{Y}}_1{\parallel }^2\le \zeta \parallel C_{\tilde{U}}\left(Y^{+}\right)-b_{\tilde{U}}{\parallel }^2$.

13 To clarify the definition of ${\hat{Y}}_1$, the sub-block for $Y_0$ is fixed to the value of $Y_0^{+}$ on the given iteration, and then ${\hat{Y}}_1$ is obtained by minimizing $f_{U^{+}}(Y_0^{+},Y_1)$ for the $Y_1$ sub-block over the feasible region $C_{U^{+}}(Y_0^{+},Y_1)=b_{U^{+}}$.

Additional information

Funding

The research of Wenbo Gao and Donald Goldfarb was supported in part by the National Science Foundation under NSF Grants CCF-1527809 and CCF- 1838061. The research of Frank E. Curtis was supported in part by the National Science Foundation under NSF Grant CCF-1618717 and by the U.S. Department of Energy under DOE Grant DE-SC0010615.

Notes on contributors

Wenbo Gao

Wenbo Gao is a PhD student in the Department of Industrial Engineering and Operations Research at Columbia University.

Donald Goldfarb

Donald Goldfarb is the Alexander and Hermine Avanessians Professor of Industrial Engineering and Operations Research at Columbia University. He has been a faculty member at Columbia Engineering since 1982. He served as interim dean of the School in 2012–2013, executive vice dean in 2011–2012, acting dean in 1994–1995, and chair of the IEOR department from 1984 to 2002.

His research interests include algorithms for linear, quadratic, semidefinite, convex and general nonlinear programming, network flows, large sparse systems, and applications in robust optimization, imaging, machine learning, and finance. He has published more than 100 technical papers and served on the editorial boards of several journals, including editor in chief of Mathematical Programming, editor of the SIAM (Society for Industrial and Applied Mathematics) Journal on Optimization and the SIAM Journal on Numerical Analysis, and associate editor of Operations Research and Mathematics of Computation. He has been a member of the councils of the Mathematical Programming Society and the American Mathematical Society, numerous technical society program and award committees, and advisory committees to various universities and government research agencies.

Before coming to Columbia, he held positions as professor and acting chair in the Department of Computer Science at the City College of New York, visiting professor in the Department of Computer Science and at the School of Operations Research and Industrial Engineering at Cornell University, and assistant research scientist at the Courant Institute of Mathematical Sciences of New York University. He earned a BChE from Cornell in 1963 and MA and PhD from Princeton in 1965 and 1966, respectively.

Frank E. Curtis

Frank E. Curtis is an Associate Professor in the Department of Industrial and Systems Engineering at Lehigh University, where he has been employed since 2009. He received his Bachelors degree from the College of William and Mary in 2003 with a double major in Mathematics and Computer Science, received his Masters in 2004 and PhD in 2007 from the Department of Industrial Engineering and Management Science at Northwestern University, and spent two years as a Postdoctoral Researcher in the Courant Institute of Mathematical Sciences at New York University from 2007 until 2009. His research focuses on the design, analysis, and implementation of numerical methods for solving large-scale nonlinear optimization problems. He received an Early Career Award from the Advanced Scientific Computing Research program of the US Department of Energy, and has received funding from various programs of the US National Science Foundation, including through a TRIPODS Institute grant awarded to him and his collaborators at Lehigh, Northwestern, and Boston University. He currently serves as an Associate Editor for Mathematical Programming, SIAM Journal on Optimization, Mathematics of Operations Research, and Mathematical Programming Computation. He served as the Vice Chair for Nonlinear Programming for the INFORMS Optimization Society from 2010 until 2012, and is currently very active in professional societies and groups related to mathematical optimization, including INFORMS, the Mathematics Optimization Society, and the SIAM Activity Group on Optimization.