Math Trust Regions and Optimization

Trust Regions and Optimization: Bounded Steps in Local Approximations

Quick-Scan Infobox

Aspect	Details
Target User	Educators simulating safe explorations, developers constraining updates—optimization basics assumed.
Core Goal	Illuminate trust regions as adaptive bubbles: shrink on mismatches, expand on wins for robust descent without overshoots.
Time to First Adjust	4 minutes: Compute rho equals 0.8 on toy step, update r_t equals 1.2 times r.
Key Analogy	Puppy on a leash: Region r as slack—shorten if it tugs wrong (bad rho), lengthen for good pulls (actual greater than predicted).
Compitum Integration	SRMF in control.py; caps metric and Lyapunov updates.
Known Limitation	Quadratic models fail in highly nonlinear regions; requires frequent Hessian updates for accuracy.

---

System Overview: The Trust Region Cycle

graph TB
    A[Current Point x_k] --> B[Build Quadratic Model: m_k p equals g transpose p plus 0.5 p transpose B p]
    B --> C[Solve Subproblem: minimize m_k p subject to norm p less than or equal Delta_k]
    C --> D[Compute Trial Step: x_trial equals x_k plus p_k]
    D --> E[Measure Actual Reduction: actual equals f x_k minus f x_trial]
    E --> F[Measure Predicted Reduction: pred equals m_k 0 minus m_k p_k]
    F --> G{Compute rho equals actual over pred}
    
    G -->|rho greater than 0.75: Great match| H[Accept Step and Expand Delta: Delta_new equals 2 Delta]
    G -->|0.1 less than or equal rho less than or equal 0.75: Good match| I[Accept Step and Keep Delta: Delta_new equals Delta]
    G -->|rho less than 0.1: Poor match| J[Reject Step and Shrink Delta: Delta_new equals Delta over 2]
    
    H --> K[x_k plus 1 equals x_trial]
    I --> K
    J --> L[x_k plus 1 equals x_k]
    
    K --> A
    L --> A
    
    style A fill:#e1f5ff,stroke:#01579b
    style G fill:#fff4e1,stroke:#ef6c00
    style H fill:#e1ffe1,stroke:#1b5e20
    style I fill:#fffae1,stroke:#f57f17
    style J fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Path from current point through model building, trial step evaluation, and adaptive radius adjustment. Alt text: Graph with 15 nodes showing trust region optimization cycle, blue current point, amber decision node, green accept and expand, yellow accept and maintain, pink reject and shrink.

---

Core Principles Layer: Technical Backbone

Trust regions enforce local fidelity in optimization: Solve subproblems to minimize m_k(p) (quadratic model of f at x_k) subject to norm p less than or equal Delta_k (trust radius), then accept if actual reduction f(x_k + p) minus f(x_k) greater than or equal eta times predicted m_k(0) minus m_k(p) (eta in (0,1)), adjusting Delta_{k+1} equals gamma times Delta_k (gamma greater than 1 expand, less than 1 shrink) based on rho equals actual over predicted.

The Adaptive Trust Cycle

graph TD
    Start[Initialize at x_0] --> BuildModel[Build Model m_k at x_k]
    BuildModel --> SolveSubproblem[Find p_k where norm p less than or equal Delta_k]
    SolveSubproblem --> EvaluateStep[Measure actual and predicted reductions]
    EvaluateStep --> ComputeRho[Calculate rho equals actual over pred]
    
    ComputeRho --> CheckExcellent{rho greater than 0.75?}
    CheckExcellent -->|Yes| Excellent[Accept Step and Expand: x_k plus 1 equals x_k plus p_k, Delta_k plus 1 equals 2 Delta_k]
    CheckExcellent -->|No| CheckGood{rho between 0.1 and 0.75?}
    
    CheckGood -->|Yes| Good[Accept Step and Maintain: x_k plus 1 equals x_k plus p_k, Delta_k plus 1 equals Delta_k]
    CheckGood -->|No| Poor[Reject Step and Shrink: x_k plus 1 equals x_k, Delta_k plus 1 equals Delta_k over 2]
    
    Excellent --> CheckConverged{Converged?}
    Good --> CheckConverged
    Poor --> CheckConverged
    
    CheckConverged -->|No| BuildModel
    CheckConverged -->|Yes| End[Optimization Complete]
    
    style Start fill:#e1f5ff,stroke:#01579b
    style ComputeRho fill:#fff4e1,stroke:#ef6c00
    style Excellent fill:#e1ffe1,stroke:#1b5e20
    style Good fill:#fffae1,stroke:#f57f17
    style Poor fill:#ffe1e1,stroke:#c2185b
    style End fill:#e8f5e9,stroke:#1b5e20

Loading

Caption: State transitions in trust region optimization. Alt text: Graph with 12 nodes showing initialization through convergence, blue start, amber decision, green excellent, yellow good, pink poor, green end.

Historical Evolution Timeline

graph TD
    A1940[1940s-60s: Levenberg-Marquardt Algorithm] --> A1963[1963: Marquardt Damped Least-Squares]
    A1963 --> A1978[1978: More TR-SQP Methods]
    A1978 --> A1980[1980s: More-Sorensen Generalization]
    A1980 --> A2000[2000: Conn-Gould-Toint Survey]
    A2000 --> A2006[2006: Nocedal-Wright Textbook]
    A2006 --> A2020[2020s: Compitum SRMF Implementation]

Loading

Caption: Key milestones in trust region method development. Alt text: Timeline with seven nodes from 1940s to 2020s showing evolution of trust region methods.

Historical Context:

• Levenberg-Marquardt (1940s-60s): Foundation for adaptive damping in nonlinear least-squares
• Marquardt (1963): Introduced damping parameter blending gradient and Newton methods
• Moré (1978): Extended to sequential quadratic programming with trust region globalization
• Moré-Sorensen (1983): Proved global convergence for general nonlinear problems
• Conn-Gould-Toint (2000): Comprehensive theoretical treatment in landmark book
• Nocedal-Wright (2006): Canonical reference for practitioners

