{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:07:50Z","timestamp":1784268470766,"version":"3.55.0"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3355089.3356491","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T20:27:58Z","timestamp":1573244878000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Accelerating ADMM for efficient simulation and optimization"],"prefix":"10.1145","volume":"38","author":[{"given":"Juyong","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yue","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenqing","family":"Ouyang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bailin","family":"Deng","sequence":"additional","affiliation":[{"name":"Cardiff University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2013.2258354"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321296.321305"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03171.x"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12178"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd Neal Parikh Eric Chu Borja Peleato Jonathan Eckstein et al. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning 3 1 (2011) 1--122.","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201387"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCI.2016.2629286"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2012.2208955"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"R. Chartrand and B. Wohlberg. 2013. A nonconvex ADMM algorithm for group sparsity with sparse groups (ICASSP 2013). 6009--6013.","DOI":"10.1109\/ICASSP.2013.6638818"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13243"},{"key":"e_1_2_2_12_1","volume-title":"Combettes and Jean-Christophe Pesquet","author":"Patrick","year":"2011","unstructured":"Patrick L. Combettes and Jean-Christophe Pesquet. 2011. Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Heinz H. Bauschke, Regina S. Burachik, Patrick L. Combettes, Veit Elser, D. Russell Luke, and Henry Wolkowicz (Eds.). 185--212."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.01.004"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2162831"},{"key":"e_1_2_2_17_1","volume-title":"A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically). arXiv preprint arXiv:1810.08455","author":"Evans Claire","year":"2018","unstructured":"Claire Evans, Sara Pollock, Leo G. Rebholz, and Mengying Xiao. 2018. A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically). arXiv preprint arXiv:1810.08455 (2018)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1996.0059"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.617"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2010.2053941"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Michel Fortin and Roland Glowinski. 1983. Chapter III On Decomposition-Coordination Methods Using an Augmented Lagrangian. In Studies in Mathematics and Its Applications. Vol. 15. Elsevier 97--146.","DOI":"10.1016\/S0168-2024(08)70028-6"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601106"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2354892"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2564160"},{"key":"e_1_2_2_26_1","volume-title":"ADMM: Algorithm and convergence analysis (ICASSP","author":"Hajinezhad D.","year":"2016","unstructured":"D. Hajinezhad, T. Chang, X. Wang, Q. Shi, and M. Hong. 2016. Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis (ICASSP 2016). 4742--4746."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925875"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1076770"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990309"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.271"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Mojtaba Kadkhodaie Konstantina Christakopoulou Maziar Sanjabi and Arindam Banerjee. 2015. Accelerated alternating direction method of multipliers (KDD '15). 497--506.","DOI":"10.1145\/2783258.2783400"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925920"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9740-x"},{"key":"e_1_2_2_34_1","volume-title":"Optimization","author":"Lange Kenneth","unstructured":"Kenneth Lange. 2004. The MM Algorithm. In Optimization. Springer, 119--136."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998135"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2454476"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2257618"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/140971178"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867846"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.39"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1731309.1731336"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2990496"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141941"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024174"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2015.2476198"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964967"},{"key":"e_1_2_2_48_1","volume-title":"Distributed non-convex ADMM-based inference in large-scale random fields (BMVC","author":"Miksik Ondrej","year":"2014","unstructured":"Ondrej Miksik, Vibhav Vineet, Patrick P\u00e9rez, and Phillip Torr. 2014. Distributed non-convex ADMM-based inference in large-scale random fields (BMVC 2014)."},{"key":"e_1_2_2_49_1","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate O(1\/k2)","volume":"27","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov. 1983. A method of solving a convex programming problem with convergence rate O(1\/k2). Soviet Mathematics Doklady 27 (1983), 372--376.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_2_50_1","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Yurii","unstructured":"Yurii Nesterov. 2013. Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12429"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508417"},{"key":"e_1_2_2_53_1","volume-title":"Wright","author":"Nocedal Jorge","year":"2006","unstructured":"Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2nd ed.). Springer-Verlag New York."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730875"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3016963"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201290"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.09.008"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.11.018"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0009-2614(80)80396-4"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540030413"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983621"},{"key":"e_1_2_2_62_1","volume-title":"Convex Analysis","author":"Rockafellar Ralph Tyrell","unstructured":"Ralph Tyrell Rockafellar. 1997. Convex Analysis. Princeton University Press."},{"key":"e_1_2_2_63_1","volume-title":"Variational Analysis","author":"Tyrrell Rockafellar R","unstructured":"R Tyrrell Rockafellar and Roger J-B Wets. 2009. Variational Analysis. Vol. 317. Springer Science & Business Media."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10910-011-9863-y"},{"key":"e_1_2_2_65_1","unstructured":"Christian Schumacher Bernhard Thomaszewski Stelian Coros Sebastian Martin Robert Sumner and Markus Gross. 2012. Efficient simulation of example-based materials (SCA '12). 1--8."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2304432"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2302746"},{"key":"e_1_2_2_69_1","unstructured":"Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling (SGP '07). 109--116."},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/110835530"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2018.07.007"},{"key":"e_1_2_2_72_1","unstructured":"J. Tao J. Zhang B. Deng Z. Fang Y. Peng and Y. He. 2019. Parallel and scalable heat methods for geodesic distance computation. IEEE Transactions on Pattern Analysis and Machine Intelligence (2019)."},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080677"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/130919398"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/10078356X"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201299"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-018-0757-z"},{"key":"e_1_2_2_80_1","volume-title":"Alternating direction methods for classical and ptychographic phase retrieval. Inverse Problems 28, 11","author":"Wen Zaiwen","year":"2012","unstructured":"Zaiwen Wen, Chao Yang, Xin Liu, and Stefano Marchesini. 2012. Alternating direction methods for classical and ptychographic phase retrieval. Inverse Problems 28, 11 (2012)."},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2011.5.237"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073662"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661263"},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2535218"},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661255"},{"key":"e_1_2_2_86_1","volume-title":"Globally convergent type-I Anderson acceleration for non-smooth fixed-point iterations. arXiv preprint arXiv:1808.03971","author":"Zhang Junzi","year":"2018","unstructured":"Junzi Zhang, Brendan O'Donoghue, and Stephen Boyd. 2018. Globally convergent type-I Anderson acceleration for non-smooth fixed-point iterations. arXiv preprint arXiv:1808.03971 (2018)."},{"key":"e_1_2_2_87_1","volume-title":"Kwok","author":"Zhang Ruiliang","year":"2014","unstructured":"Ruiliang Zhang and James T. Kwok. 2014. Asynchronous distributed ADMM for consensus optimization (ICML '14). II-1701--II-1709."},{"key":"e_1_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1059941"},{"key":"e_1_2_2_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355089.3356491","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355089.3356491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:40Z","timestamp":1750203880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355089.3356491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,8]]},"references-count":89,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3355089.3356491"],"URL":"https:\/\/doi.org\/10.1145\/3355089.3356491","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,8]]},"assertion":[{"value":"2019-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}