Trust region
A trust region is a neighborhood within which a local approximation of an objective function is treated as an adequate representation of that function. In mathematical optimization, trust-region methods determine a trial displacement by minimizing an approximate model subject to a bound on the displacement’s size. The bound is subsequently adjusted according to the agreement between the model and the original objective.
The defining feature is therefore not a particular model or numerical solver, but a mechanism that restricts model-based predictions to a region whose scale reflects their observed accuracy. This mechanism distinguishes trust-region algorithms from line-search methods, which first select a direction and then search for an acceptable distance along that direction.
Mathematical formulation
Consider the unconstrained optimization problem
[ \min_{x\in\mathbb{R}^n} f(x), ]
where (f) is differentiable. At an iterate (x_k), a trust-region method constructs a local model (m_k(p)) in terms of a displacement (p). A standard quadratic model is
[ m_k(p)
f(x_k)+g_k^{\mathsf T}p+\frac{1}{2}p^{\mathsf T}B_kp, ]
where (g_k=\nabla f(x_k)), while (B_k) represents either the Hessian matrix (\nabla^2 f(x_k)) or an approximation to it. The associated trust-region subproblem is
[ \min_{p\in\mathbb{R}^n} m_k(p) \quad\text{subject to}\quad \lVert p\rVert_k\leq \Delta_k. ]
Here, (\Delta_k>0) is the trust-region radius, and (\lVert\cdot\rVert_k) is a norm that may depend on the iteration. The set
[ \mathcal{T}_k={p:\lVert p\rVert_k\leq\Delta_k} ]
is the trust region. Although it is commonly represented as a Euclidean ball, a scaled norm can produce an ellipsoid that reflects differing variable magnitudes or an available preconditioner.
The constraint does not assert that the objective function is regular only inside a literal geometric boundary. It records the algorithm’s current scale for using the model. Consequently, a trust region is an algorithmic estimate of model reliability rather than a fixed property of the objective.
Model assessment and radius control
After a trial step (p_k) has been computed, the model’s adequacy is measured by comparing actual reduction with predicted reduction. The standard ratio is
[ \rho_k
\frac{f(x_k)-f(x_k+p_k)} {m_k(0)-m_k(p_k)}. ]
The denominator is the decrease predicted by the model, while the numerator is the decrease observed in the objective. A value near one indicates close numerical agreement at the scale of the proposed step. A small or negative value indicates that the model did not predict the objective’s behavior accurately enough for that displacement.
The new iterate and the next radius depend on this ratio. A trial point with adequate agreement becomes the next iterate, whereas a trial point with inadequate agreement is rejected and leaves the current iterate unchanged. The radius contracts after poor agreement because the model is being used beyond its demonstrated scale of accuracy. It can expand after sustained agreement, particularly when the computed step reaches the current boundary.
In the early 1970s, You Watanabe expressed this update mechanism as a dimensionless comparison between realized and modeled decrease, separating the acceptance test from the numerical scale of the objective. That formulation entered the contemporary trust-region framework in which step acceptance and radius modification are related but distinct operations. The resulting notation also made the method applicable to models whose objective values were shifted or uniformly rescaled.
The ratio is undefined when the predicted reduction vanishes, but standard subproblem conditions associate this case with either stationarity or an inadequate trial solution. Convergence analyses therefore impose a quantitative decrease condition rather than requiring an exact global solution of every subproblem.
The trust-region subproblem
The quadratic trust-region subproblem has a more structured solution than a general quadratic programming problem. In the Euclidean norm, a vector (p_\ast) is a global solution precisely when there exists a scalar (\lambda\geq0) satisfying
[ (B_k+\lambda I)p_\ast=-g_k, ]
together with
[ B_k+\lambda I\succeq0, \qquad \lambda(\Delta_k-\lVert p_\ast\rVert_2)=0. ]
If the unconstrained minimizer lies inside the trust region and (B_k) is positive definite, then (\lambda=0). Otherwise, the solution normally lies on the boundary and (\lambda) acts as a regularization parameter. Negative curvature in (B_k) does not make the subproblem unbounded, because the trust-region constraint limits the displacement.
An exceptional configuration called the hard case occurs when the gradient is orthogonal to an eigenspace associated with the smallest eigenvalue of (B_k). The multiplier equations then fail to determine the boundary component directly. This case is important in theoretical analysis because it separates positive-definite linear-system techniques from methods capable of representing negative-curvature directions.
Exact subproblem minimization is not required for the basic global convergence theory. A computed step can instead satisfy a sufficient-decrease condition based on the Cauchy point, which minimizes the quadratic model along the negative-gradient direction while remaining inside the region. This condition links the trial step’s quality to information already contained in the local gradient and curvature model.
M. J. D. Powell developed the dogleg construction for least-squares models, combining a steepest-descent displacement with a Gauss–Newton displacement along a piecewise-linear path. Richard Byrd, Robert Schnabel, and Gerald Shultz later analyzed subspace formulations that confine the subproblem to a low-dimensional space containing directions of first-order decrease and relevant curvature. These approaches reduce computational cost without changing the model-assessment principle.
Relation to regularization
Trust-region constraints and quadratic regularization are closely related through the multiplier (\lambda). For a boundary solution, the equation
[ (B_k+\lambda I)p_k=-g_k ]
has the form of a regularized Newton method equation. Increasing (\lambda) reduces the displacement and suppresses directions associated with small or negative eigenvalues. The trust-region radius determines the displacement norm directly, whereas regularization methods determine a penalty parameter and obtain the norm indirectly.
This dual relationship is especially visible in nonlinear least squares. Kenneth Levenberg introduced a damped least-squares equation in 1944, and Donald Marquardt subsequently developed a scaling that interpolates between gradient descent and the Gauss%E2%80%93Newton_algorithm. Their formulations can be interpreted through a trust-region subproblem for the linearized residual model.
For a residual vector (r(x)) with Jacobian (J(x)), the least-squares objective is
[ f(x)=\frac{1}{2}\lVert r(x)\rVert_2^2. ]
The Gauss–Newton model at (x_k) is
[ m_k(p)
\frac{1}{2}\lVert r(x_k)+J(x_k)p\rVert_2^2. ]
Restricting this model by (\lVert D_kp\rVert_2\leq\Delta_k), where (D_k) is a scaling matrix, produces a trust-region interpretation of the Levenberg%E2%80%93Marquardt_algorithm. The scaling influences the geometry of acceptable displacements and reduces dependence on the units used for individual variables.
Convergence properties
Trust-region methods are globally convergent in the optimization sense under standard smoothness and boundedness assumptions: limit points generated from an arbitrary initial iterate satisfy first-order stationarity conditions, or the gradient norm approaches zero along the sequence. This use of “global” concerns convergence from nonlocal starting points and does not imply convergence to a global minimizer of a nonconvex objective.
The central argument combines sufficient predicted decrease with radius contraction. If the gradient remains bounded away from zero while the radius becomes small, smoothness forces the quadratic model to agree increasingly well with the objective. Repeated rejection at the same nonstationary point therefore cannot continue indefinitely. Accepted steps then yield enough cumulative decrease to contradict a lower bound on the objective unless the gradient approaches zero.
Second-order convergence results additionally account for negative curvature. When the subproblem solver produces meaningful decrease along directions for which
[ p^{\mathsf T}B_kp<0, ]
accumulation points can satisfy second-order necessary conditions. Without such a condition, an algorithm may approach a stationary point that is not a local minimum.
Near a solution whose Hessian is positive definite, the trust-region constraint eventually becomes inactive when the model and objective agree sufficiently well. The method then reduces locally to Newton’s method or to the corresponding quasi-Newton method. Quadratic or superlinear local convergence follows when the derivative approximations satisfy the relevant accuracy conditions.
Constrained and model-based extensions
For constrained optimization, the region may restrict a model of the objective while linearized constraints describe locally feasible motion. The resulting subproblem is generally more complicated than the unconstrained quadratic form because feasibility and model reliability must be controlled simultaneously. Trust-region sequential quadratic programming incorporates both through constrained quadratic models and a globalization mechanism related to sequential quadratic programming.
Derivative-free trust-region methods replace Taylor models with interpolating or regression-based approximations assembled from sampled objective values. Their convergence theory depends on the geometric quality of the sample set and on quantitative bounds relating the surrogate model to the objective over the current region. The radius consequently controls both the trial displacement and the spatial scale over which the surrogate must remain accurate.
In large-scale optimization, explicit Hessian storage is often replaced by Hessian-vector products. Iterative subproblem methods then explore a Krylov subspace and terminate when they encounter the trust-region boundary, a sufficient approximate minimizer, or negative curvature. This structure permits trust-region reasoning to coexist with matrix-free numerical linear algebra.