The Trust Region Landscape

graph LR
    subgraph TrustRegion[Trust Region Delta_k]
        C[Current Point x_k]
        P1[Cauchy Point: steepest descent]
        P2[Newton Point: if norm p less than or equal Delta]
        P3[Boundary: norm p equals Delta]
        
        C -.-> P1
        C -.-> P2
        C --> P3
    end
    
    subgraph Outside[Outside Region]
        O1[Too Aggressive: Model unreliable]
    end
    
    P3 -.->|Violates constraint| O1
    
    style C fill:#fff4e1,stroke:#ef6c00
    style P1 fill:#e1f5ff,stroke:#01579b
    style P2 fill:#e1ffe1,stroke:#1b5e20
    style P3 fill:#ffe1e1,stroke:#c2185b
    style O1 fill:#ffcccc,stroke:#b71c1c

Loading

Caption: Interior and boundary solutions within trust region. Alt text: Graph with two subgraphs showing trust region interior points and outside boundary violations, amber current, blue Cauchy, green Newton, pink boundary, red outside.

Mathematical Framework

Key Results:

• Sufficient Decrease: rho greater than eta ensures descent; adaptive Delta yields superlinear convergence rates near optima (O(Delta squared) locally)
• Quadratic Convergence: In quadratic spaces, trust regions bound geodesics, preventing conditioning jumps greater than 10x
• Adaptive Strategy: Low rho less than 0.25 triggers radius halving: Delta equals Delta over 2

Convergence Properties:

• Global: All limit points are stationary under mild assumptions
• Local: Superlinear convergence when Hessian approximation is accurate
• Robustness: Handles non-convexity better than pure line search methods

Limitation: Quadratic models assume local linearity; highly nonlinear regions need frequent updates.

---

Implementation Deep Dive

The Optimization Framework

graph TD
    A[Problem: minimize f x] --> B[At iteration k]
    B --> C[Build Quadratic Model]
    C --> D[m_k p equals g_k transpose p plus 0.5 p transpose B_k p]
    
    D --> E[Constrained Subproblem]
    E --> F[p_k equals argmin m_k p]
    E --> G[subject to: norm p less than or equal Delta_k]
    
    F --> H{Solution Strategy?}
    H -->|Unconstrained minimum inside| I[Newton Step: p equals negative B_k inverse g_k]
    H -->|Boundary solution| J[Cauchy or Dogleg: norm p equals Delta_k]
    
    I --> K[Evaluate Quality]
    J --> K
    
    K --> L[rho_k equals actual_red over pred_red]
    L --> M{Decision?}
    M -->|rho greater than eta_1| N[Accept and Expand]
    M -->|rho less than or equal eta_1| O[Reject and Shrink]
    
    style A fill:#e1f5ff,stroke:#01579b
    style D fill:#fff4e1,stroke:#ef6c00
    style L fill:#ffe1f5,stroke:#e91e63
    style N fill:#e1ffe1,stroke:#1b5e20
    style O fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Framework from problem formulation through solution strategy. Alt text: Graph with 17 nodes showing optimization workflow, blue problem, amber model, pink quality ratio, green accept, pink reject.

Mathematical Formulation

Subproblem:

p_k = argmin_p { m_k(p) = g_k^T p + (1/2) p^T B_k p }
subject to: ||p|| ≤ Delta_k

Quality Ratio:

rho_k = [f(x_k) - f(x_k + p_k)] / [m_k(0) - m_k(p_k)]

Radius Adjustment:

If rho_k ≥ eta_1 (0.1):
    Delta_{k+1} = max(Delta_k, gamma_1 * ||p_k||)  // Expand, gamma_1=2
Else:
    Delta_{k+1} = Delta_k / 2  // Shrink

Code Implementation

Open on GitHub | Open in nbviewer | Launch in Binder

Snippet from Math-Trust-Regions-and-Optimization.md

import numpy as np

def trust_step(g: np.ndarray, B: np.ndarray, Delta: float,
               eta1: float = 0.1, gamma1: float = 2.0) -> tuple:
    """
    Execute one trust region step with adaptive radius adjustment.
    
    Args:
        g: Gradient vector (d,).
        B: Hessian approximation (d x d).
        Delta: Current trust radius.
        eta1: Acceptance threshold for rho.
        gamma1: Expansion factor.
    
    Returns:
        Tuple of (step p, quality ratio rho, new radius Delta).
    """
    
    # Compute Cauchy point (steepest descent approximation)
    g_norm = np.linalg.norm(g)
    if g_norm == 0:
        return np.zeros_like(g), 1.0, Delta
    
    # Scale gradient to trust boundary
    p = -(Delta / g_norm) * g
    
    # Predicted reduction (quadratic model)
    m0 = 0
    m_p = g @ p + 0.5 * p @ B @ p
    pred_red = m0 - m_p
    
    # Actual reduction (in practice: route and measure energy change)
    # Here using toy: 70% match for demonstration
    actual_red = 0.7 * pred_red
    
    # Compute quality ratio
    rho = actual_red / pred_red if pred_red > 0 else -1
    
    # Accept/reject and adjust radius
    accept = rho > eta1
    if accept:
        Delta_new = min(gamma1 * Delta, 2 * np.linalg.norm(p))
    else:
        Delta_new = Delta / 2
    
    return p, rho, Delta_new

# Example: Gradient descent with trust region control
g = np.array([1.0, 0.5])  # Gradient
B = np.eye(2) * 0.1       # Hessian approximation
Delta = 1.0               # Initial trust radius

p, rho, Delta_new = trust_step(g, B, Delta)

