---
kind: concept
slug: trust-region-method
title: Trust-region method
summary: >-
  Minimise a function, or search a black-box space safely, by trusting a local model only inside a region around the current guess. Two variants: a Gauss-Newton pose solver that sets its radius from the predicted-versus-actual decrease, and a safe Bayesian-optimisation box that grows or shrinks from success counts. Trade-offs: an extra subproblem solve per try, or many unstated constants.
tags: [optimization, nonlinear-least-squares, trust-region, safe-exploration]
papers: ["2412.20350", "2610.19734"]
related: [perspective-n-point, dual-quaternion, unit-quaternion-rotation, bayesian-optimization, gaussian-process, thompson-sampling]
status: draft
updated_at: 2026-10-25
---

## Overview

A local model of a nonlinear function is only accurate near the current guess.
A trust-region method therefore limits each step to a ball of radius δ around
that guess. It solves for the best step inside the ball, compares the decrease
the model predicted with the decrease the function actually gave, and then
decides whether to accept the step and how to set the next radius
[arxiv:2610.19734 §4] [arxiv:2610.19734 §4.1].

Many variants share one acceptance test: the ratio ρ of actual to predicted
reduction. A step is accepted when ρ reaches a threshold, and the radius doubles
when the model agrees closely with the function. A step with a poor ratio is
rejected, and the radius is halved and the step recomputed
[arxiv:2610.19734 §4.1] [arxiv:2610.19734 eq. 28]. The variants differ in the
model they use, in how the step inside the region is found, and in how the
region's size is set. The safe Bayesian-optimisation variant below does not use
a ratio. It counts successes and failures instead [arxiv:2412.20350 §4.2].

## Variants

### Gauss-Newton model with a shifted Hessian

For a sum of squared residuals, the paper uses the gradient `Jᵀ Φ` and the
Gauss-Newton Hessian `JᵀJ`, which drops the second-order term. It adds a small
shift α = 0.001 to the Hessian and first solves the unconstrained system. If
that step lies inside the radius, it is used. Otherwise the step is taken on
the boundary, found by Hebden's search, which increases a shift μ until the
step length matches the radius [arxiv:2610.19734 §4] [arxiv:2610.19734 app. A].
The paper reports about four Hebden iterations on average in practice
[arxiv:2610.19734 app. A].

Card: [Pose of a 3-D object from point and line matches](/papers/2610.19734).

The paper contrasts this with Levenberg-Marquardt, which it says is poorly
conditioned when its damping term is near zero, and with Newton's method, which
it says can increase the error [arxiv:2610.19734 §4.2]. Those two methods have
no card here, so this page does not describe them further.

### Safe Bayesian optimisation with a box and success counts

Here the trust region is a box with side length l around the incumbent, the
best safe point found so far, in a low-dimensional latent space. Candidate
points inside the box are kept only if an optimistic safety bound passes a
threshold, and a Thompson sample of the objective picks the next trial
[arxiv:2412.20350 §4] [arxiv:2412.20350 alg. 1]. The latent space comes from
PCA or from an isometric autoencoder [arxiv:2412.20350 §4.3].

The box is not resized from a ratio. A trial is a success when it is safe and
improves the incumbent, and any other trial is a failure. After a set number of
successes the side length doubles, up to a maximum. After a set number of
failures it halves, down to a minimum. When it reaches that minimum it restarts
at an initial length, and all past samples are kept [arxiv:2412.20350 §4.2]
[arxiv:2412.20350 alg. 2].

The paper's evidence is an author-reported comparison on 1000-dimensional
synthetic functions, with 500 evaluations and 100 runs. The objective is 3.96
for this method against 3.07 for the best baseline, LineBO, and cumulative
violation is 27.42 against 36.59 [arxiv:2412.20350 tab. 1]. The paper does not
isolate the trust region in that table. Its ablation says that removing the
local search makes the method over-explore, but that ablation is shown only as a
figure [arxiv:2412.20350 app. C.2] [fig. 6].

Pitfalls specific to this variant:

