Trust Region Methods

Trust region methods are a class of optimization algorithms that construct and minimize a model function within a restricted region around the current iterate, where the model is considered to be a good approximation of the objective function.

Principle

Unlike line search methods that first determine a direction and then find an appropriate step size, trust region methods:

1. Define a region around the current point within which a model (usually quadratic) is trusted to be an adequate representation of the objective function
2. Find the step that minimizes the model within this region
3. Update the size of the trust region based on how well the model predicts the actual function behavior

Mathematical Formulation

At each iteration $k$, trust region methods solve the subproblem:

\begin{align} \min_{\Delta \theta} \quad & m_k(\Delta \theta) \ \text{subject to} \quad & |\Delta \theta| \leq \Delta_k \end{align}

where:

• $\Delta \theta$ is the step from the current point ${\theta }_k$
• $m_k(\Delta \theta )$ is the model function at iteration $k$
• ${\Delta }_k$ is the trust region radius
• $|\cdot |$ is a norm (typically Euclidean or weighted Euclidean)

Model Function

The model function is typically a quadratic approximation of the objective function $L(\theta )$ around the current point ${\theta }_k$:

$m_k(\Delta \theta )=L({\theta }_k)+\nabla L({\theta }_k{)}^T\Delta \theta +\frac{1}{2}\Delta {\theta }^T{B}_k\Delta \theta$

where:

• $\nabla L({\theta }_k)$ is the gradient at ${\theta }_k$
• $B_k$ is an approximation to the Hessian matrix ${\nabla }^{2}L({\theta }_k)$

Trust Region Algorithm

Basic Algorithm

1. Initialize ${\theta }_0$, ${\Delta }_0>0$, and parameters $0<{\eta }_1<{\eta }_2<1$, $0<{\gamma }_1<1<{\gamma }_2$
2. For iteration $k=0,1,2,\dots$:
   • Construct the model $m_k(\Delta \theta )$
   • Solve the trust region subproblem to find $\Delta {\theta }_k$
   • Compute the actual reduction: $\text{ared}_k = L(\theta