Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions

For many problems, some of which are reviewed in the paper, popular algorithms like Douglas–Rachford (DR), ADMM, and FISTA produce approximating sequences that show signs of spiraling toward the solution. We present a meta-algorithm that exploits such dynamics to potentially enhance performance. The...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2022-12, Vol.83 (3), p.999-1026
Main Author: Lindstrom, Scott B.
Format: Article
Language:English
Subjects:
Algorithms
Convex and Discrete Geometry
Liapunov functions
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Operators (mathematics)
Optimization
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For many problems, some of which are reviewed in the paper, popular algorithms like Douglas–Rachford (DR), ADMM, and FISTA produce approximating sequences that show signs of spiraling toward the solution. We present a meta-algorithm that exploits such dynamics to potentially enhance performance. The strategy of this meta-algorithm is to iteratively build and minimize surrogates for the Lyapunov function that captures those dynamics. As a first motivating application, we show that for prototypical feasibility problems the circumcentered-reflection method, subgradient projections, and Newton–Raphson are all describable as gradient-based methods for minimizing Lyapunov functions constructed for DR operators, with the former returning the minimizers of spherical surrogates for the Lyapunov function. As a second motivating application, we introduce a new method that shares these properties but with the added advantages that it: (1) does not rely on subproblems (e.g. reflections) and so may be applied for any operator whose iterates have the spiraling property; (2) provably has the aforementioned Lyapunov properties with few structural assumptions and so is generically suitable for primal/dual implementation; and (3) maps spaces of reduced dimension into themselves whenever the original operator does. This makes possible the first primal/dual implementation of a method that seeks the center of spiraling iterates. We describe this method, and provide a computed example (basis pursuit).
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-022-00413-8