Convergence Analysis via ODE Approach for Convex Optimization with Linear Equality Constraints
Abstract
This paper studies the continuous-time dynamics of primal-dual algorithms for linearly constrained convex optimization problems and provides a quantitative convergence analysis using the Lyapunov functions. With the growing prevalence of sparse and low-rank models, large-scale problems involving nonsmooth objective functions have become increasingly important. Our approach addresses nonsmooth and nonstrong convex objective functions, which is particularly effective in extending classical accelerated methods to broader large-scale optimization problems. Building upon the ordinary differential equation (ODE) approach inspired by the recent work on Nesterov's acceleration methods, we extend the analysis to an ODE associated with an optimization problem with linear equality constraints. Furthermore, to relax strong assumptions, we introduce two geometric conditions the Flatness condition and the Growth condition and derive explicit convergence rates depending on the local geometry and algorithmic parameter. When the objective function is convex and the Lagrangian satisfies the Flatness condition, an appropriate parameter choice yields a worst-case convergence rate of O(1/t^2). Furthermore, incorporating the Growth condition guarantees this worst-case rate of O(1/t^2) for any function satisfying these assumptions if and only if the parameter is chosen above a suitable threshold; under this condition, even faster convergence can be achieved. For the algorithmic construction, a numerical scheme is derived by discretizing the proposed ODE. We also investigate the influence of algorithm parameters and provide insights into their optimal selection. Finally, preliminary numerical experiments are provided to validate the consistency with the theoretical results.
Related
- Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints
- R-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
- Global and Unconditional R-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints
BibTeX
@misc{ishii2026convergence,
title = {{Convergence Analysis via ODE Approach for Convex Optimization with Linear Equality Constraints}},
author = {Chise Ishii and Yasushi Narushima},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.17819},
eprint = {2605.17819},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.17819},
}
RIS
TY - UNPB
TI - Convergence Analysis via ODE Approach for Convex Optimization with Linear Equality Constraints
AU - Chise Ishii
AU - Yasushi Narushima
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2605.17819
UR - https://arxiv.org/abs/2605.17819
AB - This paper studies the continuous-time dynamics of primal-dual algorithms for linearly constrained convex optimization problems and provides a quantitative convergence analysis using the Lyapunov functions. With the growing prevalence of sparse and low-rank models, large-scale problems involving nonsmooth objective functions have become increasingly important. Our approach addresses nonsmooth and nonstrong convex objective functions, which is particularly effective in extending classical accelerated methods to broader large-scale optimization problems. Building upon the ordinary differential equation (ODE) approach inspired by the recent work on Nesterov's acceleration methods, we extend the analysis to an ODE associated with an optimization problem with linear equality constraints. Furthermore, to relax strong assumptions, we introduce two geometric conditions the Flatness condition and the Growth condition and derive explicit convergence rates depending on the local geometry and algorithmic parameter. When the objective function is convex and the Lagrangian satisfies the Flatness condition, an appropriate parameter choice yields a worst-case convergence rate of O(1/t^2). Furthermore, incorporating the Growth condition guarantees this worst-case rate of O(1/t^2) for any function satisfying these assumptions if and only if the parameter is chosen above a suitable threshold; under this condition, even faster convergence can be achieved. For the algorithmic construction, a numerical scheme is derived by discretizing the proposed ODE. We also investigate the influence of algorithm parameters and provide insights into their optimal selection. Finally, preliminary numerical experiments are provided to validate the consistency with the theoretical results.
ER -