- **Constants are not stated.** The paper gives no values for the success and
  failure counts, the side-length bounds or the initial length [arxiv:2412.20350
  app. B.3].
- **The safety level is unstated.** The one-step bound needs Φ(β) ≤ 1 − α. With
  the paper's β = 2 this holds only for α up to about 0.023, and the paper never
  states α [arxiv:2412.20350 §4.1] [arxiv:2412.20350 eq. 3].
- **The bound uses a finite domain.** The cumulative violation bound uses the
  size of the domain, but the domain is continuous and the proof does not
  discuss discretisation [arxiv:2412.20350 eq. 4] [arxiv:2412.20350 app. A.2].
- **Embedding error.** The isometry result needs exact distance preservation.
  The autoencoder used for the neural task reaches a distance correlation of
  0.9729, so the guarantee does not strictly apply there [arxiv:2412.20350 app. A.3]
  [arxiv:2412.20350 tab. 4].
- **Released code.** One reading of the released code, recorded on the paper's
  card and not run, is that the success test never fires, so the box only
  shrinks and restarts. Check that before reusing the code.

Card: [Safe Bayesian Optimization for the Control of High-Dimensional Embodied Systems](/papers/2412.20350).

## When to use which

The source card evaluates one application: pose from point and line
correspondences, with 6 to 8 unknowns, depending on the error function
[arxiv:2610.19734 §2] [arxiv:2610.19734 §5]. The conclusions below are limited
to that setting and to the authors' own numbers.

| Situation | Use | Why |
|---|---|---|
| Residuals are small at the solution | Gauss-Newton model with the shift above | The paper drops the second-order term, which it says is justified only when residuals are small [arxiv:2610.19734 §4.2]. |
| Residuals are large, for example heavy image noise or wrong matches | Consider a safeguarded Moré-Sorensen step; test it first | The paper suggests this for large residuals, but no experiment in the card uses it [arxiv:2610.19734 §4.2]. |
| Noisy image points, and a closed-form linear estimate is unreliable | This method, if the residual model fits the problem | At 100 points and noise 1.00, the author-reported translation error is 0.0002 cm against 11.4770 cm for the linear method [arxiv:2610.19734 tab. 2] [arxiv:2610.19734 tab. 8]. |
| Tight time budget with large point sets | Line-based, rotation first, where the data allows | Reported CPU time is 0.03 s for 30 lines and 0.67 s for 230 lines [arxiv:2610.19734 tab. 3] [arxiv:2610.19734 tab. 5]. The joint point variant takes 4.83 s at 460 points [arxiv:2610.19734 tab. 7]. Timings were measured on 1990s hardware and differ in data size, so use them for rough ratios only [arxiv:2610.19734 tab. 3]. |
| Black-box controller with hundreds to thousands of parameters, a safety signal on every trial, and a few hundred trials | Safe Bayesian optimisation with a box and success counts | Author-reported objective 3.96 against 3.07 for the best baseline on 1000-D synthetic functions [arxiv:2412.20350 tab. 1]. The guarantee needs a safety level the paper does not state [arxiv:2412.20350 §4.1]. |
| Low-dimensional tuning under a safety constraint | A conservative safe method such as SafeOpt, not this box | The paper says SafeOpt may struggle to expand its safe region beyond about 10 parameters [arxiv:2412.20350 §1]. That is the paper's claim, not tested here. |

## Implementation sketch

Language-agnostic pseudocode of the common core, following the steps of
[arxiv:2610.19734 §4.1]. The paper's values are a threshold of 0.25 for
accepting a step, 0.75 for doubling the radius, and α = 0.001.