print("Trust Region Step Results")
print("=" * 50)
print(f"Step direction: {p}")
print(f"Quality ratio rho: {rho:.2f}")
print(f"Accept step: {rho > 0.1}")
print(f"New radius Delta: {Delta_new:.2f}")
print(f"\nInterpretation:")
print(f"  rho > 0.75: Excellent (expand aggressively)")
print(f"  0.1 ≤ rho ≤ 0.75: Good (maintain or expand)")
print(f"  rho < 0.1: Poor (reject and shrink)")

Expected Output:

Trust Region Step Results
==================================================
Step direction: [-0.89442719 -0.4472136 ]
Quality ratio rho: 0.70
Accept step: True
New radius Delta: 2.00

Interpretation:
  rho > 0.75: Excellent (expand aggressively)
  0.1 ≤ rho ≤ 0.75: Good (maintain or expand)
  rho < 0.1: Poor (reject and shrink)

Note: Values depend on toy model; real applications measure actual function change. Limitation: Cauchy point is conservative; dogleg or CG methods yield better steps.

---

Approachable Layer: Educator's Guide

The Puppy Leash Analogy

graph LR
    subgraph GoodBehavior[Good Behavior: rho greater than 0.75]
        P1[Puppy] -->|Pulls correctly| L1[Lengthen Leash: Delta_new equals 2 Delta]
        L1 --> R1[More exploration freedom]
    end
    
    subgraph NeutralBehavior[Neutral Behavior: 0.1 less than or equal rho less than or equal 0.75]
        P2[Puppy] -->|Stays on path| L2[Keep Leash: Delta_new equals Delta]
        L2 --> R2[Steady progress]
    end
    
    subgraph BadBehavior[Bad Behavior: rho less than 0.1]
        P3[Puppy] -->|Tugs wrong way| L3[Shorten Leash: Delta_new equals Delta over 2]
        L3 --> R3[Restricted movement]
    end
    
    style R1 fill:#e1ffe1,stroke:#1b5e20
    style R2 fill:#fffae1,stroke:#f57f17
    style R3 fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Adaptive leash adjustment based on puppy behavior. Alt text: Graph with three subgraphs showing good/neutral/bad behavior leading to lengthen/keep/shorten leash, green freedom, yellow steady, pink restricted.

Teaching Applications Flow

graph TD
    A[Design Lesson Variation] --> B[Predict Engagement Gain: quadratic model]
    B --> C[Implement with Scope Delta]
    C --> D[Measure Actual Engagement: student responses]
    D --> E[Calculate rho equals actual over predicted]
    
    E --> F{Quality Check?}
    F -->|rho greater than 0.75: Big success| G[Expand Approach: Next larger variation]
    F -->|rho moderate: Works well| H[Maintain Approach: Next same scale]
    F -->|rho less than 0.1: Did not work| I[Reduce Scope: Next smaller steps]
    
    G --> J[Scale to full class]
    H --> K[Continue with cohort]
    I --> L[Test with subgroup]
    
    J --> M[Document and Share]
    K --> M
    L --> M
    
    style A fill:#e1f5ff,stroke:#01579b
    style E fill:#fff4e1,stroke:#ef6c00
    style G fill:#e1ffe1,stroke:#1b5e20
    style H fill:#fffae1,stroke:#f57f17
    style I fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Lesson planning with trust region adaptation. Alt text: Graph with 13 nodes showing design through documentation, blue design, amber evaluation, green expand, yellow maintain, pink reduce.

Classroom Applications

Debate Expansion Example:
Trust regions guide debate format scaling. Predict engagement gain from expanding to full class (quadratic model of past cohort data), implement with scope Delta equals medium, measure actual participation rates, compute rho. If rho equals 0.3 (moderate), maintain scope for next unit; if rho equals 0.85, scale to full grade level.

Key Insights:

• Adaptive Bounding: Like measuring leash slack based on previous walks
• Iterative Refinement: Each iteration informs next scope adjustment
• Risk Management: Small steps when uncertain, larger when confident

Common Pitfalls:

• Stale Models: Refresh Hessian B every 5 steps to keep rho honest
• Over-Optimism: Cap maximum Delta to prevent unrealistic expansions
• Threshold Sensitivity: Test multiple eta values to find classroom sweet spot

Limitation: Analogies simplify; validate with domain-specific data before production use.

---

Quick-Reference Toolkit

Component Architecture

graph LR
    subgraph Inputs[Input Components]
        I1[Gradient g_k: d dimensions]
        I2[Hessian B_k: d x d]
        I3[Trust Radius Delta_k]
    end
    
    subgraph Processing[Core Processing]
        P1[Build Quadratic Model]
        P2[Solve Constrained Subproblem]
        P3[Evaluate Quality Ratio]
    end
    
    subgraph Outputs[Output Signals]
        O1[Step Direction p_k]
        O2[Quality Ratio rho_k]
        O3[New Radius Delta_k plus 1]
    end
    
    I1 --> P1
    I2 --> P1
    I3 --> P2
    P1 --> P2
    P2 --> P3
    P3 --> O1
    P3 --> O2
    O2 --> O3
    
    style Inputs fill:#e3f2fd,stroke:#01579b
    style Processing fill:#e8f5e9,stroke:#1b5e20
    style Outputs fill:#fff3e0,stroke:#ef6c00

Loading

Caption: Flow from inputs through processing to outputs. Alt text: Graph with three subgraphs and 12 nodes, blue inputs, green processing, amber outputs.

Parameter Reference Table

Element	Definition	Key Parameter	Range	Interpretation	Compitum Field
Subproblem	Minimize m_k(p) subject to norm p less than or equal Delta_k	B_k (Hessian approx)	Positive definite	Local optimization guess	Internal Cauchy solve
Predicted Reduction	m_k(0) minus m_k(p_k)	g_k, B_k	Greater than or equal 0	Model-based gain estimate	Quadratic energy approx
Quality Ratio	Actual over Predicted	eta_1 equals 0.1 threshold	(-infinity, infinity)	Model fidelity check	From energy change over pred
Radius Adjustment	Delta_{k+1} equals gamma Delta_k or over 2	gamma_1 equals 2 expand	(0, infinity)	Adaptive trust scaling	SRMF r_t

