First-Order Optimization Algorithms with Resets and Hamiltonian flows
Andrew R. Teel, Jorge I. Poveda, Justin H. Le · 2019
This paper presents a novel class of algorithms with momentum for the solution of convex optimization problems. The novelty of the approach lies in combining Hamiltonian flows, induced by a Hamiltonian field, with an appropriate flow set that forces the flows to decrease the cost, and a class of resetting mechanisms that reset the momentum to zero whenever it generates solutions that do not decrease the cost function. For radially unbounded, invex functions with Lipschitz gradients we show uniform global asymptotic stability, and for functions that additionally satisfy the Polyak-Lojasiewicz inequality we establish exponential convergence. Since the flow dynamics are given by Hamiltonian systems, which preserve energy, symplectic integrators with stable behavior under not necessarily small step sizes can be implemented. These leads to a class of discretized algorithms with performance comparable to existing algorithms that are optimal in the sense of generating the fastest possible rates of convergence.