```pseudocode
# Trust-region loop with a shifted Gauss-Newton step  [arxiv:2610.19734 §4.1]
# residual(x) returns the vector Phi(x); jacobian(x) returns its derivatives
def trust_region(x, radius, residual, jacobian, eta, big, alpha):
    while not converged(x):
        # Objective, gradient and Gauss-Newton Hessian  [arxiv:2610.19734 eq. 23-25]
        phi = residual(x)
        J = jacobian(x)
        g = J.T @ phi
        H = J.T @ J
        while True:
            # Shifted model; use a constrained step if it leaves the ball  [§4]
            step = solve(H + alpha * I, -g)
            if norm(step) >= radius:
                step = constrained_step(H + alpha * I, g, radius)  # Hebden  [app. A]
            # Ratio of actual to predicted reduction  [arxiv:2610.19734 eq. 28]
            predicted = -(g @ step + 0.5 * step @ H @ step)
            actual = 0.5 * phi @ phi - 0.5 * residual(x + step) @ residual(x + step)
            rho = actual / predicted
            # Accept when the model agrees well enough  [arxiv:2610.19734 §4.1]
            if rho >= eta:
                break
            # Otherwise shrink the ball and recompute the step  [§4.1 k.6]
            radius = radius / 2
        x = x + step
        # Model agreed closely: allow a longer step next time  [§4.1 k.5]
        if rho >= big:
            radius = 2 * radius
    return x
```

The box update of the Bayesian-optimisation variant replaces the ratio test
above. It uses the counts described in its section, and the paper's
Algorithm 2 [arxiv:2412.20350 alg. 2]:

```pseudocode
# Box update after each trial  [arxiv:2412.20350 alg. 2] [§4.2]
# Success: safe and better than the incumbent; anything else is a failure
def update_box(sample, incumbent, state, settings):
    if sample.safe and sample.value > incumbent.value:
        incumbent = sample
        state.successes += 1
        state.failures = 0
    else:
        state.successes = 0
        state.failures += 1
    # Double after enough successes, capped at the maximum length
    if state.successes == settings.success_tolerance:
        state.length = min(2 * state.length, settings.length_max)
        state.successes = 0
    # Halve after enough failures, floored at the minimum length
    elif state.failures == settings.failure_tolerance:
        state.length = max(state.length / 2, settings.length_min)
        state.failures = 0
        # At the minimum, restart at the initial length  [§4.2]
        if state.length == settings.length_min:
            state.length = settings.length_0
    return incumbent, state
```

Points where the paper leaves choices open in the Gauss-Newton variant, each
noted in the card:

- **Factor of ½.** The least-squares form carries ½ in the objective, but
  several error functions in the paper do not. The paper calls them equivalent
  [arxiv:2610.19734 §4] [arxiv:2610.19734 eq. 23]. The gradient and Hessian
  scale differ by 2, so the fixed shift α is relative to a different scale.
  Pick one convention throughout.
- **Hebden's start and tolerance.** The start value μ₀ and the stop tolerance
  are not stated [arxiv:2610.19734 app. A]. It is also not stated whether
  Hebden's search shifts the already-shifted Hessian or the raw one
  [arxiv:2610.19734 §4.1].
- **Zero denominator.** The predicted reduction can be zero at convergence, and
  the paper does not say how that case is handled [arxiv:2610.19734 eq. 28].
- **Initial radius and start pose.** Neither is given [arxiv:2610.19734 §4.1].
- **Stop tolerances.** They are called small positive numbers, with no values
  given [arxiv:2610.19734 §4.1].

## Contradictions

No numbers conflict, because the two papers solve different problems: a pose
fit and a safe search. They do use different acceptance and size rules. The pose
paper accepts or rejects a step from the ratio of actual to predicted decrease,
and changes the radius by factors of two [arxiv:2610.19734 §4.1]. The
Bayesian-optimisation paper changes its box from success and failure counts and
uses no ratio [arxiv:2412.20350 §4.2]. Neither paper compares its rule with the
other's, so this page does not rank them.

The pose paper says the final result does not depend on the initialisation
[arxiv:2610.19734 §6]. No initial pose is given and no experiment varies the
start, so that claim is untested in the paper.

## Papers

- [Pose of a 3-D object from point and line matches](/papers/2610.19734): applies a Gauss-Newton trust-region loop with Hebden's constrained step to a penalised dual-quaternion pose error.
- [Safe Bayesian Optimization for the Control of High-Dimensional Embodied Systems](/papers/2412.20350): runs a trust-region box with success and failure counts inside a safe Thompson-sampling search over controller parameters.