浏览全部资源
扫码关注微信
Research advance on Anderson mixing
- Acta Scientiarum Naturalium Universitatis Sunyatseni Vol. 62, Issue 5, Pages: 59-66(2023)
- 作者机构：
1.清华大学丘成桐数学科学中心，北京 100084
2.清华大学计算机科学与技术系，北京 100084
- 作者简介：
- 基金信息：
DOI：10.13471/j.cnki.acta.snus.2023A035
CLC： O221.2Published：25 September 2023，
Published Online：30 August 2023，
Received：11 May 2023，
Accepted：21 June 2023
扫 描 看 全 文
包承龙,韦福超.关于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.
0
Views
2
下载量
0
CSCD
- L-PDFDownload
- Meta-XMLDownload
- BibTeXDownload
- EndnoteDownload
- RefMan Download
- NoteExpressDownload
- NoteFirstDownload
Publicity Resources
Related Articles
Related Author
Related Institution
- Postal code：510275
- Tel：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
- Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19
京公网安备11010802024621 - It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
- Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
