{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T08:39:27Z","timestamp":1792226367126,"version":"4.4.0"},"reference-count":76,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["SNF 200021-146750"],"award-info":[{"award-number":["SNF 200021-146750"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["SNF CRSII2-147633"],"award-info":[{"award-number":["SNF CRSII2-147633"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1619884"],"award-info":[{"award-number":["DMS-1619884"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We propose a new and low per-iteration complexity first-order primal-dual optimization framework for a convex optimization template with broad applications. Our analysis relies on a novel combination of three classic ideas applied to the primal-dual gap function: smoothing, acceleration, and homotopy. The algorithms due to the new approach achieve the best-known convergence rate results, in particular when the template consists of only nonsmooth functions. We also outline a restart strategy for the acceleration to significantly enhance the practical performance. We demonstrate relations with the augmented Lagrangian method and show how to exploit the strongly convex objectives with rigorous convergence rate guarantees. We provide representative examples to illustrate that the new methods can outperform the state of the art, including Chambolle--Pock, and the alternating direction method-of-multipliers algorithms. We also compare our algorithms with the well-known Nesterov smoothing method.<\/jats:p>","DOI":"10.1137\/16m1093094","type":"journal-article","created":{"date-parts":[[2018,1,11]],"date-time":"2018-01-11T13:32:37Z","timestamp":1515677557000},"page":"96-134","source":"Crossref","is-referenced-by-count":44,"title":["A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization"],"prefix":"10.1137","volume":"28","author":[{"given":"Quoc","family":"Tran-Dinh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olivier","family":"Fercoq","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volkan","family":"Cevher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,1,11]]},"reference":[{"key":"atypb1","unstructured":"A. Auslender,\n                      Optimisation: Me\u0301thodes Nume\u0301riques\n                      , Masson, Paris, 1976."},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"H. Bauschke and P. Combettes,\n                      Convex Analysis and Monotone Operators Theory in Hilbert Spaces\n                      , Springer-Verlag, Berlin, 2011.","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/100818327"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.10.007"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asr043"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal and A. Nemirovski,\n                      Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications\n                      , MPS\/SIAM Series on Optimization 3, SIAM, Philadelphia, PA, 2001.","DOI":"10.1137\/1.9780898718829"},{"key":"atypb8","unstructured":"D. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice Hall, Englewood Chiffs, NJ, 1989."},{"key":"atypb9","unstructured":"D. P. Bertsekas,\n                      Constrained Optimization and Lagrange Multiplier Methods\n                      , Athena Scientific, Nashua, NH, 1996."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s11750-014-0326-z"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"X. Cai, D. Han, and X. Yuan,\n                      On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function\n                      , Comput. Optim. Appl. (2016), pp. 1-35.","DOI":"10.1007\/s10589-016-9860-y"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2329397"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0826-5"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582566"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/130919362"},{"key":"atypb20","first-page":"185","author":"Combettes P.","year":"2011","journal-title":"Berlin"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-011-0191-y"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0245-9"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/151003076"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/140992291"},{"key":"atypb25","unstructured":"D. Davis and W. Yin,\n                      Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions\n                      , Math. Oper. Res. (2014)."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"W. Deng, M.J. Lai, Z. Peng, and W. Yin,\n                      Parallel multi-block ADMM with ${o}(1\/k)$ convergence\n                      , J. Scientific Computing,https:\/\/doi.org\/10.1007\/s10915-016-0318-2, 2016.","DOI":"10.1007\/s10915-016-0318-2"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"atypb28","unstructured":"J. E. Esser,\n                      Primal-Dual Algorithm for Convex Models and Applications to Image Restoration, Registration and Nonlocal Inpainting\n                      , Ph.D. thesis, University of California, Los Angeles, Los Angeles, CA, 2010."},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"F. Facchinei and J.S. Pang,\n                      Finite-Dimensional Variational Inequalities and Complementarity Problems\n                      , vols. 1-2, Springer-Verlag, Berlin, 2003.","DOI":"10.1007\/b97543"},{"key":"atypb30","unstructured":"O. Fercoq and Z. Qu,\n                      Restarting Accelerated Gradient Methods with a Rough Strong Convexity Estimate\n                      , preprint,arXiv:1609.07358, 2016."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"P. Giselsson and S. Boyd,\n                      Monotonicity and restart in fast gradient methods\n                      , in IEEE Conference on Decision and Control, CDC, Los Angeles, CA, December 2014.","DOI":"10.1109\/CDC.2014.7040179"},{"key":"atypb32","unstructured":"T. Goldstein, E. Esser, and R. Baraniuk,\n                      Adaptive Primal-Dual Hybrid Gradient Methods for Saddle Point Problems\n                      , Technical report, 2013, pp. 1-26,arXiv:1305.0546v1.pdf."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/100814494"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-014-0673-6"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/14096757X"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10334-010-0234-7"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0588-x"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0861-x"},{"key":"atypb40","first-page":"1","author":"Lin T.","year":"2015","journal-title":"J. Sci. Comput., ("},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/140971178"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-015-0092-0"},{"key":"atypb43","unstructured":"Y. Malitsky and T. Pock,\n                      A First-Order Primal-Dual Algorithm with Linesearch\n                      , preprint,arXiv:1608.08883, 2016."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2013.2296605"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/090753127"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/100801652"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"atypb49","unstructured":"I. Necoara and A. Patrascu,\n                      Iteration complexity analysis of dual first order methods for convex programming\n                      , J. Optim. Theory Appl.arXiv:1409.1462, 2014."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2007159"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/120897547"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"atypb53","first-page":"543","volume":"269","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Akad. Nank"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Applied Optimization 87, Kluwer Academic Publishers, Dordrecht, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403422285"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0034-z"},{"key":"atypb58","unstructured":"J. Nocedal and S. Wright,\n                      Numerical Optimization\n                      , 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, Berlin, 2006."},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9150-3"},{"key":"atypb60","first-page":"80","volume":"28","author":"Ouyang H.","year":"2013","journal-title":"JMLR Workshop Conf. Proc."},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/14095697X"},{"key":"atypb62","unstructured":"R. Rockafellar and R. Wets,\n                      Variational Analysis\n                      , Vol. 317, Springer, Berlin, 2004."},{"key":"atypb63","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton Mathematics Series 28, Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1137\/130910774"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008777829180"},{"key":"atypb66","unstructured":"W. Su, S. Boyd, and E. Candes,\n                      A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights\n                      , in Advances in Neural Information Processing Systems (NIPS), 2014, pp. 2510-2518."},{"key":"atypb67","first-page":"721","author":"Tran-Dinh Q.","year":"2014","journal-title":"Canada"},{"key":"atypb68","first-page":"1","author":"Tran-Dinh Q.","year":"2014","journal-title":"LIONS"},{"key":"atypb69","unstructured":"Q. Tran-Dinh and V. Cevher,\n                      Smooth Alternating Direction Methods for Nonsmooth Constrained Convex Optimization\n                      , Technical report, LIONS, EPFL, 2015,arXiv:1507.03734."},{"key":"atypb70","first-page":"374","volume":"15","author":"Tran-Dinh Q.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1137\/0329006"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1080\/01630563.2013.763825"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-022513-115643"},{"key":"atypb74","unstructured":"X. Wang, M. Hong, S. Ma, and Z.Q. Luo,\n                      Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers\n                      , preprint,arXiv:1308.5294, 2013."},{"key":"atypb75","first-page":"551","author":"Wei E.","year":"2013","journal-title":"IEEE"},{"key":"atypb76","doi-asserted-by":"crossref","unstructured":"Y. Xu,\n                      Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming\n                      , preprint,arXiv:1606.09155, 2016.","DOI":"10.1137\/16M1082305"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1093094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:55Z","timestamp":1787336095000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1093094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1093094"],"URL":"https:\/\/doi.org\/10.1137\/16m1093094","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}