\section{Introduction}
Numerical optimization is commonly used in computer graphics, and finding a suitable solver is often instrumental to the performance of the algorithm. For an unconstrained problem with a simple smooth target function, gradient-based solvers such as gradient descent or the Newton method are popular choices~\cite{nocedal2006numerical}. 
On the other hand, for more complex problems, such as those with a nonsmooth target function or with nonlinear hard constraints, it is often necessary to employ more sophisticated optimization solvers to achieve the desired performance.
For example, proximal splitting methods~\cite{Combettes2011} are often used to handle nonsmooth optimization problems with or without constraints. The basic idea is to introduce auxiliary variables to replace some of the original variables in the target function, while enforcing consistency between the original variables and the auxiliary variables with a soft or hard constraint. This often allows to problem to be solved via alternating update of the variables, which reduces to simple sub-problems that can be solved efficiently. One example of such proximal splitting methods is the local-global solvers commonly used for geometry processing and physical simulation~\cite{SorkineA07,Liu2008,BouazizDSWP12,Liu2013,Bouaziz2014}. 


Another popular type of proximal splitting methods, the alternating direction method of multipliers (ADMM)~\cite{boyd2011distributed}, is designed for the following form of optimization:
\begin{equation}
\min_{\mathbf{x},\mathbf{z}}~\varPhi(\mathbf{x}, \mathbf{z})\qquad
\textrm{s.t.}~\mathbf{A}\mathbf{x} - \mathbf{B} \mathbf{z} = \mathbf{c},
\label{eq:GeneralADMMProblem}
\end{equation}
where $\mathbf{x},\mathbf{z}$ are the original variable and the auxiliary variable, and the linear hard constraint $\mathbf{A}\mathbf{x} - \mathbf{B} \mathbf{z} = \mathbf{c}$ enforces their compatibility. ADMM computes a stationary point of the augmented Lagrangian function 
$L(\mathbf{x},\mathbf{z},\mathbf{y})=\varPhi(\mathbf{x}, \mathbf{z}) + \langle \beta \mathbf{y},\mathbf{A}\mathbf{x}-\mathbf{B}\mathbf{z}-\mathbf{c} \rangle + \frac{\beta}{2} \| \mathbf{A}\mathbf{x} - \mathbf{B} \mathbf{z} - \mathbf{c} \|^2$ via the following iterations~\cite{boyd2011distributed}:
\begin{align}
\mathbf{z}_{k+1}&=\argmin_{\mathbf{z}}~L(\mathbf{x}_{k}, \mathbf{z},\mathbf{y}_k), \label{eq:GeneralZStep}\\
\mathbf{x}_{k+1}&=\argmin_{\mathbf{x}}~L(\mathbf{x}, \mathbf{z}_{k+1},\mathbf{y}_k), \label{eq:GeneralXStep}\\
\mathbf{y}_{k+1}&=\mathbf{y}_k+\mathbf{A}\mathbf{x}_{k+1}-\mathbf{B}\mathbf{z}_{k+1}-\mathbf{c}, \label{eq:GeneralYStep}
\end{align}
where $\mathbf{y}$ is the dual variable, and $\beta \in \mathbb{R}^{+}$ is a penalty parameter.
This formulation is general enough to represent a large variety of optimization problems. For example, any additional hard constraint can be incorporated into the target function using an indicator function that vanishes if the constraint is satisfied and has value $+\infty$ otherwise. The above iteration often has a low computational cost, where each sub-problem can be solved in parallel and/or in a closed form. The solver can handle nonsmooth problems, and typically converges to an approximate solution in a small number of iterations~\cite{boyd2011distributed}. Moreover, although ADMM was initially designed for convex problems, it has proved to be also effective for many noncovex problems~\cite{wang2019global}. Such properties make it a popular solver for large-scale optimization in computer graphics~\cite{Neumann2013,Neumann2014-CMM,Overby2017}, computer vision~\cite{Lu2018-Unified,Wu2019-LpBox}, and image processing~\cite{Figueiredo2010,Almeida2013,Heide2016}.

Despite its popularity, a major drawback of ADMM is that it can take a long time to converge to a solution of high accuracy. This limitation has motivated various work on accelerating ADMM with a focus on convex problem~\cite{Goldstein2014,Kadkhodaie2015,Zhang2018-GMRES}. For nonconvex ADMM, an acceleration technique was proposed recently in~\cite{zhang2019accelerating}. By treating the steps~\eqref{eq:GeneralZStep}--\eqref{eq:GeneralYStep} as a fixed-point iteration of the variables $(\mathbf{x}, \mathbf{y})$ , it speeds up the convergence using Anderson acceleration~\cite{Anderson1965}, a well-known acceleration technique for fixed-point iterations.
It is also shown in~\cite{zhang2019accelerating} that for problems with a separable target function that satisfies certain assumptions, ADMM can be treated as a fixed-point iteration on a reduced set of variables, which further reduces the overhead of Anderson acceleration.

In this paper, we propose a novel acceleration technique for nonconvex ADMM from a different perspective. We note that if the target function is separable in $\mathbf{x}$ and $\mathbf{z}$, then ADMM is equivalent to Douglas-Rachford (DR) splitting~\cite{douglas1956numerical}, a classical proximal splitting method. Such equivalence enables us to interpret ADMM using its equivalent DR splitting form, which turns out to be a fixed-point iteration for a linear transformation of the ADMM variables, with the same dimensionality as the dual variable $\mathbf{y}$. As a result, we can apply Anderson acceleration to such alternative form of fixed-point iteration, often with a much lower dimensionality than the fixed-point iteration of $(\mathbf{x}, \mathbf{y})$ that is utilized in~\cite{zhang2019accelerating} for the general case and with a lower computational overhead. Moreover, compared to the other acceleration techniques in~\cite{zhang2019accelerating} based on reduced variables, our new approach has the same dimensionality for the fixed-point iteration but requires a much weaker assumption on the optimization problem. 
To achieve stability of the Anderson acceleration, we propose two merit functions for determining whether an accelerated iterate can be accepted: 1) the DR envelope, with a strong guarantee for global convergence of the accelerated solver, and 2) the primal residual norm, which provides fewer theoretical guarantees but incurs lower computational overhead. As far as we are aware of, this is the first global convergence proof for Anderson acceleration on nonconvex ADMM. 
We evaluate our method on a variety of nonconvex ADMM solvers used in computer graphics and other domains. Thanks to its low dimensionality and strong theoretical guarantee, our method achieves more effective acceleration than~\cite{zhang2019accelerating} on many of the experiments. 

To summarize, our main contributions include:
\begin{itemize}
	\item We propose an acceleration technique for nonconvex ADMM solvers, by utilizing their equivalence to DR splitting and applying Anderson acceleration to the fixed-point iteration form of DR splitting. We also propose two types of merit functions that can be used to verify the effectiveness of an accelerated iterate, as well as acceptance criteria for the iterate based on the merit functions.
	\item We prove the convergence of our accelerated solver under appropriate assumptions on the  problem and the algorithm parameters.
\end{itemize}
{"config": "arxiv", "file": "2006.14539/introduction.tex"}