Nonlinear Solver Method Catalog

Nonlinear Solver Method Catalog

Comprehensive catalog of nonlinear solver methods with parameters and guidance.

Newton-Type Methods

Newton's Method (Full Newton)

Update formula:

x_{k+1} = x_k - J(x_k)^{-1} f(x_k)

Requirements:

• Jacobian J(x) = ∂f/∂x available
• J(x) nonsingular

Convergence:

• Quadratic near solution: ||e_{k+1}|| ≤ C ||e_k||²
• Requires good initial guess

Parameters:

When to use:

• Small to medium problems (n < 5000)
• Jacobian cheap to compute and factor
• Quadratic convergence needed

When to avoid:

• Large problems (use Newton-Krylov)
• Expensive Jacobian (use modified Newton)
• Far from solution (add globalization)

Modified Newton

Update formula:

x_{k+1} = x_k - J(x_0)^{-1} f(x_k)   (frozen Jacobian)
x_{k+1} = x_k - J(x_m)^{-1} f(x_k)   (recompute every m steps)

Convergence:

• Linear when Jacobian frozen
• Faster than Picard if Jacobian is good

Parameters:

When to use:

• Jacobian expensive to compute
• Jacobian changes slowly
• Initial iterations where exact Jacobian less critical

Inexact Newton

Idea: Solve J(x_k) δ = -f(x_k) approximately

Inner solve criterion:

||J(x_k) δ_k + f(x_k)|| ≤ η_k ||f(x_k)||

Forcing sequence η_k:

When to use:

• Large problems where exact solve too expensive
• Combined with Krylov inner solver (Newton-Krylov)

Newton-Krylov Methods

Idea: Use Krylov method (GMRES, BiCGSTAB) for inner linear solve

Key methods:

Parameters:

Jacobian-free variant:

J(x) v ≈ (f(x + εv) - f(x)) / ε

where ε ≈ √(machine_eps) × ||x|| / ||v||

When to use:

• Large-scale problems (n > 10000)
• Jacobian too expensive to form/store
• Sparse structure can be exploited

Quasi-Newton Methods

BFGS (Broyden-Fletcher-Goldfarb-Shanno)

Update formula (for B ≈ Hessian):

s_k = x_{k+1} - x_k
y_k = ∇F(x_{k+1}) - ∇F(x_k)
B_{k+1} = B_k - (B_k s_k)(B_k s_k)^T / (s_k^T B_k s_k) + y_k y_k^T / (y_k^T s_k)

Properties:

• Maintains positive definiteness if B_0 is PD and y_k^T s_k > 0
• Superlinear convergence on smooth convex problems
• Self-correcting

Parameters:

When to use:

• Optimization when Hessian unavailable
• Moderate problem size (n < 1000)
• Smooth, convex objectives

L-BFGS (Limited-memory BFGS)

Idea: Store only last m pairs (s_k, y_k), reconstruct H_k v implicitly

Two-loop recursion:

Algorithm for computing H_k ∇F(x_k):
1. q = ∇F
2. For i = k-1, ..., k-m: α_i = ρ_i s_i^T q; q = q - α_i y_i
3. r = H_0 q
4. For i = k-m, ..., k-1: β = ρ_i y_i^T r; r = r + (α_i - β) s_i
5. Return r

Parameters:

Memory: O(mn) vs O(n²) for full BFGS

When to use:

• Large-scale optimization (n > 1000)
• Memory constrained
• Smooth objectives

Broyden's Method (Good and Bad)

Broyden's "good" update (for J ≈ Jacobian):

J_{k+1} = J_k + (y_k - J_k s_k) s_k^T / (s_k^T s_k)

Broyden's "bad" update:

J_{k+1}^{-1} = J_k^{-1} + (s_k - J_k^{-1} y_k) y_k^T / (y_k^T y_k)

Properties:

• Superlinear convergence for root-finding
• Does not maintain symmetry or positive definiteness
• "Good" is better for most problems

When to use:

• Root-finding without exact Jacobian
• Moderate problem size
• Jacobian is nearly constant

SR1 (Symmetric Rank-1)

Update formula:

B_{k+1} = B_k + (y_k - B_k s_k)(y_k - B_k s_k)^T / ((y_k - B_k s_k)^T s_k)

Properties:

• Maintains symmetry
• Does NOT maintain positive definiteness
• Can capture indefinite Hessian

When to use:

• Saddle point problems
• When negative curvature information needed
• Often combined with trust region

Fixed-Point Methods

Picard Iteration (Fixed-Point)

Form: Rewrite f(x) = 0 as x = g(x)

Update:

x_{k+1} = g(x_k)

Convergence:

• Linear: ||e_{k+1}|| ≤ L ||e_k|| where L = ||g'(x*)||
• Converges if L < 1

When to use:

• Natural fixed-point form available
• Stability more important than speed
• Initial guess may be far from solution

Anderson Acceleration

Idea: Accelerate fixed-point iteration using history

Algorithm:

1. Compute g_k = g(x_k)
2. Define f_k = g_k - x_k (residual)
3. Minimize ||Σ α_i f_{k-i}||² subject to Σ α_i = 1
4. x_{k+1} = Σ α_i g_{k-i}

Parameters:

Properties:

• Transforms linear convergence to superlinear (often)
• Robust when simple acceleration fails
• Works well for multiphysics coupling

When to use:

• Accelerating Picard iteration
• Coupled multiphysics problems
• When Jacobian unavailable or ill-conditioned

Specialized Methods

Levenberg-Marquardt

For least-squares: min ||r(x)||²

Update: Solve

(J^T J + λ D^T D) δ = -J^T r

where D is scaling (often diagonal of J^T J or identity)

λ strategy:

Parameters:

When to use:

• Nonlinear least-squares problems
• Small to medium problems
• Data fitting, parameter estimation

Gauss-Newton

Same as Levenberg-Marquardt with λ = 0:

J^T J δ = -J^T r

Properties:

• Fast when residual is small at solution
• May fail when residual is large
• Requires J^T J invertible

When to use:

• Zero-residual or small-residual problems
• Well-conditioned J
• Combined with line search for robustness

Dogleg Method

For trust region: Combine Cauchy point and Newton step

1. Cauchy point: p_C = -α_C ∇F where α_C = ||∇F||² / (∇F^T B ∇F)
2. Newton step: p_N = -B^{-1} ∇F
3. Dogleg path: interpolate between origin, p_C, and p_N
4. Find intersection with trust region boundary

When to use:

• Trust region subproblem
• When exact subproblem solve too expensive
• Positive definite Hessian approximation

Steihaug-CG

For large trust region subproblem: Solve using CG

1. Start CG iteration for B p = -∇F
2. If direction of negative curvature, go to boundary
3. If CG step exits trust region, go to boundary
4. Otherwise, continue CG until convergence

When to use:

• Large-scale trust region
• Truncated Newton methods
• When B may be indefinite

Parameter Guidelines

Convergence Tolerances

Maximum Iterations

Line Search Parameters

Trust Region Parameters