A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems

1 Introduction

• Basic fixed-point iterations can converge prohibitively slowly, while AA accelerates them by choosing affine combinations of recent iterates to minimize the corresponding residual combination.Fixed-point formulations arise in nonlinear equations, optimization, variational inequalities, and nonlinear PDE solvers.Source: §1 · pp. 1–2
• AA’s convergence theory is less developed than that of the underlying fixed-point iteration, with cited analyses establishing mainly local linear convergence under specific mapping assumptions.Toth and Kelley proved local r-linear convergence for continuously differentiable contractions under bounded coefficients; Chen and Kelley relaxed the differentiability condition.Source: §1 · p. 2
• AA can become unstable or stagnate, prompting safeguards that fall back to a base iteration or methods that regularize, constrain, or filter its least-squares subproblem.The cited safeguarded schemes for nonexpansive mappings provide global guarantees, but their analyses yield no explicit convergence factors.Source: §1 · p. 2
• Some existing globalization approaches rely on objective-function descent, while the nonmonotone framework of Ouyang et al. requires prior knowledge of the contraction factor for its contractive guarantees.Objective-based strategies are not directly applicable to general fixed-point problems without an available objective and descent properties.Source: §1 · p. 3
• The proposed framework combines global convergence guarantees with local acceleration, without requiring prior knowledge of the contraction factor.For contractive mappings, it eventually reduces exactly to pure AA; for nonexpansive mappings, residuals converge globally to zero.Source: §1 · p. 3

2 Global Anderson Acceleration Algorithm

• GlobAA(m) executes exactly one of processes (A) and (K) at each iteration, resets memory parameter m_k after each Krasnosel’skiĭ–Mann step, and allows λ ∈ (0, 1] for contractive mappings versus λ ∈ (0, 1) for nonexpansive mappings.Source: §2 · p. 5

2.1.1 Global r-linear convergence for m ≥1

• For contractive G, GlobAA(m) converges globally with r-linear rate c and, after finitely many iterations, coincides exactly with pure AA.The result assumes G is a contraction, differentiable at its fixed point, and the update parameters satisfy the stated conditions.Source: §2.1.1 · pp. 6, 8, 9

2.1.2 Global residual q-linear convergence for m = 1

• For m = 1, GlobAA(1) has global residual q-linear convergence under the contractive-case assumptions.Theorem 2.11 addresses residual convergence for the one-memory algorithm.Source: §2.1.2 · pp. 9–10

2.2 Global residual convergence for nonexpansive mappings

• For nonexpansive G with a fixed point, the update strategy requires 0 < γk < 1 and bounds γk by 1 − Θ(Wk/W0), with Θ nondecreasing, Θ(0) = 0, and Θ(t) > 0 for t > 0.Here Wk is the maximum residual norm over the current memory window.Source: §2.2 · p. 11
• Under Assumptions 2.12–2.13 and λ ∈ (0, 1), the sequence {uk} generated by GlobAA(m) satisfies ∥F(uk)∥ → 0 as k → ∞.The cited conclusion also states Wk → 0 as k → ∞.Source: §2.2 · pp. 11–12

2.3 A class-agnostic strategy for contractive and nonexpansive mappings

• Strategy S requires no prior knowledge of the mapping class and yields global r-linear convergence for contractive mappings and global residual convergence for nonexpansive mappings.Theorem 2.17 applies the strategy’s update rule to GlobAA(m).Source: §2.3 · p. 13
• For a locally contractive G, the strategy’s residual convergence implies uk → u*, and the associated Anderson points also converge to u*.The theorem states that its conclusions for contractive mappings remain valid under the class-agnostic strategy.Source: §2.3 · p. 13
• The assumptions on γk serve different roles: contractive mappings allow γk to approach one and enable eventual pure AA, while nonexpansive mappings require sufficient reduction from accepted Anderson steps.For nonexpansive mappings, the reduction is needed when Wk stays away from zero; the two assumptions are generally not interchangeable.Source: §2.3 · p. 14
• The strategy accommodates a mapping that is globally nonexpansive but locally contractive near its unique fixed point, without changing its parameter rule.The example has ∥G′(u)∥ ≤ 1 globally and ∥G′(u*)∥ = a < 1 locally.Source: §2.3 · p. 14

3.1 A non-convergence example of pure Anderson acceleration

• On the constructed example, pureAA(1) approaches a period-four orbit for specified initializations, while GlobAA converges across tested initializations, memory sizes, and γ choices.With m = 3, pureAA(m) and resAA(m) remain non-convergent over the tested iterations, whereas both converge for m = 5; GlobAA converges rapidly for both memory sizes. For random initial vectors, all methods meet tolerance, but Anderson-based methods generally require fewer iterations than Picard.Source: §3.1 · pp. 16–17

3.2 Elastic net regression

• In both contractive and nonexpansive elastic-net experiments, regularized GlobAA reaches tolerance and generally uses less CPU time; its advantage grows with m, while competitors may fail for large m.In the nonexpansive case, Picard fails for every tested m and pureAA(m) fails for most tested values.Source: §3.2 · p. 20, Table 2 · p. 21, Figure 4 · p. 21

3.3 Nonlinear Helmholtz equation

• For nonlinear Helmholtz, GlobAA generally needs fewer iterations and remains robust as m increases; Picard stagnates and pureAA is sensitive to m.Regularized GlobAA has almost the same convergence behavior as the unregularized version while significantly reducing CPU time.Source: Table 3 · p. 22, §3.3 · p. 22, Figure 6 · p. 23

3.4 2D Navier-Stokes equations

• For the tested Navier–Stokes cases, Picard stagnates, while AA-based methods reach tolerance and GlobAA uses the fewest or nearly the fewest iterations across memory sizes, Reynolds numbers, and problem sizes.Regularized GlobAA has almost identical convergence behavior while generally reducing computational time; the reported solution plots show the dominant cavity vortex and corner recirculation structures.Source: Figure 7 · p. 24, §3.4 · p. 24, Figure 8 · p. 24

• GlobAA(m) is a nonmonotone globalized Anderson acceleration framework that combines global convergence guarantees with local acceleration.Source: §4 · p. 24
• For contractive mappings, residual and iterate sequences converge globally r-linearly for m ≥1, while residuals converge q-linearly for m = 1, with factors no greater than the contraction factor.The method reduces exactly to pure Anderson acceleration after finitely many iterations.Source: §4 · pp. 24–25
• For nonexpansive mappings, fixed point residuals converge globally to zero, and a class-agnostic parameter rule ensures residual convergence in this setting while preserving linear convergence for contractive mappings.Source: §4 · p. 25
• Numerical experiments demonstrate the framework's effectiveness and robustness, particularly where pure Anderson acceleration may fail to converge or stagnate.Source: §4 · p. 25