# Trust-Region Algorithm

The Trust-Region (TR) algorithms are relatively new iterative methods for solving nonlinear optimization problems. They are widely used in power engineering, finance, applied mathematics, physics, computer science, economics, sociology, biology, medicine, mechanical engineering, chemistry, and other areas. The TR methods have global convergence and local super convergence, which differentiates them from line search methods and Newton methods. The TR methods have better convergence when compared with widely-used Newton-like methods.

The main idea behind a TR algorithm is calculating a trial step and checking if the next values of `х+` belong to the trust region [Conn00]. Calculation of the trial step is strongly associated with the approximation model.

If the nonlinear least squares problem is defined as

then the trial step is a solution of the following subproblem:

This operation is an approximation to the objective function in a neighborhood of the current point x.

Consider a TR algorithm with linear (bound) constraints :

The first-order necessary condition for the vector to be minimized with this constraint is

where D is the diagonal scaling matrix

with

for i = 1, ..., n.

Provided `Ω ={x ∈ Rn: l ≤ x ≤ u} ⊂` Rn, write `int(Ω)` for the strictly nonempty interior of `Ω`. At each iteration, the basic structure of the method involves solving an elliptical trust-region subproblem and computing a search step to update the current iteration.

Provided `xi ∈ int(Ω)` and the trust region size Δk > 0, consider the elliptical trust-region subproblem

Let ptr(Δk) and pc(Δk) be a solution and a Cauchy point of the above trust-region subproblem respectively [Conn00]. The following linear combination of two vectors ptr(Δk) and pc(Δk) defines the search step (trial step) used in the algorithm, that is,

A good agreement between the model function mk and the objective function f is ensured for the following standard condition:

with the given constant β2 ∈ (0,1). If this condition is not met, reject p(Δk), and the trust-region size Δk is successively reduced so that p(Δk) satisfies the accuracy requirement.

Parent topic: Optimization Solvers Basics