Search

First-order optimization algorithms can be considered as a discretization of ordinary differential equations (ODEs) (Su et al. in Adv Neural Inf Process Syst 27, 2014). In this perspective, studying the properties of the corresponding trajectories may lead to convergence results which can be transfered to the numerical scheme. In this paper we analyse the following ODE introduced by Attouch et al. (J Differ Equ 261(10):5734–5783, 2016): ∀ t ⩾ t 0 , x ¨ (t) + α t x ˙ (t) + β H F (x (t)) x ˙ (t) + ∇ F (x (t)) = 0 , where α > 0 , β > 0 and H F denotes the Hessian of F. This ODE can be derived to build numerical schemes which do not require F to be twice differentiable as shown in Attouch et al. (Math Program 1–43, 2020) and Attouch et al. (Optimization 72:1–40, 2021). We provide strong convergence results on the error F (x (t)) - F ∗ and integrability properties on ‖ ∇ F (x (t)) ‖ under some geometry assumptions on F such as quadratic growth around the set of minimizers. In particular, we show that the decay rate of the error for a strongly convex function is O (t - α - ε) for any ε > 0 . These results are briefly illustrated at the end of the paper. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a speed restarting scheme for the inertial dynamics with Hessian-driven damping, introduced by Attouch et al. (J Differ Equ 261(10):5734–5783, 2016). We establish a linear convergence rate for the function values along the restarted trajectories. Numerical experiments suggest that the Hessian-driven damping and the restarting scheme together improve the performance of the dynamics and corresponding iterative algorithms in practice. [ABSTRACT FROM AUTHOR]

