Anderson Acceleration

class pathsim.optim.anderson.Anderson(m=4, restart=False)[source]

Bases: object

Anderson acceleration for fixed-point iteration.

Solves nonlinear equations in fixed-point form \(x = g(x)\) by computing the next iterate as a linear combination of previous iterates whose coefficients minimise the least-squares residual.

\[x_{k+1} = \sum_{i=0}^{m_k} \alpha_i^{(k)}\, g(x_{k-m_k+i}) \quad\text{with}\quad \alpha^{(k)} = \arg\min \bigl\|\sum_i \alpha_i\, r_{k-m_k+i}\bigr\|\]

where \(r_k = g(x_k) - x_k\) and \(m_k \le m\) is the current buffer depth.

In PathSim this class is the inner fixed-point solver used by the simulation engine to resolve algebraic loops (cycles in the block diagram). Each loop-closing ConnectionBooster owns an Anderson instance that accelerates convergence of the fixed-point iteration over the loop. The buffer depth m controls how many previous iterates are retained; larger values improve convergence on difficult loops at the cost of a small least-squares solve per iteration.

Parameters:

  • m (int) – buffer depth (number of stored iterates)

  • restart (bool) – if True, clear the buffer once it reaches depth m

References

solve(func, x0, iterations_max=100, tolerance=1e-06)[source]

Solve the function ‘func’ with initial value ‘x0’ up to a certain tolerance.

Note

This method is for testing purposes only and not used in the simulation loop.

Parameters:

  • func (callable) – function to solve

  • x0 (numeric) – starting value for solution

  • iterations_max (int) – maximum number of solver iterations

  • tolerance (float) – convergence condition

Returns:

  • x (numeric) – solution

  • res (float) – residual

  • i (int) – iteration count

reset()[source]

reset the anderson accelerator

step(x, g)[source]

Perform one iteration on the fixed-point solution.

Parameters:

  • x (float, array) – current solution

  • g (float, array) – current evaluation of g(x)

Returns:

  • x (float, array) – new solution

  • res (float) – residual norm, fixed point error

class pathsim.optim.anderson.NewtonAnderson(m=4, restart=False)[source]

Bases: Anderson

Hybrid Newton–Anderson fixed-point solver.

Extends Anderson by prepending a Newton step when a Jacobian of \(g\) is available. The Newton step

\[\tilde{x} = x - (J_g - I)^{-1}\,(g(x) - x)\]

provides a quadratically convergent initial correction; the subsequent Anderson mixing step then stabilises the iteration and damps oscillations.

In PathSim this solver is used inside every implicit ODE integration engine (BDF, DIRK, ESDIRK). When a block provides a local Jacobian (e.g. ODE or LTI blocks), the Newton pre-step yields much faster convergence of the implicit update equation, reducing the number of fixed-point iterations per timestep. Without a Jacobian the solver falls back to pure Anderson acceleration.

References

reset()[source]

Reset the anderson accelerator and the cached Newton factorization

solve(func, x0, jac=None, iterations_max=100, tolerance=1e-06)[source]

Solve the function ‘func’ with initial value ‘x0’ up to a certain tolerance.

Parameters:

  • func (callable) – function to solve

  • x0 (numeric) – starting value for solution

  • jac (callable) – jacobian of ‘func’

  • iterations_max (int) – maximum number of solver iterations

  • tolerance (float) – convergence condition

Note

This method is for testing purposes only and not used in the simulation loop.

Returns:

  • x (numeric) – solution

  • res (float) – residual

  • i (int) – iteration count

step(x, g, jac=None)[source]

Perform one iteration on the fixed-point solution.

If the jacobian of g ‘jac’ is provided, a newton step is performed previous to anderson acceleration.

Parameters:

  • x (float, array) – current solution

  • g (float, array) – current evaluation of g(x)

  • jac (array) – evaluation of jacobian of ‘g’

Returns:

  • x (float, array) – new solution

  • res (float) – residual norm

pathsim.optim.anderson.solve_root(opt, residual, x0, jac=None, tolerance=1e-09, iterations_max=200, line_search_max=20)[source]

Solve the square nonlinear system \(F(x) = 0\) by Anderson accelerated damped Newton iteration.

Each iteration takes a Newton direction \(\Delta x = J^{-1} F\), damps it with a backtracking line search on the residual norm so the step stays in the basin of the current root, and then accelerates the resulting iterate with the Anderson optimizer

\[\tilde{x}_{k+1} = x_k - \alpha_k J^{-1} F(x_k), \qquad x_{k+1} = \mathrm{Anderson}(x_k, \tilde{x}_{k+1})\]

The Anderson step is applied to the (damped) Newton iterate rather than to the raw fixed-point map \(x + F(x)\), so the first iterate is already a proper Newton step and cold starts do not jump out of the root’s basin. The accelerated iterate is kept only if it does not increase the residual, otherwise the plain Newton iterate is used, which makes the acceleration safe. The optimizer instance is the same Newton-Anderson type the implicit engines use, so the algebraic solves stay consistent with the solver stack.

The optimizer is reset before the iteration; the initial value doubles as the warm-start.

Parameters:

  • opt (Anderson | NewtonAnderson) – Anderson optimizer instance used to accelerate the Newton iterates

  • residual (callable) – residual function ‘F(x)’ of the square system

  • x0 (float, array[float]) – initial value / warm-start for the solution

  • jac (callable, None) – optional analytical Jacobian of ‘residual’, central finite differences are used as a fallback if ‘None’

  • tolerance (float) – convergence tolerance on the residual norm

  • iterations_max (int) – maximum number of iterations

  • line_search_max (int) – maximum number of backtracking line search steps per iteration

Returns:

  • x (array[float]) – converged solution

  • res (float) – residual norm at the last iteration

  • iterations (int) – number of iterations used