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

We propose a hybrid control algorithm that guarantees fast convergence and uniform global asymptotic stability of the unique minimizer of a smooth, convex objective function. The algorithm, developed using hybrid system tools, employs a uniting control strategy, in which Nesterov's accelerated...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-09
Main Authors: Hustig-Schultz, Dawn M, Sanfelice, Ricardo G
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic methods
Asymptotic properties
Control algorithms
Control stability
Control theory
Convergence
Feedback control
Hybrid control
Hybrid systems
Optimization
Robustness (mathematics)
Stability analysis
Switches
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a hybrid control algorithm that guarantees fast convergence and uniform global asymptotic stability of the unique minimizer of a smooth, 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.
ISSN:2331-8422