Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping

DOI10.1007/S00245-023-09999-9zbMATH Open1522.37097arXiv2209.06438OpenAlexW4378878692MaRDI QIDQ6166339FDOQ6166339

Author name not available (Why is that?)

Publication date: 6 July 2023

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: In this work, we approach the minimization of a continuously differentiable convex function under linear equality constraints by a second-order dynamical system with an asymptotically vanishing damping term. The system under consideration is a time rescaled version of another system previously found in the literature. We show fast convergence of the primal-dual gap, the feasibility measure, and the objective function value along the generated trajectories. These convergence rates now depend on the rescaling parameter, and thus can be improved by choosing said parameter appropriately. When the objective function has a Lipschitz continuous gradient, we show that the primal-dual trajectory asymptotically converges weakly to a primal-dual optimal solution to the underlying minimization problem. We also exhibit improved rates of convergence of the gradient along the primal trajectories and of the adjoint of the corresponding linear operator along the dual trajectories. Even in the unconstrained case, some trajectory convergence result seems to be new. We illustrate the theoretical outcomes through numerical experiments.

Full work available at URL: https://arxiv.org/abs/2209.06438

Recommendations

• Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping
• A primal-dual approach to comparative dynamics with time-dependent parameters in variational calculus
• Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems
• “Second-Order Primal” + “First-Order Dual” Dynamical Systems With Time Scaling for Linear Equality Constrained Convex Optimization Problems
• Time-dependent rescalings and Lyapunov functionals for some kinetic and fluid models
• Optimal dichotomy of temporal scales and boundedness/stability of time-varying multidimensional nonlinear systems
• On time scaling for nonlinear systems: Application to linearization
• Asymptotic stability for dynamic equations on time scales
• scientific article
• scientific article; zbMATH DE number 966385

zbMATH Keywords

convergence rateaugmented Lagrangian methodNesterov's accelerated gradient methodLyapunov analysistime rescalingdamped inertial dynamicsprimal-dual dynamical systemtrajectory convergence

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Dynamical systems in optimization and economics (37N40) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Approximation methods and numerical treatment of dynamical systems (37M99)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• Convex analysis and monotone operator theory in Hilbert spaces
• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Fast Alternating Direction Optimization Methods
• Conjugate duality in convex optimization
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• Randomized optimal consensus of multi-agent systems
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
• Some methods of speeding up the convergence of iteration methods
• A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
• On the Long Time Behavior of Second Order Differential Equations with Asymptotically Small Dissipation
• On the long time behavior of second order differential equations with asymptotically small dissipation
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Distributed gradient algorithm for constrained optimization with application to load sharing in power systems
• Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems
• New Proximal Point Algorithms for Convex Minimization
• Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• A primal-dual dynamical approach to structured convex minimization problems
• Combining fast inertial dynamics for convex optimization with Tikhonov regularization
• Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
• First-order optimization algorithms via inertial systems with Hessian driven damping
• Asymptotic for a second-order evolution equation with convex potential andvanishing damping term
• Distributed Continuous-Time Algorithms for Nonsmooth Extended Monotropic Optimization Problems
• Fast Proximal Methods via Time Scaling of Damped Inertial Dynamics
• Accelerated Optimization for Machine Learning
• Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem
• Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics
• Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
• Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping
• Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems
• Title not available (Why is that?)
• Fast convex optimization via a third-order in time evolution equation
• Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems
• Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates

Cited In (3)

• A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem
• A primal-dual approach to comparative dynamics with time-dependent parameters in variational calculus
• Fast convergence rates and trajectory convergence of a Tikhonov regularized inertial primal-dual dynamical system with time scaling and vanishing damping

This page was built for publication: Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166339)