{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T07:28:13Z","timestamp":1777447693967,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T00:00:00Z","timestamp":1731888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T00:00:00Z","timestamp":1731888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100018927","name":"Southwest Minzu University","doi-asserted-by":"publisher","award":["2024SXXYKY002"],"award-info":[{"award-number":["2024SXXYKY002"]}],"id":[{"id":"10.13039\/501100018927","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100018927","name":"Southwest Minzu University","doi-asserted-by":"publisher","award":["2024CXTD19"],"award-info":[{"award-number":["2024CXTD19"]}],"id":[{"id":"10.13039\/501100018927","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper studies the convergence rate of a second-order dynamical system associated with a nonsmooth bilinearly coupled convex-concave saddle point problem, as well as the convergence rate of its corresponding discretizations. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on an implicit discretization scheme, we propose a primal-dual algorithm and provide a non-ergodic convergence rate under a general setting for the inertial parameters when one objective function is continuously differentiable and convex and the other is a proper, convex and lower semicontinuous function. For this algorithm we derive a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O\\left( 1\/k^2 \\right) $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> convergence rate under three classical rules proposed by Nesterov, Chambolle-Dossal and Attouch-Cabot without assuming strong convexity, which is compatible with the results of the continuous-time dynamic system.  For the case when both objective functions are continuously differentiable and convex, we further present a primal-dual algorithm based on an explicit discretization. We provide a corresponding non-ergodic convergence rate for this algorithm and show that the sequence of iterates generated weakly converges to a primal-dual optimal solution. Finally, we present numerical experiments that indicate the superior numerical performance of both algorithms.<\/jats:p>","DOI":"10.1007\/s10589-024-00626-z","type":"journal-article","created":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T19:49:00Z","timestamp":1731959340000},"page":"151-192","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem"],"prefix":"10.1007","volume":"90","author":[{"given":"Ke-wei","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4459-5419","authenticated-orcid":false,"given":"J\u00f6rg","family":"Fliege","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phan Tu","family":"Vuong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,18]]},"reference":[{"key":"626_CR1","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/17M1114739","volume":"28","author":"H Attouch","year":"2018","unstructured":"Attouch, H., Cabot, A.: Convergence rates of inertial forward-backward algorithms. SIAM J. Optimiz. 28, 849\u2013874 (2018)","journal-title":"SIAM J. Optimiz."},{"key":"626_CR2","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/s10957-021-01859-2","volume":"193","author":"H Attouch","year":"2022","unstructured":"Attouch, H., Chbani, Z., Fadili, J., Riahi, H.: Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics. J. Optimiz. Theory Appl. 193, 704\u2013736 (2022)","journal-title":"J. Optimiz. Theory Appl."},{"key":"626_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10107-016-0992-8","volume":"168","author":"H Attouch","year":"2018","unstructured":"Attouch, H., Chbani, Z., Peypouquet, J., Redont, P.: Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Math. Program. 168, 123\u2013175 (2018)","journal-title":"Math. Program."},{"key":"626_CR4","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1137\/15M1046095","volume":"26","author":"H Attouch","year":"2016","unstructured":"Attouch, H., Peypouquet, J.: The rate of convergence of Nesterov\u2019s accelerated forward-backward method is actually faster than $$1\/k^2$$. SIAM J. Optim. 26, 1824\u20131834 (2016)","journal-title":"SIAM J. Optim."},{"key":"626_CR5","doi-asserted-by":"publisher","first-page":"5734","DOI":"10.1016\/j.jde.2016.08.020","volume":"261","author":"H Attouch","year":"2016","unstructured":"Attouch, H., Peypouquet, J., Redont, P.: Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differ. Equations 261, 5734\u20135783 (2016)","journal-title":"J. Differ. Equations"},{"key":"626_CR6","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10107-019-01415-x","volume":"184","author":"HH Bauschke","year":"2020","unstructured":"Bauschke, H.H., Bui, M.N., Wang, X.: Applying FISTA to optimization problems (with or) without minimizers. Math. Program. 184, 349\u2013381 (2020)","journal-title":"Math. Program."},{"key":"626_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5","volume-title":"Convex analysis and monotone operator theory in Hilbert spaces","author":"HH Bauschke","year":"2017","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in Hilbert spaces. Springer, New York (2017)"},{"key":"626_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"626_CR9","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1137\/21M1420939","volume":"4","author":"A B\u00f6hm","year":"2022","unstructured":"B\u00f6hm, A., Sedlmayer, M., Csetnek, E.R., Bo\u0163, R.I.: Two steps at a time\u2013taking GAN training in stride with Tseng\u2019s method. SIAM J. Math. Data Sci. 4, 750\u2013771 (2022)","journal-title":"SIAM J. Math. Data Sci."},{"key":"626_CR10","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.jde.2021.09.021","volume":"303","author":"RI Bo\u0163","year":"2021","unstructured":"Bo\u0163, R.I., Nguyen, D.K.: Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping. J. Differ. Eq. 303, 369\u2013406 (2021)","journal-title":"J. Differ. Eq."},{"key":"626_CR11","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s10107-022-01879-4","volume":"200","author":"RI Bo\u0163","year":"2023","unstructured":"Bo\u0163, R.I., Csetnek, E.R., Nguyen, D.K.: Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates. Math. Program. 200, 147\u2013197 (2023)","journal-title":"Math. Program."},{"key":"626_CR12","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1007\/s10589-022-00378-8","volume":"86","author":"RI Bo\u0163","year":"2023","unstructured":"Bo\u0163, R.I., Csetnek, E.R., Sedlmayer, M.: An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function. Comput. Optim. Appl. 86, 925\u2013966 (2023)","journal-title":"Comput. Optim. Appl."},{"key":"626_CR13","first-page":"1","volume":"24","author":"RI Bo\u0163","year":"2023","unstructured":"Bo\u0163, R.I., Sedlmayer, M., Vuong, P.T.: A relaxed inertial forward-backward-forward algorithm for solving monotone inclusions with application to GANs. J. Mach. Learn Res. 24, 1\u201337 (2023)","journal-title":"J. Mach. Learn Res."},{"key":"626_CR14","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"key":"626_CR15","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s10107-015-0957-3","volume":"159","author":"A Chambolle","year":"2016","unstructured":"Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159, 253\u2013287 (2016)","journal-title":"Math. Program."},{"key":"626_CR16","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1007\/s10957-015-0746-4","volume":"166","author":"A Chambolle","year":"2015","unstructured":"Chambolle, A., Dossal, C.: On the convergence of the iterates of the \u201cfast iterative shrinkage\/thresholding algorithm\u2019\u2019. J. Optim. Theory Appl. 166, 968\u2013982 (2015)","journal-title":"J. Optim. Theory Appl."},{"key":"626_CR17","doi-asserted-by":"publisher","first-page":"1779","DOI":"10.1137\/130919362","volume":"24","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optimiz. 24, 1779\u20131814 (2014)","journal-title":"SIAM J. Optimiz."},{"key":"626_CR18","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s10957-012-0245-9","volume":"158","author":"L Condat","year":"2013","unstructured":"Condat, L.: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158, 460\u2013479 (2013)","journal-title":"J. Optim. Theory Appl."},{"key":"626_CR19","unstructured":"Du, S.S., Chen, J., Li, L., Xiao, L., Zhou, D.: Stochastic variance reduction methods for policy evaluation. In: International conference on machine learning pp. 1049-1058 (2017)"},{"key":"626_CR20","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1137\/09076934X","volume":"3","author":"E Esser","year":"2010","unstructured":"Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal- dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015\u20131046 (2010)","journal-title":"SIAM J. Imaging Sci."},{"key":"626_CR21","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1137\/21M1453463","volume":"15","author":"B He","year":"2022","unstructured":"He, B., Ma, F., Xu, S., Yuan, X.: A generalized primal-dual algorithm with improved convergence condition for saddle point problems. SIAM J. Imaging Sci. 15, 1157\u20131183 (2022)","journal-title":"SIAM J. Imaging Sci."},{"key":"626_CR22","doi-asserted-by":"publisher","first-page":"110547","DOI":"10.1016\/j.automatica.2022.110547","volume":"146","author":"X He","year":"2022","unstructured":"He, X., Hu, R., Fang, Y.P.: Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem. Automatica 146, 110547 (2022)","journal-title":"Automatica"},{"key":"626_CR23","doi-asserted-by":"publisher","first-page":"1669","DOI":"10.1007\/s11075-021-01246-y","volume":"90","author":"X He","year":"2022","unstructured":"He, X., Hu, R., Fang, Y.P.: Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems. Numer. Algorithms 90, 1669\u20131690 (2022)","journal-title":"Numer. Algorithms"},{"key":"626_CR24","unstructured":"He, X., Huang, N., Fang, Y.P.: Non-ergodic convergence rates of first-order primal-dual algorithms for saddle point problems. (2023) arXiv:2311.11274"},{"key":"626_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00245-023-10102-5","volume":"89","author":"X He","year":"2024","unstructured":"He, X., Hu, R., Fang, Y.P.: A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem. Appl. Math. Opt. 89, 1\u201322 (2024)","journal-title":"Appl. Math. Opt."},{"key":"626_CR26","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1090\/mcom\/3610","volume":"90","author":"F Jiang","year":"2021","unstructured":"Jiang, F., Cai, X., Wu, Z., Han, D.: Approximate first-order primal-dual algorithms for saddle point problems. Math. Comput. 90, 1227\u20131262 (2021)","journal-title":"Math. Comput."},{"key":"626_CR27","first-page":"747","volume":"12","author":"GM Korpelevich","year":"1976","unstructured":"Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekon. Mat. Metody 12, 747\u2013756 (1976)","journal-title":"Ekon. Mat. Metody"},{"key":"626_CR28","unstructured":"Kovalev, D., Gasnikov, A., Richt\u00e1rik, P.: Accelerated primal-dual gradient method for smooth and convex-concave saddle-point problems with bilinear coupling. (2021) arXiv:2112.15199"},{"key":"626_CR29","unstructured":"Li, C.J., Yuan, A., Gidel, G., Jordan, MI.: Nesterov meets optimism: rate-optimal optimistic-gradient-based method for stochastic bilinearly-coupled minimax optimization. (2022) arXiv:2210.17550"},{"key":"626_CR30","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/0716071","volume":"16","author":"PL Lions","year":"1979","unstructured":"Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964\u2013979 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"626_CR31","first-page":"681","volume":"41","author":"R May","year":"2017","unstructured":"May, R.: Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turk. J. Math. 41, 681\u2013685 (2017)","journal-title":"J. Math."},{"key":"626_CR32","doi-asserted-by":"publisher","first-page":"3230","DOI":"10.1137\/19M127375X","volume":"30","author":"A Mokhtari","year":"2020","unstructured":"Mokhtari, A., Ozdaglar, A.E., Pattathil, S.: Convergence rate of $$O(1\/k)$$ for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM J. Optimiz. 30, 3230\u20133251 (2020)","journal-title":"SIAM J. Optimiz."},{"key":"626_CR33","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $$O(\\frac{1}{k^2})$$. Soviet Math. Dokl. 27, 372\u2013376 (1983)","journal-title":"Soviet Math. Dokl."},{"key":"626_CR34","doi-asserted-by":"publisher","first-page":"1850","DOI":"10.1137\/19M1272767","volume":"30","author":"O Sebbouh","year":"2020","unstructured":"Sebbouh, O., Dossal, C., Rondepierre, A.: Convergence rates of damped inertial dynamics under geometric conditions and perturbations. SIAM J. Optimiz. 30, 1850\u20131877 (2020)","journal-title":"SIAM J. Optimiz."},{"key":"626_CR35","first-page":"1","volume":"17","author":"W Su","year":"2016","unstructured":"Su, W., Boyd, S., Cand\u00e9s, E.J.: A differential equation for modeling Nesterov\u2019s accelerated gradient method: theory and insights. J. Mach. Learn. Res. 17, 1\u201343 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"626_CR36","unstructured":"Thekumparampil, K.K., He, N., Oh, S.: Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In: International conference on artificial intelligence and statistics, pp. 4281-4308 (2022)"},{"key":"626_CR37","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1007\/s11590-021-01775-4","volume":"16","author":"Q Tran-Dinh","year":"2022","unstructured":"Tran-Dinh, Q.: A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm. Optim. Lett. 16, 1235\u20131257 (2022)","journal-title":"Optim. Lett."},{"key":"626_CR38","doi-asserted-by":"publisher","first-page":"7362","DOI":"10.1016\/j.ifacol.2020.12.1257","volume":"53","author":"X Zeng","year":"2020","unstructured":"Zeng, X., Lei, J., Chen, J.: Accelerated first-order continuous-time algorithm for solving convex-concave bilinear saddle point problem. IFAC-PapersOnLine 53, 7362\u20137367 (2020)","journal-title":"IFAC-PapersOnLine"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00626-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00626-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00626-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:33:01Z","timestamp":1736771581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00626-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,18]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["626"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00626-z","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,18]]},"assertion":[{"value":"3 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal rights"}}]}}