Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization

Wenqing Ouyang; Jiong Tao; Andre Milzarek; Bailin Deng

doi:10.1007/s10915-023-02231-4

Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization

Wenqing Ouyang
, Jiong Tao
, Andre Milzarek
, Bailin Deng

Department of Computer Science

Chinese University of Hong Kong (Shenzhen)
Shenzhen Institute of Artificial Intelligence and Robotics for Society
Cardiff University

Research output: Contribution to journal › Article › peer-review

5 Citations (SciVal)

Abstract

Anderson acceleration (AA) is a popular method for accelerating fixed-point iterations, but may suffer from instability and stagnation. We propose a globalization method for AA to improve stability and achieve unified global and local convergence. Unlike existing AA globalization approaches that rely on safeguarding operations and might hinder fast local convergence, we adopt a nonmonotone trust-region framework and introduce an adaptive quadratic regularization together with a tailored acceptance mechanism. We prove global convergence and show that our algorithm attains the same local convergence as AA under appropriate assumptions. The effectiveness of our method is demonstrated in several numerical experiments.

Original language	English
Article number	5
Journal	Journal of Scientific Computing
Volume	96
Issue number	1
DOIs	https://doi.org/10.1007/s10915-023-02231-4
Publication status	Published - 18 May 2023

Bibliographical note

Funding Information:
A. Milzarek was partly supported by the Fundamental Research Fund - Shenzhen Research Institute for Big Data (SRIBD) Startup Fund JCYJ-AM20190601. B. Deng was partly supported by the Guangdong International Science and Technology Cooperation Project (No. 2021A0505030009).

Data Availability:
The datasets generated during and/or analysed during the current study are available in the GitHub repository https://github.com/bldeng/Nonmonotone-AA.

Funding

A. Milzarek was partly supported by the Fundamental Research Fund - Shenzhen Research Institute for Big Data (SRIBD) Startup Fund JCYJ-AM20190601. B. Deng was partly supported by the Guangdong International Science and Technology Cooperation Project (No. 2021A0505030009).

Keywords

Adaptive regularization
Anderson acceleration
Global convergence
Nonmonotone trust region

ASJC Scopus subject areas

Software
Theoretical Computer Science
Numerical Analysis
General Engineering
Computational Mathematics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10915-023-02231-4

Cite this

@article{59c008616170472c8df40c614629c7ce,

title = "Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization",

abstract = "Anderson acceleration (AA) is a popular method for accelerating fixed-point iterations, but may suffer from instability and stagnation. We propose a globalization method for AA to improve stability and achieve unified global and local convergence. Unlike existing AA globalization approaches that rely on safeguarding operations and might hinder fast local convergence, we adopt a nonmonotone trust-region framework and introduce an adaptive quadratic regularization together with a tailored acceptance mechanism. We prove global convergence and show that our algorithm attains the same local convergence as AA under appropriate assumptions. The effectiveness of our method is demonstrated in several numerical experiments.",

keywords = "Adaptive regularization, Anderson acceleration, Global convergence, Nonmonotone trust region",

author = "Wenqing Ouyang and Jiong Tao and Andre Milzarek and Bailin Deng",

note = "Funding Information: A. Milzarek was partly supported by the Fundamental Research Fund - Shenzhen Research Institute for Big Data (SRIBD) Startup Fund JCYJ-AM20190601. B. Deng was partly supported by the Guangdong International Science and Technology Cooperation Project (No. 2021A0505030009). Data Availability: The datasets generated during and/or analysed during the current study are available in the GitHub repository https://github.com/bldeng/Nonmonotone-AA.",

year = "2023",

month = may,

day = "18",

doi = "10.1007/s10915-023-02231-4",

language = "English",

volume = "96",

journal = "Journal of Scientific Computing",

issn = "0885-7474",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization

AU - Ouyang, Wenqing

AU - Tao, Jiong

AU - Milzarek, Andre

AU - Deng, Bailin

N1 - Funding Information: A. Milzarek was partly supported by the Fundamental Research Fund - Shenzhen Research Institute for Big Data (SRIBD) Startup Fund JCYJ-AM20190601. B. Deng was partly supported by the Guangdong International Science and Technology Cooperation Project (No. 2021A0505030009). Data Availability: The datasets generated during and/or analysed during the current study are available in the GitHub repository https://github.com/bldeng/Nonmonotone-AA.

PY - 2023/5/18

Y1 - 2023/5/18

N2 - Anderson acceleration (AA) is a popular method for accelerating fixed-point iterations, but may suffer from instability and stagnation. We propose a globalization method for AA to improve stability and achieve unified global and local convergence. Unlike existing AA globalization approaches that rely on safeguarding operations and might hinder fast local convergence, we adopt a nonmonotone trust-region framework and introduce an adaptive quadratic regularization together with a tailored acceptance mechanism. We prove global convergence and show that our algorithm attains the same local convergence as AA under appropriate assumptions. The effectiveness of our method is demonstrated in several numerical experiments.

AB - Anderson acceleration (AA) is a popular method for accelerating fixed-point iterations, but may suffer from instability and stagnation. We propose a globalization method for AA to improve stability and achieve unified global and local convergence. Unlike existing AA globalization approaches that rely on safeguarding operations and might hinder fast local convergence, we adopt a nonmonotone trust-region framework and introduce an adaptive quadratic regularization together with a tailored acceptance mechanism. We prove global convergence and show that our algorithm attains the same local convergence as AA under appropriate assumptions. The effectiveness of our method is demonstrated in several numerical experiments.

KW - Adaptive regularization

KW - Anderson acceleration

KW - Global convergence

KW - Nonmonotone trust region

UR - https://www.scopus.com/pages/publications/85160018419

U2 - 10.1007/s10915-023-02231-4

DO - 10.1007/s10915-023-02231-4

M3 - Article

AN - SCOPUS:85160018419

SN - 0885-7474

VL - 96

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

IS - 1

M1 - 5

ER -

Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this