Technical Papers Fast-Forward :
Accelerating ADMM for Efficient Simulation and Optimization
Technical Papers Fast-Forward
TimeSunday, 17 November 201918:14 - 18:15
LocationGreat Hall 1&2
DescriptionThe alternating direction method of multipliers (ADMM) is a popular method for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications including physics 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 problems, 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, which is an established technique to accelerate a fixed-point iteration. 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 commonly used in computer graphics, and prove the convergence of ADMM on such problem under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.