Convergence of Constrained Anderson Acceleration

2020/10/29 by Mathieu Barré, Barré, Mathieu, Adrien Taylor +4
Computer Science · Engineering · Mathematics · #Advanced Numerical Methods in Computational Mathematics #FOS: Mathematics #Matrix Theory and Algorithms #Nuclear reactor physics and engineering #Numerical Analysis (math.NA) #Numerical methods for differential equations #Optimization and Control (math.OC) #cs.NA #math.NA #math.OC

paper · pdf · doi:10.48550/arxiv.2010.15482

arxiv created 2020/10/29 · openalex publication_date 2020/10/29 · arxiv updated 2020/10/30 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

We prove non asymptotic linear convergence rates for the constrained Anderson acceleration extrapolation scheme. These guarantees come from new upper bounds on the constrained Chebyshev problem, which consists in minimizing the maximum absolute value of a polynomial on a bounded real interval with l₁ constraints on its coefficients vector. Constrained Anderson Acceleration has a numerical cost comparable to that of the original scheme.

Citations

• Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
• Online Regularized Nonlinear Acceleration

Related

• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Anderson acceleration with adaptive relaxation for convergent fixed-point iterations
• Anderson acceleration with approximate calculations: applications to scientific computing
• Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis
• Anderson Acceleration for Fixed-Point Iterations