Uniting Nesterov and Heavy Ball Methods for Uniform Global Asymptotic Stability of the Set of Minimizers

Abstract

We propose a hybrid control algorithm that guarantees fast convergence and uniform global asymptotic stability of the unique minimizer of a continuously differentiable, convex objective function. The algorithm, developed using hybrid system tools, employs a uniting control strategy, in which Nesterov's accelerated gradient descent is used "globally" and the heavy ball method is used "locally," relative to the minimizer. Without knowledge of its location, the proposed hybrid control strategy switches between these accelerated methods to ensure convergence to the minimizer without oscillations, with a (hybrid) convergence rate that preserves the convergence rates of the individual optimization algorithms. We analyze key properties of the resulting closed-loop system including existence of solutions, uniform global asymptotic stability, and convergence rate. Additionally, stability properties of Nesterov's method are analyzed, and extensions on convergence rate results in the existing literature are presented. Numerical results validate the findings and demonstrate the robustness of the uniting algorithm.

arXiv commentThe technical report accompanying "Uniting Nesterov and Heavy Ball Methods for Uniform Global Asymptotic Stability of the Set of Minimizers", accepted to Automatica, 2023. Minor revisions to have been made to make this version consistent with the final journal version