Anderson Acceleration for Nonsmooth Fixed Point Problems

DOI10.1137/22M1475983zbMATH Open1503.65102arXiv2209.10336OpenAlexW4296679606MaRDI QIDQ5043623FDOQ5043623

Xiaojun Chen, Wei Bian

Publication date: 6 October 2022

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

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.

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)

Cites Work

• 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
• A comparative study on methods for convergence acceleration of iterative vector sequences
• Two classes of multisecant methods for nonlinear acceleration
• Anderson acceleration of the alternating projections method for computing the nearest correlation matrix
• Anderson Acceleration for Fixed-Point Iterations
• Title not available (Why is that?)
• Iterative Procedures for Nonlinear Integral Equations
• Title not available (Why is that?)
• Smoothing methods for nonsmooth, nonconvex minimization
• Smoothing Methods and Semismooth Methods for Nondifferentiable Operator Equations
• Convergence Analysis for Anderson Acceleration
• Krylov subspace acceleration for nonlinear multigrid schemes
• On the Use of Policy Iteration as an Easy Way of Pricing American Options
• The Quasi-Newton Least Squares Method: A New and Fast Secant Method Analyzed for Linear Systems
• Nonlinear Krylov and moving nodes in the method of lines
• Anderson acceleration and application to the three-temperature energy equations
• Elliptic preconditioner for accelerating the self-consistent field iteration in Kohn-Sham density functional theory
• Anderson-Accelerated Convergence of Picard Iterations for Incompressible Navier--Stokes Equations
• A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
• Anderson acceleration for contractive and noncontractive operators
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• Anderson Acceleration for a Class of Nonsmooth Fixed-Point Problems
• Convergence of the EDIIS Algorithm for Nonlinear Equations

Cited In (9)

• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• Anderson Accelerated Douglas--Rachford Splitting
• The effect of Anderson acceleration on superlinear and sublinear convergence
• 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)
• Nonmonotone globalization for Anderson acceleration via adaptive regularization
• Anderson acceleration based on the \(\mathcal{H}^{- s}\) Sobolev norm for contractive and noncontractive fixed-point operators
• Shanks and Anderson-type acceleration techniques for systems of nonlinear equations
• Fast Algorithms for Nonsmooth Compact Fixed-Point Problems

Uses Software

• Anderson
• NKA

   Recommendations

• Anderson Acceleration for a Class of Nonsmooth Fixed-Point Problems 👍 👎
• Anderson acceleration for fixed-point iterations 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)