Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
Abstract
In this paper, we develop accelerated primal-dual dynamics and algorithms for strongly convex-concave saddle point problems with bilinear coupling. Combining strongly convex Nesterov dynamics with scaled heavy-ball dynamics, we propose a second-order primal-dual dynamical system with constant damping and derive an associated algorithm by time discretization and coefficient adjustment. Under suitable conditions on the continuous scaling function β(t) and the discrete scaling sequence βk, we establish primal-dual gap estimates of 𝒪(1/β(t)) in continuous time and 𝒪(1/βk) in discrete time. The maximal admissible growth rates of these scales recover the exponential and linear convergence rates of strongly convex Nesterov methods in continuous and discrete time, respectively. We also prove convergence of the primal-dual trajectory and sequence, even when the dual solution is nonunique. Saddle residual estimates of 𝒪(1/√(β(t))) and 𝒪(1/√(βk)) hold under globally Lipschitz gradients in continuous time and with a possibly nonsmooth dual potential in discrete time. Numerical experiments illustrate the theoretical results and the performance of the proposed methods.
Related
- Accelerated primal-dual dynamics and algorithms for convex optimization with nonlinear inequality constraints
- Tikhonov-Regularized Dynamics and Inexact Algorithms for Nonlinear Saddle-Point Problems
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent
- Synthesis of the Transient Behaviour of Optimization Algorithms for Strongly Convex Objective Functions
BibTeX
@misc{zhang2026accelerated,
title = {{Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems}},
author = {Yun-xi Zhang and Yi-bin Xiao and Xin He},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29723},
eprint = {2610.29723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29723},
}
RIS
TY - UNPB
TI - Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
AU - Yun-xi Zhang
AU - Yi-bin Xiao
AU - Xin He
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29723
UR - https://arxiv.org/abs/2610.29723
AB - In this paper, we develop accelerated primal-dual dynamics and algorithms for strongly convex-concave saddle point problems with bilinear coupling. Combining strongly convex Nesterov dynamics with scaled heavy-ball dynamics, we propose a second-order primal-dual dynamical system with constant damping and derive an associated algorithm by time discretization and coefficient adjustment. Under suitable conditions on the continuous scaling function β(t) and the discrete scaling sequence β_k, we establish primal-dual gap estimates of 𝒪(1/β(t)) in continuous time and 𝒪(1/β_k) in discrete time. The maximal admissible growth rates of these scales recover the exponential and linear convergence rates of strongly convex Nesterov methods in continuous and discrete time, respectively. We also prove convergence of the primal-dual trajectory and sequence, even when the dual solution is nonunique. Saddle residual estimates of 𝒪(1/√(β(t))) and 𝒪(1/√(β_k)) hold under globally Lipschitz gradients in continuous time and with a possibly nonsmooth dual potential in discrete time. Numerical experiments illustrate the theoretical results and the performance of the proposed methods.
ER -