Trust-region method

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 2610.19734 §4 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 2610.19734 §4.1 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 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 2610.19734 §4 2610.19734 app. A. The paper reports about four Hebden iterations on average in practice 2610.19734 app. A.

Card: Pose of a 3-D object from point and line matches.

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 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 2412.20350 §4 2412.20350 alg. 1. The latent space comes from PCA or from an isometric autoencoder 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 2412.20350 §4.2 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 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 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 α 2412.20350 §4.1 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 2412.20350 eq. 4 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 2412.20350 app. A.3 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.

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 2610.19734 §2 2610.19734 §5. The conclusions below are limited to that setting and to the authors' own numbers.

Implementation sketch

Language-agnostic pseudocode of the common core, following the steps of 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.

# 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 2412.20350 alg. 2:

# 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 2610.19734 §4 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 2610.19734 app. A. It is also not stated whether Hebden's search shifts the already-shifted Hessian or the raw one 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 2610.19734 eq. 28.
• Initial radius and start pose. Neither is given 2610.19734 §4.1.
• Stop tolerances. They are called small positive numbers, with no values given 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 2610.19734 §4.1. The Bayesian-optimisation paper changes its box from success and failure counts and uses no ratio 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 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: 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: runs a trust-region box with success and failure counts inside a safe Thompson-sampling search over controller parameters.