Parameter Sensitivity Guide

graph TD
    subgraph TrustRadius[Trust Radius Delta]
        D1[Too Small: Delta less than 0.01] --> DR1[Overly conservative and Slow convergence]
        D2[Sweet Spot: 0.1 less than or equal Delta less than or equal 10] --> DR2[Balanced and Good progress]
        D3[Too Large: Delta greater than 100] --> DR3[Reckless and Model unreliable]
    end
    
    subgraph AcceptanceThreshold[Acceptance Threshold eta]
        E1[Too Strict: eta greater than 0.5] --> ER1[Reject too often and Rarely expand]
        E2[Recommended: eta equals 0.1] --> ER2[Balanced acceptance]
        E3[Too Lenient: eta less than 0.01] --> ER3[Accept bad steps and Poor convergence]
    end
    
    subgraph ExpansionFactor[Expansion Factor gamma]
        G1[Conservative: gamma equals 1.2] --> GR1[Slow growth and Safe but slow]
        G2[Recommended: gamma equals 2.0] --> GR2[Moderate growth and Good balance]
        G3[Aggressive: gamma greater than 3.0] --> GR3[Fast growth and Risk instability]
    end
    
    style DR2 fill:#e1ffe1,stroke:#1b5e20
    style ER2 fill:#e1ffe1,stroke:#1b5e20
    style GR2 fill:#e1ffe1,stroke:#1b5e20
    style DR1 fill:#ffe1e1,stroke:#c2185b
    style DR3 fill:#ffe1e1,stroke:#c2185b
    style ER1 fill:#ffe1e1,stroke:#c2185b
    style ER3 fill:#ffe1e1,stroke:#c2185b
    style GR1 fill:#fffae1,stroke:#f57f17
    style GR3 fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Effects of parameter choices on optimization behavior. Alt text: Graph with three subgraphs showing radius/threshold/factor ranges with outcomes, green recommended, yellow conservative, pink problematic.

---

Common Gotchas and Solutions

Diagnostic Decision Tree

graph TD
    A{Trust Region Problem?} --> B[Model Mismatch]
    A --> C[Norm Incongruence]
    A --> D[Stuck Small Delta]
    A --> E[Explosive Blowup]
    
    B --> B1[Symptom: rho less than 0 frequently]
    B1 --> B2[Diagnosis: Stale Hessian or poor gradient]
    B2 --> B3[Fix: Update B every 5 steps and Add diagonal regularization]
    
    C --> C1[Symptom: Skewed norm p and inconsistent scaling]
    C1 --> C2[Diagnosis: Mismatched parameter spaces]
    C2 --> C3[Fix: Use Frobenius norm for matrices]
    
    D --> D1[Symptom: Delta never expands and stuck at minimum]
    D1 --> D2[Diagnosis: rho barely greater than 0.1 and conservative gamma]
    D2 --> D3[Fix: gamma_1 equals 1.5 minimum and force expand on rho greater than 0.75]
    
    E --> E1[Symptom: Delta approaches infinity and unbounded growth]
    E1 --> E2[Diagnosis: No upper cap and model too optimistic]
    E2 --> E3[Fix: Cap Delta_max equals 10 and couple with Lyapunov]
    
    style B fill:#ffe1e1,stroke:#c2185b
    style C fill:#ffe1e1,stroke:#c2185b
    style D fill:#ffe1e1,stroke:#c2185b
    style E fill:#ffe1e1,stroke:#c2185b
    style B3 fill:#e1ffe1,stroke:#1b5e20
    style C3 fill:#e1ffe1,stroke:#1b5e20
    style D3 fill:#e1ffe1,stroke:#1b5e20
    style E3 fill:#e1ffe1,stroke:#1b5e20

Loading

Caption: Problem identification and resolution paths. Alt text: Graph with 20 nodes showing problem types branching to symptoms/diagnosis/fixes, pink problems, green fixes.

Detailed Debugging Reference

Issue	Symptom	Fix	Analogy
Model Mismatch	rho less than 0 often	Update B frequently; add Hessian diagonal	Bad map—recalibrate compass
Norm Incongruence	Skewed norm p	Match to parameter space (Frobenius for matrices)	Wrong tape—measure apples to apples
Stuck Small Delta	No expansion	gamma_1 equals 1.5 minimum; force on rho greater than 0.75	Timid puppy—gentle encouragement
Explosive Blowup	Delta approaches infinity	Cap Delta_max equals 10; couple Lyapunov	Loose leash snap—add collar constraint

Detailed Diagnostic Flowchart

graph TD
    Start[Convergence Issues?] --> Check1{Check rho history?}
    
    Check1 -->|Many rho less than 0| Fix1[Model Quality Problem]
    Check1 -->|Many rho approximately 0.1| Fix2[Threshold Tuning Needed]
    Check1 -->|Good rho but slow| Fix3[Radius Too Conservative]
    Check1 -->|Unstable rho| Fix4[Normalization Issue]
    
    Fix1 --> Sol1[Update B more frequently and Check gradient accuracy and Add Hessian regularization]
    Fix2 --> Sol2[Lower eta threshold to 0.05 and Increase expansion factor gamma and Review step acceptance]
    Fix3 --> Sol3[Increase initial Delta_0 and More aggressive gamma equals 2.5 and Force expansion on high rho]
    Fix4 --> Sol4[Match norm to parameter space and Scale variables consistently and Use preconditioner]
    
    Sol1 --> Monitor[Monitor for 10 iterations]
    Sol2 --> Monitor
    Sol3 --> Monitor
    Sol4 --> Monitor
    
    Monitor --> Better{Improved?}
    Better -->|Yes| Success[Continue with new settings]
    Better -->|No| Check1
    
    style Start fill:#e1f5ff,stroke:#01579b
    style Success fill:#e1ffe1,stroke:#1b5e20
    style Fix1 fill:#ffe1e1,stroke:#c2185b
    style Fix2 fill:#ffe1e1,stroke:#c2185b
    style Fix3 fill:#ffe1e1,stroke:#c2185b
    style Fix4 fill:#ffe1e1,stroke:#c2185b

