Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem

Ke-wei Ding (), Jörg Fliege () and Phan Tu Vuong ()
Additional contact information
Ke-wei Ding: Southwest Minzu University
Jörg Fliege: University of Southampton
Phan Tu Vuong: University of Southampton

Computational Optimization and Applications, 2025, vol. 90, issue 1, No 6, 192 pages

Abstract: Abstract 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 $$O\left( 1/k^2 \right) $$ O 1 / k 2 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.

Keywords: Saddle point problem; Primal-dual dynamical system; Convergence rate; Numerical algorithm; Nesterov’s accelerated gradient method; Iterates convergence; 37N40; 49J35; 65K10; 68Q25; 90C25 (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-024-00626-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:90:y:2025:i:1:d:10.1007_s10589-024-00626-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-024-00626-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().