{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T06:59:58Z","timestamp":1790405998753,"version":"4.1.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1719549"],"award-info":[{"award-number":["DMS-1719549"]}],"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>Recent years have witnessed the rapid development of block coordinate update (BCU) methods, which are particularly suitable for problems involving large-sized data and\/or variables. In optimization, BCU first appears as the coordinate descent method that works well for smooth problems or those with separable nonsmooth terms and\/or separable constraints. As nonseparable constraints exist, BCU can be applied under primal-dual settings. In the literature, it has been shown that for weakly convex problems with nonseparable linear constraints, BCU with fully Gauss--Seidel updating rule may fail to converge and that with fully Jacobian rule can converge sublinearly. However, empirically the method with Jacobian update is usually slower than that with Gauss--Seidel rule. To maintain their advantages, we propose a hybrid Jacobian and Gauss--Seidel BCU method for solving linearly constrained multiblock structured convex programming, where the objective may have a nonseparable quadratic term and separable nonsmooth terms. At each primal block variable update, the method approximates the augmented Lagrangian function at an affine combination of the previous two iterates, and the affinely mixing matrix with desired nice properties can be chosen through solving a semidefinite program. We show that the hybrid method enjoys the theoretical convergence guarantee as Jacobian BCU. In addition, we numerically demonstrate that the method can perform as well as the Gauss--Seidel method and better than a recently proposed randomized primal-dual BCU method.<\/jats:p>","DOI":"10.1137\/16m1084705","type":"journal-article","created":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T10:45:50Z","timestamp":1520937950000},"page":"646-670","source":"Crossref","is-referenced-by-count":17,"title":["Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming"],"prefix":"10.1137","volume":"28","author":[{"given":"Yangyang","family":"Xu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb2","unstructured":"X. Cai, D. Han, and X. Yuan,\n                      The Direct Extension of ADMM for Three-Block Separable Convex Minimization Models Is Convergent When One Function is Strongly Convex\n                      , e-print, Optimization Online, 2014."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0826-5"},{"key":"atypb5","unstructured":"C. Chen, M. Li, X. Liu, and Y. Ye,\n                      Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights\n                      , preprint,https:\/\/arxiv.org\/abs\/1508.00193, 2015."},{"key":"atypb6","first-page":"183961","author":"Chen C.","year":"2013","journal-title":"Abstract Appl. Anal."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/140971233"},{"key":"atypb8","unstructured":"Y. Cui, X. Li, D. Sun, and K.C. Toh,\n                      On the Convergence Properties of a Majorized ADMM for Linearly Constrained Convex Optimization Problems with Coupled Objective Functions\n                      , preprint,https:\/\/arxiv.org\/abs\/1502.00098, 2015."},{"key":"atypb9","unstructured":"C. Dang and G. Lan,\n                      Randomized Methods for Saddle Point Computation\n                      , preprint,https:\/\/arxiv.org\/abs\/1409.8625, 2014."},{"key":"atypb10","unstructured":"D. Davis and W. Yin,\n                      A Three-Operator Splitting Scheme and Its Optimization Applications\n                      , preprint,https:\/\/arxiv.org\/abs\/1504.01032, 2015."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-016-0318-2"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-015-0084-0"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"atypb14","unstructured":"X. Gao, B. Jiang, and S. Zhang,\n                      On the Information-Adaptive Variants of the ADMM: An Iteration Complexity Perspective\n                      , e-print, Optimization Online, 2014."},{"key":"atypb15","unstructured":"X. Gao, Y. Xu, and S. Zhang,\n                      Randomized Primal-Dual Proximal Block Coordinate Updates\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.05969, 2016."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-016-0131-5"},{"key":"atypb17","first-page":"41","volume":"9","author":"Glowinski R.","year":"1975","journal-title":"ESAIM Math. Model. Numer. Anal."},{"key":"atypb18","unstructured":"M. Grant, S. Boyd, and Y. Ye,\n                      CVX: MATLAB Software for Disciplined Convex Programming\n                      , Version 2.1, 2017,http:\/\/cvxr.com\/cvx\/(accessed 2-5-18)."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0003-z"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/130922793"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/110822347"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0822"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0060-1"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800040113"},{"key":"atypb26","unstructured":"M. Hong, T.H. Chang, X. Wang, M. Razaviyayn, S. Ma, and Z.Q. Luo,\n                      A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1401.7079, 2014."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1057-8"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Topics in Matrix Analysis\n                      , Cambridge University Press, New York, 1991.","DOI":"10.1017\/CBO9780511840371"},{"key":"atypb29","unstructured":"G. M. James, C. Paulson, and P. Rusmevichientong,\n                      The Constrained Lasso\n                      , Technical report, 2012."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500244"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0850-5"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/140971178"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-015-0092-0"},{"key":"atypb34","unstructured":"Y.F. Liu, X. Liu, and S. Ma,\n                      On the Non-ergodic Convergence Rate of an Inexact Augmented Lagrangian Framework for Composite Convex Programming\n                      , preprint,http:\/\/arxiv.org\/abs\/1603.05738, 2016."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9598-8"},{"key":"atypb37","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , Springer, 2006."},{"key":"atypb38","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4310\/AMSA.2016.v1.n1.a2","volume":"1","author":"Peng Z.","year":"2016","journal-title":"Ann. Math. Sci. Appl."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024950"},{"key":"atypb40","unstructured":"J.C. Pesquet and A. Repetti,\n                      A Class of Randomized Primal-Dual Algorithms for Distributed Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1406.6404, 2014."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/120891009"},{"key":"atypb42","unstructured":"H.J. M. Shi, S. Tu, Y. Xu, and W. Yin,\n                      A Primer on Coordinate Descent Algorithms\n                      , preprint,https:\/\/arxiv.org\/abs\/1610.00040, 2016."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/140964357"},{"key":"atypb44","unstructured":"R. Sun, Z.Q. Luo, and Y. Ye,\n                      On the Expected Convergence of Randomly Permuted ADMM\n                      , preprint,https:\/\/arxiv.org\/abs\/1503.06387, 2015."},{"key":"atypb45","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"Tibshirani R.","year":"1996","journal-title":"J. Roy. Statist. Soc. Ser. B Methodol."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-008-9458-3"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0170-0"},{"key":"atypb50","unstructured":"Y. Wang, W. Yin, and J. Zeng,\n                      Global Convergence of ADMM in Nonconvex Nonsmooth Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1511.06324, 2015."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/0111043"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iat002"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0892-3"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082305"},{"key":"atypb55","first-page":"105","author":"Xu Y.","year":"2015","journal-title":"Springer"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/s10044-015-0485-z"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/120887795"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0376-0"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1084705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:43Z","timestamp":1787336143000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1084705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1084705"],"URL":"https:\/\/doi.org\/10.1137\/16m1084705","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}