Loading

Caption: Iterative diagnostic and solution workflow. Alt text: Graph with 15 nodes showing convergence check through monitoring loop, blue start, pink problems, green success.

---

Integration Flow in Compitum

SRMF Controller Architecture

graph TB
    subgraph SRMFController[SRMF Controller in control.py]
        S1[Monitor Energy Change] --> S2[Build Quadratic Model]
        S2 --> S3[Solve Trust Region Subproblem]
        S3 --> S4[Compute Quality Ratio rho]
        S4 --> S5[Adjust Trust Radius Delta]
    end
    
    subgraph MetricUpdates[Metric Updates in metric.py]
        M1[Proposed Delta L update] --> M2{Check norm Delta L Frobenius less than or equal Delta?}
        M2 -->|Pass| M3[Apply Update]
        M2 -->|Fail| M4[Reject and Shrink Delta]
    end
    
    subgraph LyapunovCoupling[Lyapunov Coupling]
        L1[Current V] --> L2[Predicted Delta V]
        L2 --> L3{Delta V less than or equal 0?}
        L3 -->|Yes| L4[Stable: Proceed]
        L3 -->|No| L5[Unstable: Reject]
    end
    
    S5 --> M1
    M3 --> L1
    M4 --> S5
    L5 --> M4
    L4 --> Next[Next Iteration]
    
    style S4 fill:#fff4e1,stroke:#ef6c00
    style M2 fill:#ffe1f5,stroke:#e91e63
    style L3 fill:#e1f5ff,stroke:#01579b
    style Next fill:#e1ffe1,stroke:#1b5e20

Loading

Caption: Multi-module integration across Compitum components. Alt text: Graph with three subgraphs showing SRMF/Metric/Lyapunov coupling, 16 nodes, amber quality check, pink norm check, blue stability check, green next.

Multi-Scale Architecture

graph LR
    subgraph GlobalLevel[Global Level]
        G1[Observer Position] --> G2[Route Planning]
    end
    
    subgraph MetricLevel[Metric Level]
        Met1[SPD Matrix M] --> Met2[Low-Rank Factor L]
        Met2 --> Met3[Trust Radius Delta_M]
    end
    
    subgraph LocalLevel[Local Level]
        L1[Gradient g] --> L2[Hessian B]
        L2 --> L3[Step p]
        L3 --> L4[Quality rho]
    end
    
    G2 --> Met1
    Met3 --> L1
    L4 --> Met3
    L4 --> G1
    
    style G1 fill:#e1f5ff,stroke:#01579b
    style Met2 fill:#fff4e1,stroke:#ef6c00
    style L4 fill:#ffe1f5,stroke:#e91e63

Loading

Caption: Hierarchical control across spatial scales. Alt text: Graph with three subgraphs showing global/metric/local levels, 12 nodes, blue global, amber metric, pink local quality feedback.

---

Interactive Tuning Guide

Bandwidth Optimization Workflow

graph TD
    START[Begin Trust Region Tuning] --> SPLIT[Split: Train 80 percent, Validation 20 percent]
    SPLIT --> GRID[Grid Search: eta from 0.05 to 0.5, step 0.05]
    GRID --> LOOP[For each eta value]
    LOOP --> FIT[Run Optimization with eta]
    FIT --> EVAL[Measure Convergence Rate]
    EVAL --> STORE[Store eta and performance]
    STORE --> MORE{More eta values?}
    MORE -->|Yes| LOOP
    MORE -->|No| MAX[Select eta with Best Performance]
    MAX --> VIS[Visualize rho Distribution]
    VIS --> CHECK{Qualitatively Good?}
    CHECK -->|Yes| DONE[Deploy Parameters]
    CHECK -->|No| REVISE[Adjust Grid Range]
    REVISE --> GRID
    
    style START fill:#e3f2fd,stroke:#01579b
    style GRID fill:#fff3e0,stroke:#ef6c00
    style MAX fill:#e8f5e9,stroke:#1b5e20
    style DONE fill:#e8f5e9,stroke:#1b5e20
    style REVISE fill:#fff3e0,stroke:#ef6c00

Loading

Caption: Systematic parameter selection process. Alt text: Flowchart with 18 nodes showing start through grid search to deployment, blue start, amber grid/revise, green max/done.

Tuning Cookbook

Profiles:

Use Case	Delta_0	eta	gamma	Notes
Dense Data	0.5	0.1	2.0	Standard settings
Sparse Data	1.0	0.15	1.5	More conservative
High Noise	0.3	0.05	2.5	Stricter acceptance
Low Noise	1.5	0.2	2.0	Aggressive expansion
Initial Survey	0.8	0.1	2.0	Default exploration

Empirical Tuning Function:

Open on GitHub | Open in nbviewer | Launch in Binder

Snippet from Math-Trust-Regions-and-Optimization.md

def tune_trust_region(f, grad_f, x0, param_grid):
    """
    Find optimal trust region parameters via grid search.
    
    Args:
        f: Objective function.
        grad_f: Gradient function.
        x0: Initial point.
        param_grid: Dict with 'eta' and 'gamma' lists.
    
    Returns:
        Best parameters (eta, gamma, Delta_0).
    """
    best_iterations = float('inf')
    best_params = None
    
    for eta in param_grid['eta']:
        for gamma in param_grid['gamma']:
            for Delta_0 in param_grid['Delta_0']:
                # Run optimization
                x, history = trust_region_optimize(
                    f, grad_f, x0, 
                    Delta_init=Delta_0,
                    eta=eta, 
                    gamma=gamma,
                    max_iter=100
                )
                
                # Measure performance
                iterations = len(history)
                final_value = f(x)
                
                # Track best
                if iterations < best_iterations and final_value < 1e-6:
                    best_iterations = iterations
                    best_params = (eta, gamma, Delta_0)
    
    return best_params

