Nonlinear Solver Decision Tree
Comprehensive decision guide for selecting nonlinear solvers for f(x)=0 or min F(x).
Problem Classification
Key Properties to Determine
| Property |
How to Check |
Impact |
| Problem type |
Root-finding, optimization, least-squares |
Determines solver class |
| Jacobian availability |
Analytic vs finite-difference |
Newton vs quasi-Newton |
| Problem size |
Number of unknowns |
Memory and algorithm choice |
| Smoothness |
Continuous derivatives |
Enables fast convergence |
| Constraints |
Bounds, equalities, inequalities |
Specialized methods needed |
| Hessian SPD |
Optimization: F''(x) > 0 |
BFGS maintains this property |
Quick Classification
Problem type:
├── f(x) = 0 (root-finding/nonlinear equations)
├── min F(x) (unconstrained optimization)
├── min F(x) s.t. g(x) = 0 (equality constrained)
├── min F(x) s.t. l ≤ x ≤ u (bound constrained)
└── min ||r(x)||² (nonlinear least-squares)
Primary Decision Tree
START: Need to solve nonlinear problem
│
├─ What type of problem?
│ │
│ ├─ ROOT-FINDING (f(x) = 0)
│ │ │
│ │ ├─ Is analytic Jacobian available?
│ │ │ │
│ │ │ ├── YES, cheap to compute
│ │ │ │ ├── Small problem (n < 1000) → Newton (full)
│ │ │ │ ├── Large problem → Newton-Krylov (GMRES/BiCGSTAB)
│ │ │ │ └── Sparse Jacobian → Newton-Krylov with ILU
│ │ │ │
│ │ │ ├── YES, expensive to compute
│ │ │ │ ├── Modified Newton (reuse Jacobian)
│ │ │ │ └── Broyden update
│ │ │ │
│ │ │ └── NO (finite-diff or unavailable)
│ │ │ ├── Smooth problem → Broyden (good/bad)
│ │ │ ├── Fixed-point form → Anderson acceleration
│ │ │ └── Very large → Newton-Krylov (matrix-free)
│ │ │
│ │ └─ Convergence issues?
│ │ ├── Diverging → Add line search or trust region
│ │ ├── Stagnating → Better preconditioner
│ │ └── Oscillating → Reduce step, add damping
│ │
│ ├─ UNCONSTRAINED OPTIMIZATION (min F(x))
│ │ │
│ │ ├─ Is Hessian available?
│ │ │ │
│ │ │ ├── YES → Newton with trust region
│ │ │ │ └── Large problem → Truncated Newton (CG)
│ │ │ │
│ │ │ └── NO → Use quasi-Newton
│ │ │ ├── Moderate size → BFGS
│ │ │ └── Large problem → L-BFGS
│ │ │
│ │ └─ Is objective smooth?
│ │ ├── YES → Standard quasi-Newton
│ │ └── NO → Subgradient methods, bundle methods
│ │
│ ├─ CONSTRAINED OPTIMIZATION
│ │ │
│ │ ├─ Bound constraints only
│ │ │ ├── Smooth → L-BFGS-B
│ │ │ └── General → Trust-region reflective
│ │ │
│ │ ├─ Equality constraints
│ │ │ ├── Few constraints → SQP
│ │ │ └── Many constraints → Augmented Lagrangian
│ │ │
│ │ └── Inequality constraints
│ │ ├── Smooth → SQP or Interior Point
│ │ └── Nonsmooth → Penalty methods
│ │
│ └─ NONLINEAR LEAST-SQUARES (min ||r(x)||²)
│ │
│ ├─ Is Jacobian of r(x) available?
│ │ ├── YES → Gauss-Newton or Levenberg-Marquardt
│ │ └── NO → Variable projection or L-BFGS
│ │
│ └─ Zero residual problem?
│ ├── YES → May converge faster (quadratic near solution)
│ └── NO → LM more robust
Method Selection by Problem Type
Root-Finding (f(x) = 0)
| Condition |
Method |
Notes |
| Small, Jacobian available |
Newton |
Quadratic convergence |
| Large, Jacobian available |
Newton-Krylov |
Matrix-free inner solve |
| Jacobian expensive |
Modified Newton |
Reuse J for k steps |
| No Jacobian, smooth |
Broyden |
Superlinear convergence |
| Fixed-point form |
Anderson acceleration |
Accelerates Picard |
| Very large, sparse |
Newton-Krylov + ILU |
Preconditioned |
Unconstrained Optimization (min F(x))
| Condition |
Method |
Notes |
| Hessian available |
Newton-TR |
Quadratic convergence |
| Gradient only |
BFGS or L-BFGS |
Superlinear |
| Large scale |
L-BFGS |
O(n) memory |
| Nonsmooth |
Subgradient, Bundle |
Slower convergence |
Least-Squares (min ||r(x)||²)
| Condition |
Method |
Notes |
| Small residual |
Gauss-Newton |
Fast near solution |
| Large residual |
Levenberg-Marquardt |
More robust |
| Very large |
Variable projection |
Separable structure |
| No Jacobian |
L-BFGS on |
|
Application-Specific Recommendations
Phase-Field Simulations
| Equation Type |
Recommended |
Notes |
| Allen-Cahn |
Newton-Krylov |
Smooth, can be stiff |
| Cahn-Hilliard |
Newton + preconditioner |
4th order, ill-conditioned |
| Crystal plasticity |
Modified Newton |
Expensive Jacobian |
| Multiphase |
Anderson/Picard + acceleration |
Fixed-point nature |
Navier-Stokes
| Formulation |
Recommended |
Notes |
| Steady |
Newton-Krylov + block precond |
Saddle point structure |
| Unsteady (implicit) |
Modified Newton |
Reuse Jacobian over time |
| Turbulent (RANS) |
Under-relaxed Picard |
Stability first |
| Large Reynolds |
Continuation in Re |
Globalization |
Solid Mechanics
| Problem |
Recommended |
Notes |
| Linear elasticity |
Direct (if linear) |
Not truly nonlinear |
| Hyperelasticity |
Newton + line search |
May need regularization |
| Plasticity |
Modified Newton |
Tangent expensive |
| Contact |
SQP or Augmented Lagrangian |
Inequality constraints |
Failure Modes and Remedies
Common Problems
| Symptom |
Likely Cause |
Remedy |
| No convergence |
Poor initial guess |
Continuation, better starting point |
| Divergence |
Step too large |
Line search, trust region |
| Slow convergence |
Poor Jacobian |
Better preconditioner, exact Jacobian |
| Oscillation |
Step size issues |
Damping, trust region |
| Stagnation |
Singular Jacobian |
Regularization, different formulation |
When Newton Fails
- Check Jacobian accuracy: Compare with finite-difference
- Add globalization: Line search or trust region
- Try continuation: Gradually increase difficult parameters
- Check conditioning: May need scaling or preconditioning
- Reformulate: Sometimes a different formulation is better
When Quasi-Newton Fails
- Reset Hessian approximation: Start fresh with identity
- Switch to BFGS: More stable than SR1/Broyden for optimization
- Try L-BFGS: Less aggressive updates
- Use Newton: If Jacobian/Hessian is available
Globalization Summary
| Method |
Use When |
| Line search (Armijo) |
Standard, root-finding |
| Line search (Wolfe) |
Optimization, quasi-Newton |
| Backtracking |
Simple, when Armijo sufficient |
| Trust region |
Ill-conditioned, near-singular |
| Levenberg-Marquardt |
Least-squares |
| Damped Newton |
Simple alternative to line search |
Quick Reference Table
| Problem |
First Choice |
Alternative |
Globalization |
| Small root-finding |
Newton |
Broyden |
Line search |
| Large root-finding |
Newton-Krylov |
Anderson |
Trust region |
| Small optimization |
BFGS |
Newton |
Wolfe line search |
| Large optimization |
L-BFGS |
Truncated Newton |
Trust region |
| Least-squares |
Levenberg-Marquardt |
Gauss-Newton |
Trust region |
| Bound constrained |
L-BFGS-B |
Trust-region reflective |
Projected |
| General constrained |
SQP |
Interior Point |
Merit function |
1---2name: nonlinear-solver-decision-tree3description: Comprehensive decision guide for selecting nonlinear solvers for f(x)=0 or min F(x).4---5# Nonlinear Solver Decision Tree67Comprehensive decision guide for selecting nonlinear solvers for f(x)=0 or min F(x).89## Problem Classification1011### Key Properties to Determine1213| Property | How to Check | Impact |14|----------|--------------|--------|15| Problem type | Root-finding, optimization, least-squares | Determines solver class |16| Jacobian availability | Analytic vs finite-difference | Newton vs quasi-Newton |17| Problem size | Number of unknowns | Memory and algorithm choice |18| Smoothness | Continuous derivatives | Enables fast convergence |19| Constraints | Bounds, equalities, inequalities | Specialized methods needed |20| Hessian SPD | Optimization: F''(x) > 0 | BFGS maintains this property |2122### Quick Classification2324```25Problem type:26├── f(x) = 0 (root-finding/nonlinear equations)27├── min F(x) (unconstrained optimization)28├── min F(x) s.t. g(x) = 0 (equality constrained)29├── min F(x) s.t. l ≤ x ≤ u (bound constrained)30└── min ||r(x)||² (nonlinear least-squares)31```3233## Primary Decision Tree3435```36START: Need to solve nonlinear problem37│38├─ What type of problem?39│ │40│ ├─ ROOT-FINDING (f(x) = 0)41│ │ │42│ │ ├─ Is analytic Jacobian available?43│ │ │ │44│ │ │ ├── YES, cheap to compute45│ │ │ │ ├── Small problem (n < 1000) → Newton (full)46│ │ │ │ ├── Large problem → Newton-Krylov (GMRES/BiCGSTAB)47│ │ │ │ └── Sparse Jacobian → Newton-Krylov with ILU48│ │ │ │49│ │ │ ├── YES, expensive to compute50│ │ │ │ ├── Modified Newton (reuse Jacobian)51│ │ │ │ └── Broyden update52│ │ │ │53│ │ │ └── NO (finite-diff or unavailable)54│ │ │ ├── Smooth problem → Broyden (good/bad)55│ │ │ ├── Fixed-point form → Anderson acceleration56│ │ │ └── Very large → Newton-Krylov (matrix-free)57│ │ │58│ │ └─ Convergence issues?59│ │ ├── Diverging → Add line search or trust region60│ │ ├── Stagnating → Better preconditioner61│ │ └── Oscillating → Reduce step, add damping62│ │63│ ├─ UNCONSTRAINED OPTIMIZATION (min F(x))64│ │ │65│ │ ├─ Is Hessian available?66│ │ │ │67│ │ │ ├── YES → Newton with trust region68│ │ │ │ └── Large problem → Truncated Newton (CG)69│ │ │ │70│ │ │ └── NO → Use quasi-Newton71│ │ │ ├── Moderate size → BFGS72│ │ │ └── Large problem → L-BFGS73│ │ │74│ │ └─ Is objective smooth?75│ │ ├── YES → Standard quasi-Newton76│ │ └── NO → Subgradient methods, bundle methods77│ │78│ ├─ CONSTRAINED OPTIMIZATION79│ │ │80│ │ ├─ Bound constraints only81│ │ │ ├── Smooth → L-BFGS-B82│ │ │ └── General → Trust-region reflective83│ │ │84│ │ ├─ Equality constraints85│ │ │ ├── Few constraints → SQP86│ │ │ └── Many constraints → Augmented Lagrangian87│ │ │88│ │ └── Inequality constraints89│ │ ├── Smooth → SQP or Interior Point90│ │ └── Nonsmooth → Penalty methods91│ │92│ └─ NONLINEAR LEAST-SQUARES (min ||r(x)||²)93│ │94│ ├─ Is Jacobian of r(x) available?95│ │ ├── YES → Gauss-Newton or Levenberg-Marquardt96│ │ └── NO → Variable projection or L-BFGS97│ │98│ └─ Zero residual problem?99│ ├── YES → May converge faster (quadratic near solution)100│ └── NO → LM more robust101```102103## Method Selection by Problem Type104105### Root-Finding (f(x) = 0)106107| Condition | Method | Notes |108|-----------|--------|-------|109| Small, Jacobian available | Newton | Quadratic convergence |110| Large, Jacobian available | Newton-Krylov | Matrix-free inner solve |111| Jacobian expensive | Modified Newton | Reuse J for k steps |112| No Jacobian, smooth | Broyden | Superlinear convergence |113| Fixed-point form | Anderson acceleration | Accelerates Picard |114| Very large, sparse | Newton-Krylov + ILU | Preconditioned |115116### Unconstrained Optimization (min F(x))117118| Condition | Method | Notes |119|-----------|--------|-------|120| Hessian available | Newton-TR | Quadratic convergence |121| Gradient only | BFGS or L-BFGS | Superlinear |122| Large scale | L-BFGS | O(n) memory |123| Nonsmooth | Subgradient, Bundle | Slower convergence |124125### Least-Squares (min ||r(x)||²)126127| Condition | Method | Notes |128|-----------|--------|-------|129| Small residual | Gauss-Newton | Fast near solution |130| Large residual | Levenberg-Marquardt | More robust |131| Very large | Variable projection | Separable structure |132| No Jacobian | L-BFGS on ||r||² | Suboptimal but works |133134## Application-Specific Recommendations135136### Phase-Field Simulations137138| Equation Type | Recommended | Notes |139|---------------|-------------|-------|140| Allen-Cahn | Newton-Krylov | Smooth, can be stiff |141| Cahn-Hilliard | Newton + preconditioner | 4th order, ill-conditioned |142| Crystal plasticity | Modified Newton | Expensive Jacobian |143| Multiphase | Anderson/Picard + acceleration | Fixed-point nature |144145### Navier-Stokes146147| Formulation | Recommended | Notes |148|-------------|-------------|-------|149| Steady | Newton-Krylov + block precond | Saddle point structure |150| Unsteady (implicit) | Modified Newton | Reuse Jacobian over time |151| Turbulent (RANS) | Under-relaxed Picard | Stability first |152| Large Reynolds | Continuation in Re | Globalization |153154### Solid Mechanics155156| Problem | Recommended | Notes |157|---------|-------------|-------|158| Linear elasticity | Direct (if linear) | Not truly nonlinear |159| Hyperelasticity | Newton + line search | May need regularization |160| Plasticity | Modified Newton | Tangent expensive |161| Contact | SQP or Augmented Lagrangian | Inequality constraints |162163## Failure Modes and Remedies164165### Common Problems166167| Symptom | Likely Cause | Remedy |168|---------|--------------|--------|169| No convergence | Poor initial guess | Continuation, better starting point |170| Divergence | Step too large | Line search, trust region |171| Slow convergence | Poor Jacobian | Better preconditioner, exact Jacobian |172| Oscillation | Step size issues | Damping, trust region |173| Stagnation | Singular Jacobian | Regularization, different formulation |174175### When Newton Fails1761771. **Check Jacobian accuracy**: Compare with finite-difference1782. **Add globalization**: Line search or trust region1793. **Try continuation**: Gradually increase difficult parameters1804. **Check conditioning**: May need scaling or preconditioning1815. **Reformulate**: Sometimes a different formulation is better182183### When Quasi-Newton Fails1841851. **Reset Hessian approximation**: Start fresh with identity1862. **Switch to BFGS**: More stable than SR1/Broyden for optimization1873. **Try L-BFGS**: Less aggressive updates1884. **Use Newton**: If Jacobian/Hessian is available189190## Globalization Summary191192| Method | Use When |193|--------|----------|194| Line search (Armijo) | Standard, root-finding |195| Line search (Wolfe) | Optimization, quasi-Newton |196| Backtracking | Simple, when Armijo sufficient |197| Trust region | Ill-conditioned, near-singular |198| Levenberg-Marquardt | Least-squares |199| Damped Newton | Simple alternative to line search |200201## Quick Reference Table202203| Problem | First Choice | Alternative | Globalization |204|---------|--------------|-------------|---------------|205| Small root-finding | Newton | Broyden | Line search |206| Large root-finding | Newton-Krylov | Anderson | Trust region |207| Small optimization | BFGS | Newton | Wolfe line search |208| Large optimization | L-BFGS | Truncated Newton | Trust region |209| Least-squares | Levenberg-Marquardt | Gauss-Newton | Trust region |210| Bound constrained | L-BFGS-B | Trust-region reflective | Projected |211| General constrained | SQP | Interior Point | Merit function |
tools-only