Trust Region Reflective Algorithm¶

NLSQ uses the Trust Region Reflective (TRF) algorithm for optimization. This guide explains how TRF works and why it’s well-suited for curve fitting.

Why Trust Region?¶

Classical Newton methods take steps based on local quadratic approximations. These steps can be too large, causing:

Overshooting the minimum
Divergence in flat regions
Numerical instability

Trust region methods solve this by:

Building a quadratic model of the objective
Limiting the step size to a “trust region”
Adjusting the region size based on how well the model predicts

The Algorithm¶

At each iteration:

Build quadratic model:

\[m(δ) = \|r + Jδ\|^2 \approx S(θ + δ)\]

where r = residuals, J = Jacobian
Minimize within trust region:

\[\min_δ m(δ) \quad \text{subject to} \quad \|δ\| ≤ Δ\]
Compute actual vs predicted improvement:

\[ρ = \frac{S(θ) - S(θ + δ)}{m(0) - m(δ)}\]
Update trust region:
- ρ > 0.75: Expand region (Δ ← 2Δ)
- ρ < 0.25: Shrink region (Δ ← 0.25Δ)
- 0.25 ≤ ρ ≤ 0.75: Keep same
Accept or reject step:
- ρ > 0: Accept (θ ← θ + δ)
- ρ ≤ 0: Reject (keep θ)

Handling Bounds¶

The “Reflective” part of TRF handles parameter bounds elegantly:

Problem: Parameters must stay within [lower, upper].

Solution: Transform the problem so that the optimizer can explore freely, but the actual parameters stay bounded.

Unconstrained space     Bounded space
      -∞ ─────────────── lower
       │                   │
       0 ═══════════════ middle
       │                   │
      +∞ ─────────────── upper

When a step would exceed a bound:

Reflect: Bounce back from the boundary
Reduce: Take a smaller step along the boundary
Project: Clip to the nearest valid value

This is why bounds in NLSQ “just work” - you specify them, and TRF handles the constrained optimization automatically.

Comparison with Other Methods¶

Method	Pros	Cons
TRF (NLSQ default)	Robust, handles bounds well, converges reliably	Slightly slower per iteration
Levenberg-Marquardt	Fast for unconstrained problems	No bound handling
Dogbox	Simple bound handling	Can be slow near bounds
Gauss-Newton	Fast when near solution	Can diverge, no bounds

NLSQ uses TRF because it combines robustness with excellent bound handling.

SVD Subproblem Solver¶

The trust region subproblem is solved using Singular Value Decomposition (SVD):

\[J = UΣV^T\]

This provides:

Numerical stability: Works even with near-singular Jacobians
Condition information: Singular values reveal ill-conditioning
Null space handling: Properly manages underdetermined problems

Convergence Properties¶

TRF has strong convergence guarantees:

Global convergence: From any starting point, converges to a stationary point (local minimum or saddle)
Local quadratic convergence: Near the solution, converges quadratically (like Newton’s method)
Superlinear convergence: Even with inexact subproblem solutions

Tuning Parameters¶

NLSQ exposes TRF tuning via tolerances:

popt, pcov = curve_fit(
    model,
    x,
    y,
    gtol=1e-8,  # Gradient tolerance
    ftol=1e-8,  # Function tolerance
    xtol=1e-8,  # Step tolerance
    max_nfev=500,  # Max function evaluations
)

Guidelines:

Tighter tolerances (1e-10): More precise, slower
Looser tolerances (1e-6): Faster, may stop early
Default (1e-8): Good balance for most problems

Monitoring Convergence¶

NLSQ provides convergence information:

result = curve_fit(model, x, y)

print(f"Iterations: {result.nit}")
print(f"Function evaluations: {result.nfev}")
print(f"Final cost: {result.cost}")
print(f"Optimality: {result.optimality}")  # Gradient norm
print(f"Message: {result.message}")

Summary¶

The Trust Region Reflective algorithm:

Uses a quadratic model of the objective
Limits steps to a trust region for stability
Adjusts region size based on prediction quality
Handles bounds via reflective transformations
Solves subproblems with SVD for numerical stability

This makes it robust, reliable, and suitable for a wide range of curve fitting problems.