# Example usage
param_grid = {
    'eta': [0.05, 0.1, 0.15, 0.2],
    'gamma': [1.5, 2.0, 2.5],
    'Delta_0': [0.5, 1.0, 1.5]
}

# best_eta, best_gamma, best_Delta = tune_trust_region(f, grad_f, x0, param_grid)

Limitation: Grid search is exhaustive; consider Bayesian optimization for high-dimensional parameter spaces.

Validation Checklist

graph TD
    A[Start Validation] --> B{Visual Quality?}
    B -->|Pass| C{Numeric Stability?}
    B -->|Fail| D[Adjust parameters by 50 percent]
    
    C -->|Pass| E{Convergence Rate?}
    C -->|Fail| F[Apply regularization or normalization]
    
    E -->|Pass| G{Production Ready?}
    E -->|Fail| H[Retune expansion factor]
    
    G -->|Pass| I[Deploy System]
    G -->|Fail| J[Collect more validation data]
    
    D --> B
    F --> C
    H --> E
    J --> G
    
    style A fill:#e3f2fd,stroke:#01579b
    style I fill:#e8f5e9,stroke:#1b5e20
    style D fill:#fff3e0,stroke:#ef6c00
    style F fill:#fff3e0,stroke:#ef6c00
    style H fill:#fff3e0,stroke:#ef6c00
    style J fill:#fff3e0,stroke:#ef6c00

Loading

Caption: Validation workflow with iterative refinement. Alt text: Graph showing checklist flow through visual/numeric/convergence/production branches, 15 nodes, blue start, green deploy, amber revision steps.

Checklist Items:

Phase	Test	Pass Criteria	Fail Action
Visual	rho distribution	60-80% in [0.1, 0.75] range	Adjust eta threshold
Visual	Delta trajectory	Smooth adaptation, no wild swings	Tune gamma factor
Numeric	No NaN or infinity	All values finite	Add gradient clipping
Numeric	Step acceptance	70-85% acceptance rate	Adjust eta or Delta_0
Convergence	Iterations to converge	Less than 100 for toy problems	Increase gamma or Delta_0
Convergence	Final objective value	Within tolerance (e.g., less than 1e-6)	Check model quality
Production	Robust to noise	Stable with 10% gradient noise	Lower eta threshold
Production	Scalability	Handles 100+ dimensional problems	Use approximate Hessian

---

Next Steps: Your Learning Loop

Learning Path

graph TD
    F1[Fundamentals: Read Documentation] --> F2[Run Sample Code]
    F2 --> F3[Visualize rho Distribution]
    F3 --> T1[Tuning: Experiment with eta]
    T1 --> T2[Validate Convergence Rate]
    T2 --> T3[Optimize for Your Domain]
    T3 --> A1[Advanced: Implement Dogleg]
    A1 --> A2[Test Lyapunov Coupling]
    A2 --> P1[Production: Track Trust Metrics]
    P1 --> P2[Benchmark Performance]
    
    style F1 fill:#e3f2fd,stroke:#01579b
    style F2 fill:#e3f2fd,stroke:#01579b
    style F3 fill:#e3f2fd,stroke:#01579b
    style T1 fill:#e8f5e9,stroke:#1b5e20
    style T2 fill:#e8f5e9,stroke:#1b5e20
    style T3 fill:#e8f5e9,stroke:#1b5e20
    style A1 fill:#fff3e0,stroke:#ef6c00
    style A2 fill:#fff3e0,stroke:#ef6c00
    style P1 fill:#fce4ec,stroke:#c2185b
    style P2 fill:#fce4ec,stroke:#c2185b

Loading

Caption: Progressive learning stages from fundamentals to production. Alt text: Timeline with four sections and 12 steps, blue fundamentals, green tuning, amber advanced, pink production.

Quick Start Checklist

graph LR
    A[Read Quick-Scan] --> B[Study Puppy Analogy]
    B --> C[Run Code Snippet]
    C --> D[Visualize rho Decision Tree]
    D --> E[Experiment with Delta]
    E --> F[Monitor in Compitum]
    F --> G[Tune Parameters]
    G --> H[Share Learnings]
    
    style A fill:#e1ffe1,stroke:#1b5e20
    style B fill:#e1ffe1,stroke:#1b5e20
    style C fill:#fff4e1,stroke:#ef6c00
    style D fill:#fff4e1,stroke:#ef6c00
    style E fill:#ffe1f5,stroke:#e91e63
    style F fill:#ffe1f5,stroke:#e91e63
    style G fill:#e1f5ff,stroke:#01579b
    style H fill:#e1f5ff,stroke:#01579b

Loading

Caption: Step-by-step onboarding sequence. Alt text: Linear flow with 8 nodes from reading to sharing, green read/study, amber run/visualize, pink experiment/monitor, blue tune/share.

Action Items:

Week 1: Fundamentals

• Understand rho ratio: Read Quick-Scan and Core Principles sections
• Study puppy analogy: Connect trust regions to intuitive leash metaphor
• Run code snippet: Execute trust_step function with toy data
• Visualize rho decision: Plot acceptance regions on sample trajectory

Week 2: Tuning

• Adjust eta threshold: Set eta equals 0.15 in config, route queries, observe acceptance rates
• Vary gamma factor: Test [1.5, 2.0, 2.5], measure convergence speed
• Delta sweep: Experiment with initial Delta_0 in [0.5, 1.0, 2.0]
• Cross-validation: Hold out 20% of data, optimize hyperparameters

Week 3: Advanced

• Implement dogleg: Code Cauchy-Newton interpolation for better steps
• Couple with Lyapunov: Verify Delta V less than or equal 0 constraint integration
• Production batch: Process 100+ queries, analyze trust radius evolution
• Performance profiling: Benchmark subproblem solve time

Ongoing:

