Accelerated augmented Lagrangian schemes for convex linearly constrained problems achieve o(1/k^2) rates on feasibility violation and objective residual plus iterate convergence under critical parameters.
Trajectory convergence and $o(t^{-2})$ rates for Nesterov accelerated primal-dual dynamics without Lipschitz gradient assumption
2 Pith papers cite this work. Polarity classification is still indexing.
abstract
We consider the Nesterov accelerated primal-dual dynamical system \[ \begin{cases} \ddot{x}(t)+\dfrac{\alpha}{t}\dot{x}(t) +\nabla f(x(t)) +A^\top\bigl(\lambda(t)+\theta t\dot{\lambda}(t)\bigr)+\beta A^\top(Ax(t)-b)=0,\\[0.6em] \ddot{\lambda}(t)+\dfrac{\alpha}{t}\dot{\lambda}(t) -\bigl(A(x(t)+\theta t\dot{x}(t))-b\bigr)=0, \end{cases} \] which is linked to the linearly constrained optimization problem $ \min_{x\in\mathbb{R}^n} f(x),\ s.t.\ Ax=b, $ where $\alpha\ge 3$ and $f$ is convex and continuously differentiable. In a Hilbert framework, the weak convergence of its trajectory was established by Bo\c{t} and Nguyen (J. Differential Equations, 303:369--406, 2021) under $\alpha>3$ and the Lipschitz continuity assumption on $\nabla f$. In this paper, we prove in finite-dimensional spaces that the trajectory converges to a primal-dual solution for $\alpha\ge3$, without assuming Lipschitz continuity of $\nabla f$. Moreover, when $\alpha>3$, we establish improved $o(t^{-2})$ convergence rates for both the objective residual and the feasibility violation. Our analysis relies on Bregman-distance arguments, instead of the Lipschitz continuity of $\nabla f$. The same strategy can also be extended to time-scaled primal-dual dynamics to obtain analogous convergence results. To the best of our knowledge, this is the first results in this topic without Lipschitz gradient assumption. Our result also present the first work on the convergence of the trajectory of the accelerated primal-dual dynamical system for the critical case $\alpha=3$.
fields
math.OC 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
Proves convergence to saddle points and o(1/t²) gap rates for continuous-time dynamics with α/t damping (α≥3) and for a structure-preserving discretization under a t_k sequence condition with ρ≤1.
citing papers explorer
-
Convergence of iterates and improved rates for accelerated augmented Lagrangian methods for linearly constrained convex optimization
Accelerated augmented Lagrangian schemes for convex linearly constrained problems achieve o(1/k^2) rates on feasibility violation and objective residual plus iterate convergence under critical parameters.
-
Fast primal-dual methods for convex-concave bilinear saddle point problems: continuous-time dynamics and discrete algorithms
Proves convergence to saddle points and o(1/t²) gap rates for continuous-time dynamics with α/t damping (α≥3) and for a structure-preserving discretization under a t_k sequence condition with ρ≤1.