Let H be a real Hilbert space, and f : H → R be a convex twice differentiable function whose solution set argmin f is nonempty. We investigate the long time behavior of the trajectories of the vanishing damped dynamical system with Tikhonov regularizing term and Hessian-driven damping x ¨ (t) + α x ˙ (t) + δ ∇ 2 f (x (t)) x ˙ (t) + β (t) ∇ f (x (t)) + c x (t) = 0 where α , c , δ are three positive constants, and the time scale parameter β is a positive nondecreasing function such that lim t → + ∞ β (t) = + ∞ . Under some assumptions on the parameter β , we will show rapid convergence of values, strong convergence toward the minimum norm element of argmin f , and rapid convergence of the gradients toward zero. Note that the Hessian-driven damping significantly reduces the oscillatory aspects, and the time scale parameter β improves the rate of convergences mentioned above. As particular cases of β , we set β (t) = t p ln q (t) , for (p , q) ∈ (R +) 2 ∖ { (0 , 0) } , and β (t) = e γ t p , for p ∈ ] 0 , 1 [ and γ > 0 . The manuscript concludes with two numerical examples and comments on their performance. [ABSTRACT FROM AUTHOR]

In a Hilbert framework, for general convex differentiable optimization, we consider accelerated gradient dynamics combining Tikhonov regularization with Hessian-driven damping. The temporal discretization of these dynamics leads to a new class of first-order optimization algorithms with favorable properties. The Tikhonov regularization parameter is assumed to tend to zero as time tends to infinity, which preserves equilibria. The presence of the Tikhonov regularization term induces a strong property of convexity which vanishes asymptotically. To take advantage of the fast convergence rates attached to the heavy ball method in the strongly convex case, we consider inertial dynamics where the viscous damping coefficient is proportional to the square root of the Tikhonov regularization parameter, and hence converges to zero. The geometric damping, controlled by the Hessian of the function to be minimized, induces attenuation of the oscillations. Under an appropriate setting of the parameters, based on Lyapunov's analysis, we show that the trajectories provide at the same time several remarkable properties: fast convergence of values, fast convergence of gradients towards zero, and strong convergence to the minimum norm minimizer. We show that the corresponding proximal algorithms share the same properties as continuous dynamics. The numerical illustrations confirm the results obtained. This study extends a previous paper by the authors regarding similar problems without the presence of Hessian driven damping. [ABSTRACT FROM AUTHOR]

We analyze the convergence properties when the time t tends to infinity of the trajectories generated by damped inertial dynamics which are driven by the sum of potential and nonpotential operators. Precisely, we seek to reach asymptotically the zeros of a maximally monotone operator which is the sum of a potential operator (the gradient of a continuously differentiable convex function) and of a monotone and cocoercive nonpotential operator. As an original feature, in addition to the viscous friction, the dynamic involves implicit Newton-type damping. This contrasts with the authors' previous study where explicit Newton-type damping was considered, which, for the potential term corresponds to Hessian-driven damping. We show the weak convergence, as time tends to infinity, of the generated trajectories toward the zeros of the sum of the potential and nonpotential operators. Our results are based on Lyapunov analysis and appropriate setting of the damping parameters. The introduction of geometric dampings allows to control and attenuate the oscillations known for the viscous damping of inertial methods. Rewriting the second-order evolution equation as a system involving only first-order derivative in time and space allows us to extend the convergence analysis to nonsmooth convex potentials. The main part of our study concerns the autonomous case with positive fixed parameters. We complete it with some first results concerning the nonautonomous case, and which are based on a recent acceleration method using time scaling and averaging. These results open the door to the design of new first-order accelerated algorithms in optimization taking into account the specific properties of potential and nonpotential terms. The proofs and techniques are original due to the presence of the nonpotential term. [ABSTRACT FROM AUTHOR]

In this paper, we propose new numerical algorithms in the setting of unconstrained optimization problems and we prove the discrete rate of convergence of order O 1 / n 2 in the iterates of the convex objective function. Our optimization algorithms are obtained via discretizations from dynamical systems with Hessian-driven damping. Finally, some numerical experiments are presented in order to validate the theoretical results. [ABSTRACT FROM AUTHOR]

In a Hilbert setting, we study the convergence properties of the second order in time dynamical system combining viscous and Hessian-driven damping with time scaling in relation to the minimization of a nonsmooth and convex function. The system is formulated in terms of the gradient of the Moreau envelope of the objective function with a time-dependent parameter. We show fast convergence rates for the Moreau envelope, its gradient along the trajectory, and also for the system velocity. From here, we derive fast convergence rates for the objective function along a path which is the image of the trajectory of the system through the proximal operator of the first. Moreover, we prove the weak convergence of the trajectory of the system to a global minimizer of the objective function. Finally, we provide multiple numerical examples illustrating the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of second-order ordinary differential equations with Hessian-driven damping and Tikhonov regularization, which arises from the minimization of a smooth convex function in Hilbert spaces. Inspired by Attouch et al. (J Differ Equ 261:5734–5783, 2016), we establish that the function value along the solution trajectory converges to the optimal value, and prove that the convergence rate can be as fast as o(1/t2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$o(1/t^2)$$\end{document}. By constructing proper energy function, we prove that the trajectory strongly converges to a minimizer of the objective function of minimum norm. Moreover, we propose a gradient-based optimization algorithm based on numerical discretization, and demonstrate its effectiveness in numerical experiments. [ABSTRACT FROM AUTHOR]

The ordinary differential equation is a powerful tool for analyzing optimization algorithm. Motivated by the fact, this paper revisits Halpern fixed-point algorithm from an ordinary differential equation. More specifically, we establish a second-order ordinary differential equation with Hessian-driven damping, which is the limit of Halpern fixed-point algorithm. The Hessian-driven damping makes it possible to significantly attenuate the oscillations. [ABSTRACT FROM AUTHOR]

In a real Hilbert space setting, we investigate the asymptotic properties of the solutions of a second-order differential system in view of linearly constrained convex minimization. The inertial dynamics are governed by a Hessian-driven damping term associated with the convex function to be minimized and potential effects induced by the linear constraints. We provide conditions on both the damping and the potential for which the solutions converge towards some feasible point of the convex minimization problem; this convergence is towards some minimizer provided that the solutions' initial data is specifically preselected. In addition, we present asymptotic estimates on the convergence rate of the solutions depending on the interaction between damping and potential effects. Our analysis is mainly based on energy-like arguments that capture the dissipative nature of the inertial dynamics by means of a Bregman distance. We complement our study with the fact that the second-order dynamics admit a first-order representation in terms of the Arrow--Hurwicz differential system. Numerical experiments further illustrate our theoretical findings. [ABSTRACT FROM AUTHOR]

We investigate the asymptotic properties of the trajectories generated by a second-order dynamical system with Hessian driven damping and a Tikhonov regularization term in connection with the minimization of a smooth convex function in Hilbert spaces. We obtain fast convergence results for the function values along the trajectories. The Tikhonov regularization term enables the derivation of strong convergence results of the trajectory to the minimizer of the objective function of minimum norm. [ABSTRACT FROM AUTHOR]

In a Hilbert space H, we introduce a new class of proximal-gradient algorithms with finite convergence properties. These algorithms naturally occur as discrete temporal versions of an inertial differential inclusion which is stabilized under the joint action of three dampings: dry friction, viscous friction, and a geometric damping driven by the Hessian. The function f : H → R to be minimized is supposed to be differentiable (not necessarily convex) and enters the algorithm via its gradient. The dry friction damping function ø: H → R+ is convex with a sharp minimum at the origin (typically ø(x) = r||x|| with r > 0). It enters the algorithm via its proximal mapping, which acts as a soft threshold operator on the velocities. It is the source of stabilization in a finite number of steps. The geometric damping driven by the Hessian intervenes in the dynamics in the form ▽²f(x(t))x(t). By treating this term as the time derivative of ▽f(x(t)), this gives, in discretized form, first-order algorithms. The Hessian-driven damping allows one to control and to attenuate the oscillations. The convergence results tolerate the presence of errors, under the sole assumption of their asymptotic convergence to zero. Replacing the potential function f by its Moreau envelope, we extend the results to the case of a nonsmooth convex function f. In this case, the algorithm involves the proximal operators of f and ø separately. Several variants of this algorithm are considered, including the case of the Nesterov accelerated gradient method. We then consider the extension to the case of additive composite optimization, thus leading to splitting methods. Numerical experiments are given for lasso-type problems. The performance profiles, as a comparison tool, highlight the effectiveness of a variant of the Nesterov accelerated method with dry friction and Hessian-driven damping. [ABSTRACT FROM AUTHOR]

We first study the fast minimization properties of the trajectories of the second-order evolution equation x ¨ ( t ) + α t x ˙ ( t ) + β ∇ 2 Φ ( x ( t ) ) x ˙ ( t ) + ∇ Φ ( x ( t ) ) = 0 , where Φ : H → R is a smooth convex function acting on a real Hilbert space H , and α , β are positive parameters. This inertial system combines an isotropic viscous damping which vanishes asymptotically, and a geometrical Hessian driven damping, which makes it naturally related to Newton's and Levenberg–Marquardt methods. For α ≥ 3 , and β > 0 , along any trajectory, fast convergence of the values Φ ( x ( t ) ) − min H ⁡ Φ = O ( t − 2 ) is obtained, together with rapid convergence of the gradients ∇ Φ ( x ( t ) ) to zero. For α > 3 , just assuming that argmin Φ ≠ ∅ , we show that any trajectory converges weakly to a minimizer of Φ, and that Φ ( x ( t ) ) − min H ⁡ Φ = o ( t − 2 ) . Strong convergence is established in various practical situations. In particular, for the strongly convex case, we obtain an even faster speed of convergence which can be arbitrarily fast depending on the choice of α . More precisely, we have Φ ( x ( t ) ) − min H ⁡ Φ = O ( t − 2 3 α ) . Then, we extend the results to the case of a general proper lower-semicontinuous convex function Φ : H → R ∪ { + ∞ } . This is based on the crucial property that the inertial dynamics with Hessian driven damping can be equivalently written as a first-order system in time and space, allowing to extend it by simply replacing the gradient with the subdifferential. By explicit–implicit time discretization, this opens a gate to new − possibly more rapid − inertial algorithms, expanding the field of FISTA methods for convex structured optimization problems. [ABSTRACT FROM AUTHOR]

In a Hilbert space setting, this paper is devoted to the study of a class of first-order algorithms which aim to solve structured monotone equations involving the sum of potential and nonpotential operators. Precisely, we are looking for the zeros of an operator A=∇f+B\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$A= \nabla f +B $$\end{document}, where ∇f\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\nabla f$$\end{document} is the gradient of a differentiable convex function f, and B is a nonpotential monotone and cocoercive operator. This study is based on the inertial autonomous dynamic previously studied by the authors, which involves dampings controlled respectively by the Hessian of f, and by a Newton-type correction term attached to B. These geometric dampings attenuate the oscillations which occur with the inertial methods with viscous damping. Temporal discretization of this dynamic provides fully splitted proximal-gradient algorithms. Their convergence properties are proven using Lyapunov analysis. These results open the door to the design of first-order accelerated algorithms in numerical optimization taking into account the specific properties of potential and nonpotential terms. [ABSTRACT FROM AUTHOR]