• Document profiles: Share optimal (eta, gamma, Delta_0) for your domain
• Report issues: Submit bugs for norm mismatches, convergence failures
• Expand documentation: Add examples for high-dimensional problems
• Contribute code: Submit pull requests to control.py improvements

---

Advanced Topics

Dogleg Method for Better Steps

The dogleg method interpolates between Cauchy (steepest descent) and Newton directions for improved subproblem solutions.

graph TD
    A[Start at Origin] --> B[Compute Cauchy Point p_C]
    B --> C[Compute Newton Point p_N]
    C --> D{Newton within Delta?}
    
    D -->|Yes: norm p_N less than or equal Delta| E[Use Full Newton Step]
    D -->|No: norm p_N greater than Delta| F[Dogleg Path]
    
    F --> G[Segment 1: Origin to p_C]
    F --> H[Segment 2: p_C toward p_N]
    
    G --> I{Intersect with Delta?}
    H --> I
    
    I --> J[Find tau where norm dogleg tau equals Delta]
    J --> K[Return p dogleg tau]
    
    E --> L[Return p_N]
    K --> L
    
    style A fill:#e1f5ff,stroke:#01579b
    style E fill:#e1ffe1,stroke:#1b5e20
    style K fill:#fff4e1,stroke:#ef6c00

Loading

Caption: Dogleg interpolation between Cauchy and Newton directions. Alt text: Graph with 13 nodes showing decision flow for dogleg computation, blue start, green Newton, amber dogleg.

Implementation:

Open on GitHub | Open in nbviewer | Launch in Binder

Snippet from Math-Trust-Regions-and-Optimization.md

def dogleg_step(g: np.ndarray, B: np.ndarray, Delta: float) -> np.ndarray:
    """
    Compute dogleg trust region step.
    
    Args:
        g: Gradient (d,).
        B: Hessian approximation (d x d).
        Delta: Trust radius.
    
    Returns:
        Dogleg step p.
    """
    # Cauchy point (steepest descent)
    g_norm_sq = g @ g
    g_B_g = g @ B @ g
    
    if g_B_g <= 0:
        tau = 1.0
    else:
        # Nocedal & Wright (2006) eq. 4.12: ||g||^3 == (g@g)**1.5, NOT (g@g)**3
        tau = min(g_norm_sq**1.5 / (Delta * g_B_g), 1.0)
    
    p_C = -tau * (Delta / np.sqrt(g_norm_sq)) * g
    
    # Newton point
    try:
        p_N = -np.linalg.solve(B, g)
    except np.linalg.LinAlgError:
        return p_C  # Fallback to Cauchy
    
    # Check if Newton within trust region
    if np.linalg.norm(p_N) <= Delta:
        return p_N
    
    # Dogleg interpolation
    # Find tau in [0, 2] where ||p_C + (tau - 1)(p_N - p_C)|| = Delta
    diff = p_N - p_C
    a = diff @ diff
    b = 2 * p_C @ diff
    c = p_C @ p_C - Delta**2
    
    discriminant = b**2 - 4*a*c
    if discriminant < 0:
        return p_C
    
    tau = (-b + np.sqrt(discriminant)) / (2*a)
    tau = np.clip(tau, 0, 1)
    
    return p_C + tau * diff

Region of Attraction Analysis

Trust regions implicitly define regions of attraction through adaptive step sizes.

graph TD
    subgraph TwoD[2D Phase Space]
        A[Equilibrium x star]
        B[Level Set: rho equals 0.75]
        C[Level Set: rho equals 0.5]
        D[Level Set: rho equals 0.25]
        E[Boundary: rho equals 0.1]
        
        B --> A
        C --> B
        D --> C
        E -.poor model.-> F[Rejected Steps]
        
        G[Initial State x_0] --> C
        H[Safe x_1] --> B
        I[Risky x_2] --> D
        J[Outside x_3] --> F
    end
    
    style A fill:#32CD32,stroke:#228B22,stroke-width:4px
    style B fill:#98FB98,stroke:#228B22,stroke-width:2px
    style C fill:#F0E68C,stroke:#DAA520,stroke-width:2px
    style D fill:#FFB6C1,stroke:#DC143C,stroke-width:2px
    style F fill:#FF6347,stroke:#8B0000,stroke-width:2px

Loading

Caption: Implicit attraction regions defined by rho contours. Alt text: Graph showing equilibrium with concentric level sets, green center/inner, yellow middle, pink outer/rejected.

Key Properties:

• Inner region (rho greater than 0.75): Rapid convergence with expansion
• Middle region (0.25 less than rho less than 0.75): Steady progress
• Outer region (rho less than 0.25): Model unreliable, contract trust
• Boundary (rho equals 0.1): Acceptance threshold, adaptive gate

Riemannian Trust Regions

For manifold optimization, trust regions use geodesic distances instead of Euclidean norms.

graph LR
    subgraph Euclidean[Euclidean Space]
        E1[Linear Step] --> E2[norm p equals sqrt p transpose p]
    end
    
    subgraph Riemannian[Riemannian Space]
        R1[Geodesic Step] --> R2[norm p M equals sqrt p transpose M p]
    end
    
    E2 -.generalize.-> R2
    
    style E1 fill:#e1f5ff,stroke:#01579b
    style R1 fill:#fff4e1,stroke:#ef6c00

Loading

Caption: Extension from Euclidean to Riemannian geometry. Alt text: Two subgraphs showing linear vs geodesic steps, blue Euclidean, amber Riemannian.

Compitum Integration:
Trust regions in Compitum use SPD metric M for geodesic distances: norm p_M equals sqrt(p transpose M p), ensuring steps respect manifold geometry. This couples naturally with metric updates in metric.py.

---

Additional Resources

Related Documentation

• Configuration: Setting eta, gamma, Delta in YAML
• Design-Notes: Trust region integration with SRMF
• Output-Format: rho and Delta tracking schema
• Cookbook: Complete example loops with visualizations
• Glossary: Definitions for trust radius, quality ratio, subproblem

