关于Anderson混合的研究进展

包承龙; 韦福超

doi:10.13471/j.cnki.acta.snus.2023A035

您当前的位置：

首页 >

文章列表页 >

关于Anderson混合的研究进展

优化技术专栏 | 更新时间：2023-11-07

- 关于Anderson混合的研究进展
- Research advance on Anderson mixing
- 中山大学学报(自然科学版)(中英文) 2023年62卷第5期页码：59-66
- 作者机构：
  
  1.清华大学丘成桐数学科学中心，北京 100084
  2.清华大学计算机科学与技术系，北京 100084
- 作者简介：
  
  包承龙（1989 年生），男；研究方向：图像处理模型与优化算法；E-mail：clbao@mail.tsinghua.edu.cn
- 基金信息：
  
  国家重点研发计划(2021YFA1001300);国家自然科学基金(12271291)
- DOI：10.13471/j.cnki.acta.snus.2023A035
  中图分类号： O221.2
- 纸质出版日期：2023-09-25，
  
  网络出版日期：2023-08-30，
  
  收稿日期：2023-05-11，
  
  录用日期：2023-06-21
扫描看全文
包承龙,韦福超.关于Anderson混合的研究进展[J].中山大学学报(自然科学版),2023,62(05):59-66.

BAO Chenglong,WEI Fuchao.Research advance on Anderson mixing[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2023,62(05):59-66.
包承龙,韦福超.关于Anderson混合的研究进展[J].中山大学学报(自然科学版),2023,62(05):59-66. DOI： 10.13471/j.cnki.acta.snus.2023A035.

BAO Chenglong,WEI Fuchao.Research advance on Anderson mixing[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2023,62(05):59-66. DOI： 10.13471/j.cnki.acta.snus.2023A035.

摘要

Anderson混合是一种经典的外推方法，它能利用历史迭代信息加速定点迭代的收敛，在科学计算和机器学习中得到了成功的应用. 由于Anderson混合在实践中经常表现出优越的数值性能，在各类应用中围绕Anderson混合的算法设计和理论分析成为近几年的研究热点. 本文综述关于Anderson混合的研究进展，重点介绍基于Anderson混合的新算法.

Abstract

Anderson mixing is a classical extrapolation method. It can make use of the information in historical iterations to accelerate the convergence of fixed-point iterations， and has been successfully applied in scientific computing and machine learning. Since Anderson mixing often exhibits superior numerical performance in practice， the algorithm design and theoretical analysis around Anderson mixing in various applications have become hot topics in recent years. This article reviews the research advance on Anderson mixing， and highlights new algorithms based on Anderson mixing.

关键词

Anderson混合定点迭代Krylov子空间方法拟Newton法

Keywords

Anderson mixingfixed-point iterationKrylov subspace methodquasi-Newton method

references

ANDERSON D G， 1965. Iterative procedures for nonlinear integral equations［J］. J ACM， 12（4）： 547-560.

ANDERSON D G， 2019. Comments on "Anderson acceleration， mixing and extrapolation"［J］. Numer Algorithms， 80（1）： 135-234.

ARORA A， MORSE D C， BATES F S， et al， 2017. Accelerating self-consistent field theory of block polymers in a variable unit cell［J］. J Chem Phys， 146（24）： 244902.

BIAN W， CHEN X J， 2022. Anderson acceleration for nonsmooth fixed point problems［J］. SIAM J Numer Anal， 60（5）： 2565-2591.

BIAN W， CHEN X J， KELLEY C T， 2021. Anderson acceleration for a class of nonsmooth fixed-point problems［J］. SIAM J Sci Comput， 43（5）： S1-S20.

BREZINSKI C， REDIVO-ZAGLIA M， SAAD Y， 2018. Shanks sequence transformations and Anderson acceleration［J］. SIAM Rev， 60（3）： 646-669.

CALEF M T， FICHTL E D， WARSA J S， et al， 2013. Nonlinear Krylov acceleration applied to a discrete ordinates formulation of the k-eigenvalue problem［J］. J Comput Phys， 238： 188-209.

CHEN X J， KELLEY C T， 2019. Convergence of the EDIIS algorithm for nonlinear equations［J］. SIAM J Sci Comput， 41（1）： A365-A379.

EVANS C， POLLOCK S， REBHOLZ L G， et al， 2020. A proof that Anderson acceleration improves the convergence rate in linearly converging fixed-point methods（but not in those converging quadratically）［J］. SIAM J Numer Anal， 58（1）： 788-810.

FANG H R， SAAD Y， 2009. Two classes of multisecant methods for nonlinear acceleration［J］. Numer Linear Algebra Appl， 16（3）： 197-221.

FU A Q， ZHANG J Z， BOYD S， 2020. Anderson accelerated Douglas-Rachford splitting［J］. SIAM J Sci Comput， 42（6）： A3560-A3583.

HENDERSON N C， VARADHAN R， 2019. Damped Anderson acceleration with restarts and monotonicity control for accelerating EM and EM-like algorithms［J］. J Comput Graph Stat， 28（4）： 834-846.

JOHNSON R， ZHANG T， 2013. Accelerating stochastic gradient descent using predictive variance reduction［C］//Proceedings of the 27th International Conference on Neural Information Processing Systems： 315-323.

KUDIN K N， SCUSERIA G E， CANCÈS E， 2002. A black-box self-consistent field convergence algorithm： One step closer［J］. J Chem Phys， 116（19）： 8255-8261.

LUPO PASINI M， 2019. Convergence analysis of Anderson-type acceleration of Richardson's iteration［J］. Numer Linear Algebra Appl， 26（4）： e2241.

MAI V V， JOHANSSON M， 2020. Anderson acceleration of proximal gradient methods［C］//Proceedings of the 37th International Conference on Machine Learning： 6620-6629.

NOCEDAL J， WRIGHT S J， 2006. Numerical optimization［M］. 2nd ed. New York： Springer.

POLLOCK S， REBHOLZ L G， 2021. Anderson acceleration for contractive and noncontractive operators［J］. IMA J Numer Anal， 41（4）： 2841-2872.

POLLOCK S， REBHOLZ L G， XIAO M Y， 2019. Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations［J］. SIAM J Numer Anal， 57（2）： 615-637.

PRATAPA P P， SURYANARAYANA P， PASK J E， 2016. Anderson acceleration of the Jacobi iterative method： An efficient alternative to Krylov methods for large， sparse linear systems［J］. J Comput Phys， 306： 43-54.

PULAY P， 1980. Convergence acceleration of iterative sequences. the case of SCF iteration［J］. Chem Phys Lett， 73（2）： 393-398.

ROHWEDDER T， SCHNEIDER R， 2011. An analysis for the DIIS acceleration method used in quantum chemistry calculations［J］. J Math Chem， 49（9）： 1889-1914.

SAAD Y， 1981. Krylov subspace methods for solving large unsymmetric linear systems［J］. Math Comp， 37（155）： 105-126.

SAAD Y， 2003. Iterative methods for sparse linear systems［M］. 2nd ed. Philadelphia： SIAM.

SAAD Y， SCHULTZ M H， 1986. GMRES： A generalized minimal residual algorithm for solving nonsymmetric linear systems［J］. SIAM J Sci Stat Comput， 7（3）： 856-869.

SCIEUR D， D'ASPREMONT A， BACH F， 2020. Regularized nonlinear acceleration［J］. Math Program， 179（1/2）： 47-83.

SUN K， WANG Y F， LIU Y， et al， 2021. Damped Anderson mixing for deep reinforcement learning： Acceleration， convergence， and stabilization［C］//Proceedings of the 35th Conference on Neural Information Processing Systems： 3732-3743.

SURYANARAYANA P， PRATAPA P P， PASK J E， 2019. Alternating Anderson-Richardson method： An efficient alternative to preconditioned Krylov methods for large， sparse linear systems［J］. Comput Phys Commun， 234： 278-285.

TOTH A， KELLEY C T， 2015. Convergence analysis for Anderson acceleration［J］. SIAM J Numer Anal， 53（2）： 805-819.

WALKER H F， NI P， 2011. Anderson acceleration for fixed-point iterations［J］. SIAM J Numer Anal， 49（4）： 1715-1735.

WEI F C， BAO C L， LIU Y， 2021. Stochastic Anderson mixing for nonconvex stochastic optimization［C］//Proceedings of the 35th Conference on Neural Information Processing Systems： 22995-23008.

WEI F C， BAO C L， LIU Y， 2022a. A class of short-term recurrence Anderson mixing methods and their applications［C］//The Tenth International Conference on Learning Representations： 1565.

WEI F C， BAO C L， LIU Y， et al， 2022b. A variant of Anderson mixing with minimal memory size［C］//Proceedings of the 36th Conference on Neural Information Processing Systems： 16650-16663.

YANG Y N， 2021. Anderson acceleration for seismic inversion［J］. Geophysics， 86（1）： R99-R108.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据