Trust-Region Methods
Build a local model, trust it only within a region, and expand or shrink that region based on how well the model predicted reality.
Trust the model locally
Line-search methods pick a direction, then a step length. Trust-region methods instead choose a region of radius delta around the current point in which a quadratic model is believed accurate, then find the best step within that region. If the model predicts the actual decrease well, the region grows; if not, it shrinks.
The subproblem
At each iteration solve: minimize m(p) = f + grad^T p + (1/2) p^T B p subject to ||p|| <= delta, where B is the Hessian or an approximation. This trust-region subproblem is well posed even when B is indefinite, which is a key advantage over pure Newton steps near saddle points.
Adapting the radius
Compute the ratio rho of actual reduction in f to reduction predicted by the model. If rho is close to 1 the model is trustworthy: accept the step and possibly enlarge delta. If rho is small or negative the model is poor: reject the step and shrink delta. This feedback loop makes trust-region methods robust.
Solving the subproblem
- Exact solution via the Moré-Sorensen algorithm using a scalar equation.
- Dogleg method: interpolate between the steepest-descent and Newton points.
- Steihaug-Toint truncated CG for large sparse problems.
Strengths
Trust-region methods handle nonconvex objectives and indefinite Hessians gracefully, converge globally to a stationary point, and retain fast local convergence. They are the basis of derivative-free trust-region methods and of robust nonlinear least-squares solvers like Levenberg-Marquardt, which is a trust-region method in disguise.
from scipy.optimize import minimize
res = minimize(f, x0, method='trust-ncg', jac=grad, hess=hess)Trust-region and Levenberg-Marquardt solvers robustly fit nonlinear physics models to data even when curvature estimates are unreliable.