  The alternating direction method of multipliers (ADMM) is a popular approach
for solving optimization problems that are potentially non-smooth and with hard
constraints. It has been applied to various computer graphics applications,
including physical simulation, geometry processing, and image processing.
However, ADMM can take a long time to converge to a solution of high accuracy.
Moreover, many computer graphics tasks involve non-convex optimization, and
there is often no convergence guarantee for ADMM on such problems since it was
originally designed for convex optimization. In this paper, we propose a method
to speed up ADMM using Anderson acceleration, an established technique for
accelerating fixed-point iterations. We show that in the general case, ADMM is
a fixed-point iteration of the second primal variable and the dual variable,
and Anderson acceleration can be directly applied. Additionally, when the
problem has a separable target function and satisfies certain conditions, ADMM
becomes a fixed-point iteration of only one variable, which further reduces the
computational overhead of Anderson acceleration. Moreover, we analyze a
particular non-convex problem structure that is common in computer graphics,
and prove the convergence of ADMM on such problems under mild assumptions. We
apply our acceleration technique on a variety of optimization problems in
computer graphics, with notable improvement on their convergence speed.
