An extension of the second order dynamical system that models Nesterov’s convex gradient method

Abstract

In this paper we deal with a general second order continuous dynamical system associated to a convex minimization problem with a Frechet differentiable objective function.

We show that inertial algorithms, such as Nesterov’s algorithm, can be obtained via the natural explicit discretization from our dynamical system.

Our dynamical system can be viewed as a perturbed version of the heavy ball method with vanishing damping, however the perturbation is made in the argument of the gradient of the objective function.

This perturbation seems to have a smoothing effect for the energy error and eliminates the oscillations obtained for this error in the case of the heavy ball method with vanishing damping, as some numerical experiments show.

We prove that the value of the objective function in a generated trajectory converges in order $$\mathcal{O}(1/t^2)$$ to the global minimum of the objective function.

Moreover, we obtain that a trajectory generated by the dynamical system converges to a minimum point of the objective function.

Authors

Cristian Daniel Alecsa
Department of Mathematics Babes-Bolyai University, Cluj-Napoca, Romania
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy, Cluj-Napoca, Romania

Szilard Csaba Laszlo
Technical University of Cluj-Napoca, Department of Mathematics, Cluj-Napoca, Romania

Titus Pinta
Mathematical Institute University of Oxford, Oxford, England

Keywords

Unconstrained optimization problems; convex optimization; heavy ball method; continuous second order dynamical system; convergence rate; inertial algorithm; Lyapunov energy functions.

Paper coordinates

C.-D. Alecsa, S.C. Laszlo, T. Pinta, An extension of the second order dynamical system that models Nesterov’s convex gradient method, Appl. Math. Optim., 84 (2021), pp. 1687–1716. doi: 10.1007/s00245-020-09692-1

Springer

0095-4616

1432-0606