Globalization Strategies

Globalization Strategies

Guide to line search, trust region, and damping strategies for nonlinear solvers.

Overview

Why Globalization?

Newton's method converges quadratically near the solution, but may:

• Diverge if initial guess is far
• Overshoot if step is too large
• Fail on singular or near-singular Jacobians

Globalization ensures convergence from "any" starting point.

Strategy Comparison

Line Search Methods

Backtracking Line Search

Algorithm:

Given: step p_k, initial α = 1, ρ ∈ (0,1), c ∈ (0,1)

while f(x_k + α p_k) > f(x_k) + c α ∇f^T p_k:
    α = ρ α

x_{k+1} = x_k + α p_k

Parameters:

Advantages:

• Simple to implement
• Low overhead per backtrack
• Works for most problems

Disadvantages:

• May take many backtracks
• No curvature information
• Can be inefficient for quasi-Newton

Armijo Condition

The Armijo (sufficient decrease) condition:

f(x_k + α p_k) ≤ f(x_k) + c₁ α ∇f(x_k)^T p_k

Geometric interpretation:

f(x)
  |
  |  *   Armijo condition requires staying
  | / \  below the dashed line
  |/   \____
  |-------- α

Wolfe Conditions

Strong Wolfe conditions:

Sufficient decrease: f(x_k + α p_k) ≤ f(x_k) + c₁ α ∇f^T p_k
Curvature:          |∇f(x_k + α p_k)^T p_k| ≤ c₂ |∇f(x_k)^T p_k|

Weak Wolfe (curvature):

∇f(x_k + α p_k)^T p_k ≥ c₂ ∇f(x_k)^T p_k

Parameters:

When to use Wolfe:

• BFGS and L-BFGS (curvature condition ensures valid update)
• Conjugate gradient methods
• When backtracking is expensive

Interpolation Line Search

Quadratic interpolation: Given f(0), f'(0), f(α):

α_new = -f'(0) α² / (2 (f(α) - f(0) - f'(0) α))

Cubic interpolation: Given f(α₀), f(α₁), f'(0):

Better approximation using two function values and derivative

Advantages:

• Fewer function evaluations than backtracking
• Better estimate of optimal step

Safeguards:

if α_new < 0.1 α or α_new > 0.9 α:
    α_new = 0.5 α  # Bisection fallback

Trust Region Methods

Basic Trust Region Framework

Subproblem:

Minimize m_k(p) = f_k + ∇f_k^T p + ½ p^T B_k p
subject to ||p|| ≤ Δ_k

Algorithm:

1. Compute step p_k by solving subproblem
2. Compute ratio ρ_k = (f(x_k) - f(x_k + p_k)) / (m_k(0) - m_k(p_k))
3. Update trust radius based on ρ_k:
   - ρ_k < 0.25: shrink Δ
   - ρ_k > 0.75 and ||p_k|| = Δ_k: expand Δ
   - otherwise: keep Δ
4. If ρ_k > η: accept step x_{k+1} = x_k + p_k

Parameters:

Cauchy Point

The Cauchy point minimizes along steepest descent:

p_C = -α_C ∇f  where α_C minimizes m_k(-α ∇f) for ||−α∇f|| ≤ Δ

Computation:

If ∇f^T B ∇f ≤ 0:  (negative curvature)
    α_C = Δ / ||∇f||
Else:
    α_C = min(||∇f||² / (∇f^T B ∇f), Δ / ||∇f||)

p_C = -α_C ∇f

Properties:

• Always well-defined
• Provides sufficient decrease guarantee
• Usually not optimal step

Dogleg Method

Combines Cauchy and Newton steps:

1. Compute Cauchy point p_C
2. Compute Newton step p_N = -B^{-1} ∇f
3. If ||p_N|| ≤ Δ: return p_N (Newton step in region)
4. If ||p_C|| ≥ Δ: return scaled p_C (Cauchy on boundary)
5. Otherwise: interpolate between p_C and p_N to hit boundary

The dogleg path:

     p_N *
        /
       /
      /
     /  <- leg 2
    *----
   p_C  ^
        |
        leg 1
        |
   -----O (origin)

Advantages:

• Simple closed-form solution
• Works well when B is positive definite
• Good balance of cost and quality

Disadvantages:

• Requires B positive definite
• May not be optimal for indefinite B

Steihaug-CG (Truncated Conjugate Gradient)

For large-scale or indefinite problems:

1. Start CG iteration for B p = -∇f
2. If direction of negative curvature detected:
   - Extend current direction to trust region boundary
3. If CG step exits trust region:
   - Interpolate to boundary
4. If converged within region:
   - Return CG solution

Advantages:

• Handles indefinite B
• Efficient for large problems
• Exploits Hessian structure

Disadvantages:

• More complex implementation
• May terminate early

Levenberg-Marquardt (Damped Newton)

Modified Newton step:

(J^T J + λ I) p = -J^T r   (least-squares)
(B + λ I) p = -∇f          (general optimization)

λ interpretation:

• λ = 0: Pure Newton/Gauss-Newton
• λ → ∞: Steepest descent
• λ interpolates between them

λ update strategy:

ρ = actual_reduction / predicted_reduction

if ρ < 0.25:
    λ = λ × 4
elif ρ > 0.75:
    λ = λ / 2

Advantages:

• Regularizes singular/ill-conditioned Jacobian
• Smooth transition from steepest descent to Newton
• Standard for nonlinear least-squares

Damping Strategies

Constant Damping

Simple damped Newton:

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

Typical ω values:

Adaptive Damping

Increase when successful, decrease on failure:

if ||f(x_{k+1})|| < ||f(x_k)||:
    ω = min(1.0, ω × 1.1)  # Gradually increase
else:
    ω = ω × 0.5            # Reduce on failure

Under-relaxation for Coupled Systems

For multiphysics coupling:

x_1^{n+1} = x_1^n + ω_1 (x̃_1 - x_1^n)
x_2^{n+1} = x_2^n + ω_2 (x̃_2 - x_2^n)

Aitken acceleration:

ω_{k+1} = ω_k × (r_k^T (r_k - r_{k-1})) / ||r_k - r_{k-1}||²

Parameter Selection Guidelines

Line Search Selection

Trust Region Selection

Switching Strategy

When to switch from line search to trust region:

• Multiple failed line searches
• Oscillating residuals
• Very ill-conditioned Jacobian
• Near-singular system detected

Practical Recommendations

Starting Points

1. Conservative start:

   • Trust region: Δ₀ = 0.1 × ||x₀||
   • Line search: α₀ = 0.5 (not full Newton)

2. Aggressive start:

   • Trust region: Δ₀ = 1.0
   • Line search: α₀ = 1.0 (full Newton)

Monitoring

Track these quantities:

- ρ = actual/predicted reduction (trust region)
- α = step size taken (line search)
- ||p|| / Δ (fraction of trust region used)
- ||∇f|| (gradient norm)
- ||f|| (residual/objective)

Common Adjustments

Failure Recovery

1. Failed line search:
   - Try trust region instead
   - Check Jacobian sign
   - Reduce initial α

2. Failed trust region:
   - Decrease Δ more aggressively
   - Add LM regularization
   - Check for local minimum

3. Repeated failures:
   - Problem may be infeasible
   - Try different formulation
   - Use continuation methods