Accelerating ADMM for efficient simulation and optimization

Zhang, Juyong, Peng, Yue, Ouyang, Wenqing and Deng, Bailin ORCID: https://orcid.org/0000-0002-0158-7670 2019. Accelerating ADMM for efficient simulation and optimization. ACM Transactions on Graphics 38 (6) , 163. 10.1145/3355089.3356491

	PDF - Accepted Post-Print Version Download (8MB)
Preview	PDF - Supplemental Material Download (886kB) | Preview
	Video (MPEG) - Supplemental Material Download (7MB)

Abstract

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Additional Information:	"© ACM, 2019. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, (VOL 38, ISS 6) http://dx.doi.org/10.1145/3355089.3356491
Publisher:	Association for Computing Machinery (ACM)
ISSN:	0730-0301
Date of First Compliant Deposit:	30 August 2019
Date of Acceptance:	29 August 2019
Last Modified:	06 Nov 2024 11:45
URI:	https://orca.cardiff.ac.uk/id/eprint/125193

Citation Data

Cited 20 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item