External References

Foundational Papers:

• Marquardt (1963): "An Algorithm for Least-Squares Estimation of Nonlinear Parameters"
• Moré (1978): "The Levenberg-Marquardt Algorithm: Implementation and Theory"
• Moré and Sorensen (1983): "Computing a Trust Region Step"
• Powell (1970): "A New Algorithm for Unconstrained Optimization"

Comprehensive Texts:

• Conn, Gould, and Toint (2000): Trust Region Methods
• Nocedal and Wright (2006): Numerical Optimization (Chapter 4)
• Yuan and Sun (2006): Optimization Theory and Methods

Implementation Guides:

• SciPy optimize.minimize: https://docs.scipy.org/doc/scipy/reference/optimize.html
• Manopt (Manifold Optimization): https://www.manopt.org/
• PyManopt: https://pymanopt.org/

Community and Support

• Discussions: https://github.com/PaulTiffany/compitum/discussions
• Issues: https://github.com/PaulTiffany/compitum/issues
• Wiki: https://github.com/PaulTiffany/compitum/wiki
• Examples: https://github.com/PaulTiffany/compitum/tree/main/examples

---

Frequently Asked Questions

Q: How do I choose the right initial trust radius Delta_0?

A: Selection strategy by problem type:

graph TD
    START{Problem Type?} --> WELLCOND{Well-Conditioned?}
    START --> ILLCOND{Ill-Conditioned?}
    START --> UNKNOWN{Unknown?}
    
    WELLCOND --> W1[Delta_0 equals 1.0]
    W1 --> W2[Gradient scale is uniform]
    
    ILLCOND --> I1[Delta_0 equals 0.1 to 0.5]
    I1 --> I2[Conservative start]
    
    UNKNOWN --> U1[Delta_0 equals norm gradient inverse]
    U1 --> U2[Adaptive to scale]
    
    W2 --> VERIFY{Monitor first 10 steps}
    I2 --> VERIFY
    U2 --> VERIFY
    
    VERIFY -->|Good rho distribution| DONE[Keep Delta_0]
    VERIFY -->|Poor rho distribution| ADJUST[Scale by 2x or 0.5x]
    ADJUST --> VERIFY
    
    style DONE fill:#e1ffe1,stroke:#1b5e20
    style ADJUST fill:#fff4e1,stroke:#ef6c00

Loading

Rules of thumb:

• Well-scaled problems: Delta_0 equals 1.0
• Ill-conditioned: Delta_0 equals 0.1
• Unknown scaling: Delta_0 equals 1 over norm(gradient)

Q: What if rho is consistently negative?

A: Negative rho indicates the model is worse than staying put. Causes and fixes:

Cause	Fix
Stale Hessian	Update B every 3-5 iterations
Poor gradient	Check gradient accuracy with finite differences
Wrong norm	Match norm to parameter space geometry
Nonlinearity	Reduce Delta_0, use more conservative steps

Diagnostic code:

Open on GitHub | Open in nbviewer | Launch in Binder

Snippet from Math-Trust-Regions-and-Optimization.md

def diagnose_negative_rho(g, B, Delta, f, x):
    """Check common causes of negative rho."""
    # Test gradient accuracy
    grad_error = check_gradient(f, x, g)
    print(f"Gradient error: {grad_error:.2e}")
    
    # Test Hessian conditioning
    eigvals = np.linalg.eigvalsh(B)
    cond = eigvals.max() / eigvals.min()
    print(f"Hessian condition number: {cond:.2e}")
    
    # Suggest fixes
    if grad_error > 1e-6:
        print("Fix: Improve gradient computation")
    if cond > 1e8:
        print("Fix: Add regularization: B + lambda*I")
    if Delta > 1.0:
        print("Fix: Reduce initial Delta_0")

Q: How does trust region compare to line search?

A: Trade-off comparison:

graph LR
    subgraph TrustRegion[Trust Region]
        TR1[Model-based] --> TR2[Adapt radius Delta]
        TR2 --> TR3[Robust to non-convexity]
        TR3 --> TR4[More complex subproblem]
    end
    
    subgraph LineSearch[Line Search]
        LS1[Direction-based] --> LS2[Adapt step size alpha]
        LS2 --> LS3[Simple direction choice]
        LS3 --> LS4[Many function evaluations]
    end
    
    TR4 -.versus.-> LS4
    
    style TR1 fill:#e1ffe1,stroke:#1b5e20
    style LS1 fill:#e1f5ff,stroke:#01579b

Loading

When to use:

• Trust Region: Non-convex problems, expensive gradients, need robustness
• Line Search: Convex problems, cheap function evaluations, simple implementation

Q: Can I use trust regions with stochastic gradients?

A: Yes, with modifications:

Challenges:

• Noisy gradients reduce model accuracy
• rho becomes unreliable indicator

Solutions:

1. Batch averaging: Use mini-batches to reduce gradient variance
2. EMA smoothing: Track smoothed rho: rho_bar equals lambda rho plus (1 minus lambda) rho_bar
3. Conservative thresholds: Lower eta to 0.05 for more lenient acceptance
4. Larger radii: Increase Delta_0 to absorb noise

Example:

Open on GitHub | Open in nbviewer | Launch in Binder

Snippet from Math-Trust-Regions-and-Optimization.md

def stochastic_trust_step(g_noisy, B, Delta, ema_alpha=0.2):
    """Trust region with noisy gradients."""
    # Smooth gradient over mini-batch
    g_smooth = np.mean(g_noisy_batch, axis=0)
    
    # Standard trust step
    p, rho, Delta_new = trust_step(g_smooth, B, Delta, eta1=0.05)
    
    # EMA smoothing of rho
    rho_ema = ema_alpha * rho + (1 - ema_alpha) * rho_ema_prev
    
    return p, rho_ema, Delta_new

---

Last Updated: November 10, 2025 · Compitum v1.0 · Open to Contributions