Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates

Vassilis Apidopoulos, Cesare Molinari, Juan Peypouquet, Silvia Villa

Introduction

In the realm of convex optimization, the problem of minimizing the sum of two functions, $f(x) + g(Ax)$, where $A$ is a linear operator, is ubiquitous across machine learning, signal processing, and control theory. To solve these problems, primal-dual methods are often employed to decouple the functions $f$ and $g$. While discrete-time algorithms like the Chambolle-Pock method are well-studied, their continuous-time counterparts—modeled as differential equations—offer unique insights into the underlying dynamics of optimization.

However, the standard continuous-time approach, known as the Arrow-Hurwicz flow, suffers from a significant drawback: it often fails to converge to a specific point. Instead, the system's trajectories tend to "orbit" or oscillate around the optimal solution. While the average of the trajectory (ergodic convergence) may eventually reach the solution, the actual state of the system at any given time does not. This paper introduces a novel preconditioned dynamical system designed to stabilize these oscillations and ensure fast, non-ergodic convergence.

The Preconditioned Dynamical System

The authors propose a dynamical system defined by the inclusion: $$P(t)\dot{z}(t) + Mz(t) \ni 0$$ Here, $z(t) = (x(t), y(t))$ represents the primal and dual variables, and $M$ is a maximally monotone operator representing the optimality conditions of the problem. The core innovation lies in the time-varying preconditioner $P(t)$.

By designing $P(t)$ as a block matrix involving time-evolving scalar functions ($\alpha, \beta, \gamma, \delta$), the researchers can manipulate the system's energy dissipation. Specifically, they focus on asymptotically antisymmetric preconditioners, where the off-diagonal terms are negatives of each other. This structure is crucial because it effectively "damps" the rotational behavior inherent in standard primal-dual flows, forcing the trajectory to converge directly toward the solution.

Convergence and Stability Analysis

The theoretical framework relies on Lyapunov stability analysis. By constructing energy estimates, the authors prove that the primal-dual gap—a standard metric for optimality—vanishes over time.

Key Theoretical Findings:

  1. Non-Ergodic Convergence: Unlike traditional proofs that only guarantee the convergence of the time-average, this work demonstrates that the current state of the system converges. This is significantly more practical for real-world applications where one needs a single, high-quality solution at termination.
  2. Tunable Rates: The speed of convergence is directly linked to the growth rates of the preconditioner parameters. By adjusting a single function, $\zeta(t)$, users can achieve sublinear, linear, or even faster convergence rates.
  3. Linear Convergence: For linearly constrained quadratic problems, the authors establish linear convergence rates ($O(e^{-t})$), matching the performance of highly specialized solvers while maintaining a more general framework.

Numerical Validation

To validate these theoretical claims, the researchers conducted experiments using the Julia programming language on several benchmark problems:

  • Quadratic Minimization: Testing on 100-dimensional problems with random matrices.
  • Linearly Constrained Quadratic: A 50-dimensional problem subject to $Ax = b$.
  • LASSO (Sparse Regression): A 20x40 dimensional problem involving non-differentiable functions.

In all instances, the antisymmetric preconditioned system significantly outperformed both the standard Arrow-Hurwicz flow and symmetric preconditioned versions. The results showed that the duality gap reached zero much faster, confirming that the antisymmetric structure is superior for stabilizing primal-dual dynamics.

Discussion and Future Work

This research provides a robust bridge between discrete-time preconditioned algorithms and continuous-time dynamics. By showing that preconditioning is a tool for stabilization rather than just acceleration, the authors open new avenues for designing more reliable optimization solvers.

However, some challenges remain. While the duality gap is proven to vanish, proving that the trajectory always converges to a unique point in all general cases remains an open problem. Additionally, the current theory is restricted to linear coupling ($Ax$). Extending these results to nonlinear coupling in convex-concave Lagrangians and investigating whether specific preconditioners bias the system toward certain solutions (e.g., minimum-norm solutions) are promising directions for future research.

Conclusion

By introducing time-varying, antisymmetric preconditioning to primal-dual flows, this work transforms a traditionally oscillating system into a fast and stable solver. The shift toward non-ergodic convergence rates represents a significant step forward in making continuous-time optimization models more applicable to practical, large-scale problems.

Summary updated

Abstract

We introduce and analyze a continuous primal-dual dynamical system in the context of the minimization problem $f(x)+g(Ax)$, where $f$ and $g$ are convex functions and $A$ is a linear operator. In this setting, the trajectories of the Arrow-Hurwicz continuous flow may not converge, accumulating at points that are not solutions. Our proposal is inspired by the primal-dual algorithm of Chambolle and Pock (2011), where convergence and splitting on the primal-dual variable are ensured by adequately preconditioning the proximal-point algorithm. We consider a family of preconditioners, which are allowed to depend on time and on the operator $A$, but not on the functions $f$ and $g$, and analyze asymptotic properties of the corresponding preconditioned flow. Fast convergence rates for the primal-dual gap and optimality of its (weak) limit points are obtained, in the general case, for asymptotically antisymmetric preconditioners, and, in the case of linearly constrained optimization problems, under milder hypotheses. Numerical examples support our theoretical findings, especially in favor of the antisymmetric preconditioners.
BibTeX
@inproceedings{apidopoulos2025preconditioned,
  author = {Vassilis Apidopoulos and Cesare Molinari and Juan Peypouquet and Silvia Villa},
  title = {{Preconditioned primal-dual dynamics in convex optimization: non-ergodic convergence rates}},
  booktitle = {Nonlinear},
  year = {2025},
  doi = {10.1016/j.nahs.2025.101674},
}
Figure