Trust Region Methods

Saddle point pose a particular challenge in non-linear optimisation, particularly in higher dimensions. The plots below show two examples of saddle points in two dimensions. Like local minima and maxima, these are stationary points where the gradient of the function is zero $\nabla f = 0$, but where the value of the function rises along certain directions and reduces along others (left plot). An alternative type of saddle point arises when the hessian is singular, and are characterised by a plateau around the stationary point, like the monkey saddle depicted in the plot to the right.

Near the location of the critical point, the function $f$ can be restated using the quadratic form like so (see also Pascanu, Dauphin and Ganguli 2014):

where $\lambda_i$ is the $i$th eigenvalue of the Hessian, and $\nabla \mathbf{v}_i$ is the motion of $\delta \mathbf{\theta}$ along the $i$th eigenvector of the Hessian. If the $i$th eigenvalue is negative/positive then along the $i$th eigenvector the function $f$ will achieve a maximum/minimum at $\mathbf{\theta}^\star$.

Gradient descent algorithms will move away or towards $\mathbf{\theta}^\star$ with a step given by $-\lambda_i \delta \mathbf{v}_i$. So for negative eigenvalues the motion will be towards lower values of $f$ away from $\mathbf{\theta}^\star$. For positive eigenvalues the motion will be towards lower values of $f$ towards $\mathbf{\theta}^\star$. The problem here is the size of the step, which is very small for small values of $\lambda_i$.

Newton methods rescale the step size by $\lambda_i$ so that it becomes $-\delta \mathbf{v}_i$. For negative eigenvalues, this has the undesirable characteristic that these methods move towards increasing values of $f$ (i.e. towards the critical point) along corresponding eigenvectors. Since for positive eigenvalues it is also moving towards the critical point, this means that saddle points act as attractors for these types of methods.

Trust region methods restate the optimisation problem as a sequence of optimisations of a second order approximation to $f$ in a local trust-region surrounding the current point $a_k$. The exact solution to each of these subproblems can be shown to be $(\nabla^2 f(a_k) + \lambda_t I)^{-1} \nabla f(a_k)$, where the value of $\lambda_t$ is related to the size of the trust region. In comparison with the previous methods above, this is equivilent to moving with a step given by $-\frac{\lambda_i}{\lambda_i + \lambda_t}\delta \mathbf{v}_i$. As long as $\lambda_t$ is chosen to be larger than the most negative eigenvalue then the direction of each step is now always towards more negative values of $f$. As long as $\lambda_t$ is small compared with $\lambda_i$ then we avoid the small step sizes associated with gradient descent.

Like many line search methods, trust region methods also use the second order Taylor expansion of $f$ around $a_k$

where $g_k = \nabla f(a_k)$, $B_k$ is an approximation to the hessian matrix $B_k \approx \nabla^2 f(a_k)$ or the hessian itself $B_k = \nabla^2 f(a_k)$. Trust region methods aim to find the $p$ that minimises $m_k$ in a local trust region $||p|| < \Delta_k$ around the current point $a_k$, where $\Delta_k$ is the trust region radius.

Solving the minimisation given above is normally done approximately, with different trust region methods varying how the approximation is achieved. Choosing the trust-region radius is fundamental to this class of methods, and is done by comparing the actual to the predicted reduction in the function value

Since $m_k(0) - m_k(p_k)$ is always positive, if $\rho_k$ is negative then the actual function value is increasing, the step is rejected and the trust region radius $\Delta_k$ is decreased in order to improve the approximate model $m_k$. If $\rho_k$ is positive but much smaller than one then we do not alter $\Delta_k$. If $\rho_k$ is close to or greater than 1 we can be confident in our model and thus increase $\Delta_k$. The general algorithm for a trust region method (reproduced from the text by Nocedal and Wright cited below) is:

Given $a_0$, $\hat{\Delta} > 0$, $\Delta_0 \in (0, \hat{\Delta})$, and $\nu \in [0, \frac{1}{4})$:

for $k = 0, 1, 2, ...$

end for.

We will describe two algorithms for minimising $m_k(p)$, the Cauchy point and the dogleg methods. The Cauchy point first solves a linear version of $m_k$ defined as

Subsequently, $p^s_k$ is used to find the scalar $\tau_k > 0$ such that

Finally, the Cauchy point is given as $p_k^C = \tau_k p_k^s$.

The solution to this problem can be shown to be

where

The second method we describe is the dogleg method, which is applicable when $B_k$ is a positive definite matrix. If the original hessian is positive definite then this method is directly applicable, or one of the quasi-Newton positive definite approximation to the hessian could also be used. The dogleg method is derived by considering the path of the $p$ that minimises $m_k(p)$ with increasing $\Delta_k$, which forms a curved path in parameter space. The method approximates this path with two straight line segments. The first segment follows the steepest descent direction and is given by

The second step is along the path between $p_k^U$ and $p^B_k = -B_k^{-1} g_k$. In the case where $p_k^B$ is inside the trust region $||p_k^B|| \le \Delta_k$ then $p_k^B$ can be used without modification. Otherwise the point of intersection with the trust-region radius must be calculated, which can be done by solving the following quadratic equation

with the second segment being defined by