Anderson Acceleration for Nonsmooth Fixed Point Problems

DOI10.1137/22M1475983MaRDI QIDQ5043623zbMATH OpenOpenAlexFDO

Authors Wei Bian, Xiaojun Chen

Publication date 6 October 2022

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.10336

zbMATH Keywords

complementarity problemsmoothing approximationAnderson accelerationminimax problemcomposite max function

Mathematics Subject Classification ID

Approximation algorithms (68W25) Numerical computation of solutions to systems of equations (65H10)

Abstract: We give new convergence results of Anderson acceleration for the composite $max$ fixed point problem. We prove that Anderson(1) and EDIIS(1) are q-linear convergent with a smaller q-factor than existing q-factors. Moreover, we propose a smoothing approximation of the composite max function in the contractive fixed point problem. We show that the smoothing approximation is a contraction mapping with the same fixed point as the composite $max$ fixed point problem. Our results rigorously confirm that the nonsmoothness does not affect the convergence rate of Anderson acceleration method when we use the proposed smoothing approximation for the composite $max$ fixed point problem. Numerical results for constrained minimax problems, complementarity problems and nonsmooth differential equations are presented to show the efficiency and good performance of the proposed Anderson acceleration method with smoothing approximation.

Recommendations

• Anderson acceleration for a class of nonsmooth fixed-point problems
• Anderson acceleration for fixed-point iterations
• Anderson acceleration of the extragradient method for the nonlinear complementarity problems
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• Anderson acceleration for degenerate and nondegenerate problems
• A characterization of the behavior of the Anderson acceleration on linear problems
• On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM
• On the asymptotic linear convergence speed of Anderson acceleration, Nesterov acceleration, and nonlinear GMRES
• Anderson acceleration for contractive and noncontractive operators
• Anderson acceleration based on the \(\mathcal{H}^{- s}\) Sobolev norm for contractive and noncontractive fixed-point operators

Cites work

• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• scientific article; zbMATH DE number 3381785 (Why is no real title available?)
• A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
• A comparative study on methods for convergence acceleration of iterative vector sequences
• Anderson acceleration and application to the three-temperature energy equations
• Anderson acceleration for a class of nonsmooth fixed-point problems
• Anderson acceleration for contractive and noncontractive operators
• Anderson acceleration for fixed-point iterations
• Anderson acceleration of the alternating projections method for computing the nearest correlation matrix
• Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations
• Convergence analysis for Anderson acceleration
• Convergence of the EDIIS algorithm for nonlinear equations
• Design and Application of a Gradient-Weighted Moving Finite Element Code II: in Two Dimensions
• Direct minimization for calculating invariant subspaces in density functional computations of the electronic structure
• Elliptic preconditioner for accelerating the self-consistent field iteration in Kohn-Sham density functional theory
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• Iterative Procedures for Nonlinear Integral Equations
• Krylov subspace acceleration for nonlinear multigrid schemes
• Nonlinear Krylov and moving nodes in the method of lines
• On the use of policy iteration as an easy way of pricing American options
• Smoothing Methods and Semismooth Methods for Nondifferentiable Operator Equations
• Smoothing methods for nonsmooth, nonconvex minimization
• The quasi-Newton least squares method: A new and fast secant method analyzed for linear systems
• Two classes of multisecant methods for nonlinear acceleration

Cited in

(13)

• Anderson acceleration based on the \(\mathcal{H}^{- s}\) Sobolev norm for contractive and noncontractive fixed-point operators
• One-step convergence of inexact Anderson acceleration for contractive and non-contractive mappings
• Benchmarking results for the Newton-Anderson method
• Anderson acceleration for a class of nonsmooth fixed-point problems
• Anderson Accelerated Douglas--Rachford Splitting
• Shanks and Anderson-type acceleration techniques for systems of nonlinear equations
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• Anderson acceleration for contractive and noncontractive operators
• A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
• The effect of Anderson acceleration on superlinear and sublinear convergence
• Fast Algorithms for Nonsmooth Compact Fixed-Point Problems
• Convergence analysis for Anderson acceleration
• Nonmonotone globalization for Anderson acceleration via adaptive regularization

Describes a project that uses

Uses Software

• Anderson
• NKA

This page was built for publication: Anderson Acceleration for Nonsmooth Fixed Point Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043623)