Trust-region methods

Author: Tung-Yen Wang (tw565) (CHEME 6800, Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Trust region methods are iterative optimization techniques designed to find local minima or maxima of objective functions, particularly in nonlinear problems (NLP), by iteratively refining approximations within dynamically adjusted trust regions. Unlike line search methods, which determine the step size along a predefined direction, trust region methods concurrently optimize both the direction and the magnitude of the step within a specified neighborhood around the current iterate.

The origins of these methods date back to Levenberg, who introduced a modified version of the Gauss-Newton method for solving nonlinear least squares problems by adding a damping term to control the step size. This approach was later rediscovered and refined by Morrison and Marquardt, ultimately gaining prominence as the Levenberg-Morrison-Marquardt method . Subsequent advancements led to the development and standardization of trust region methods, further improving their robustness and application.

The central core of trust region methods lies in the idea of constructing a simplified model — often a quadratic approximation — that represents the objective function near the current point. This model serves as a surrogate, guiding the search for the optimum within a bounded region around the current estimate. The size of the trust region is dynamically adjusted based on how well the model predicts the actual behavior of the objective function. If the model is predicting accurate behavior of the objective function, the size of the trust region is increased, allowing the algorithm to explore a larger area around the current solution; the trust region is reduced if otherwise .

Algorithm Discussion

The mathematical framework involved in trust region methods starts with the construction of a local approximation of the objective function and defining a constrained region within which this model is trusted to be accurate. Consider the following local quadratic approximation of $f$ around $x_{k}$:

(1) $m_{k}(p)=f_{k}+\nabla f_{k}^{T}p+{\frac {1}{2}}p^{T}B_{k}p$

where $p$ represents the step or direction vector from the current point, $f_{k}=f(x_{k})$, $\nabla f_{k}=\nabla f(x_{k})$, and $B_{k}$ is a symmetric matrix.

The first two terms $m_{k}(p)$ are designed to match the first two terms of the Taylor series expansion of $f(x_{k}+p)$. The expression can also be written as:

$m_{k}(p)=f_{k}+\nabla f_{k}^{T}p+O(||p||^{2})$

where higher-order terms $O(||p||^{2})$ are approximated using $B_{k}$. It can also be noted that the difference between $m_{k}(p)$ and $f(x_{k}+p)$ is of order $O(||p||^{2})$, suggesting that when p is small, the approximation error is minimal.

For each iteration, seek a solution of the subproblem:

(2) $m_{k}(p)=f_{k}+\nabla f_{k}^{T}p+{\frac {1}{2}}p^{T}B_{k}p$   $s.t.||p||\leq \Delta _{k}$

where $\Delta _{k}$ represents the trust region radius and is greater than 0.

Here, $p_{k}$ represents the step taken at iteration $k$, hence the next point calculated can be denoted as $x_{k}+1=x_{k}+p$. For the moment, $||\cdot ||$ is the Euclidean norm.

To solve the subproblem, the trust region radius $k$ must be determined at each iteration.

(3) $p_{k}={\frac {f(x_{k})-f(x_{k}+p_{k})}{m_{k}(0)-m_{k}(p_{k})}}={\frac {actual\;reduction}{predicted\;reduction}}$

If $p_{k}$ is negative, the objective value $f(x_{k}+p)$ would be greater than the current value $f(x_{k})$, leading to the rejection of the step. If $p_{k}$ is positive but not close to 1, the trust region remains unchanged. If $p_{k}$ is positive but close to 0, the trust region radius $\Delta _{k}$ is reduced. On the other hand, if $p_{k}$is approximately equal to 1, the trust region radius $\Delta _{k}$ is expanded for the next point iteration [1].

Cauchy Point

Identical to line search, there is no need to compute the subproblem (2) to achieve optimal minimum as the model improves itself with each iteration, meaning that as long as the step lies in the trust region and provides sufficient reduction, the algorithm can converge to the best solution. This sufficient reduction can be expressed as the Cauchy Point, that is:

(4) $p_{k}^{C}=-\tau _{k}{\frac {\Delta _{k}}{||\nabla f_{k}||}}$

where

$\tau _{k}={\begin{cases}1,&{\text{if }}\nabla f_{k}^{T}B_{k}\nabla f_{k}\leq 0\\min({\frac {||\nabla f_{k}||^{3}}{\Delta _{k}\nabla f_{k}^{T}B_{k}\nabla f_{k}}},1),&{\text{if otherwise}}\end{cases}}$

Computations often start with this as it is simple to calculate. To achieve better performance, however, it is necessary to integrate information about $B_{k}$ to refine $p_{k}$. Consider the following:

$p_{B}=-B_{k}^{-1}\nabla f_{k}$

as the full Newton step where $||p_{k}||\leq \Delta _{k}$.

The Dogleg Method

The full Newton step, however, is not feasible when the trust region constraint is active. To handle such cases, the Dogleg method is used to approximate the subproblem (2). This method finds a solution that considers two line segments. The first line is the steepest descent direction:

$p^{U}=-{\frac {g^{T}g}{g^{T}B_{g}}}g$

where $g=\nabla f(x_{k})$.

The second line runs from $p^{U}$ to $p^{B}$ for $\tau \in [0,2]$:

$p(\tau )={\begin{cases}\tau p^{U}&0\leq \tau \leq 1\\p^{U}+(\tau -1)(p^{B}-p^{U})&1\leq \tau \leq 2\end{cases}}$

where $p^{B}=-B^{-1}f(x_{k})$.

The method works well when $B_{k}$ is positive definite. However, when $B_{k}$ is not convex, $p_{B}$ cannot guaranteed to be a meaningful solution since the method is not well-suited to handle negative $B_{k}$.

The Conjugated Gradient Steihaug’s Method

In contrast to the methods above, Steihaug’s method is designed to better handle large-scale trust region subproblems. It mitigates the limitations of slower convergence and the need for a positive definite Hessian. In addition, it handles negative curvature by enabling early termination when such directions are detected or when the trust region boundary is reached. These features make the method more scalable and robust, suited for large-scale or poorly conditioned optimization problems . The method is described as follows:

given $\varepsilon >0$

set $p_{0}=0,r_{0}=g,d_{0}=-g,j=0$;

if $||r_{0}||<\varepsilon$

return $p_{0}=p_{j}$;

for all $j$,

if $d_{j}^{T}Bd_{j}\leq 0$

determine $\tau$ such that $p=p_{j}+\tau d_{j}$ minimizes (2) and satisfies $||p||=\Delta$

return $p$;

set $\alpha _{j}={\frac {r_{j}^{T}r_{j}}{d_{j}^{T}Bd_{j}}}$;

set $p_{j+1}=\alpha _{j}d_{j}$;

if $||p_{j+1}||\geq \Delta$;

determine the positive value of $\tau$ such that $p=p_{j}+\tau d_{j}$ and satisfies $||p||=\Delta$

return $p$;

set $r_{j+1}=r_{j}+\alpha _{j}Bd_{j}$;

if $||r_{j+1}||\leq \varepsilon$

return $p=p_{j+1}$;

set $\beta _{j+1}={\frac {r_{j+1}^{T}r_{j+1}}{r_{j+1}r_{j}}}$;

set $d_{j+1}=-r_{j+1}+\beta _{j+1}d_{j}$;

end (for)

The initialization of $p_{0}=0$ is fundamental, as the Cauchy Point is obtained right after in $p_{1}$; this condition guarantees global convergence.

Termination Criteria

The convergence of a trust region algorithm (1) depends on the accuracy of the approximate solution to the subproblem (2). It is desirable that the subproblem is approximated rather than solved exactly, provided the approximation guarantees the algorithm’s convergence . Fletcher proposes that the algorithm terminates when either of the following are small :

1. $f(x_{k})-f(x_{k+1})$
2. $x_{k}-x_{k+1}$
3. $\nabla f(x_{k})$

These criteria ensure that the algorithm terminates efficiently while maintaining convergence.

In addition, termination can be considered when $\Delta _{k}$ is small as it is possible for $\Delta _{k}$ to converge to 0 when $k$ approaches infinity.

Numerical example

Example One

This section introduces trust region methods and demonstrates their application using a simple function as a numerical example. Consider the following:

$f(x)=(x-2)^{2}$

Our goal is to minimize this function, and clearly, the solution is $x=2$ where $f(2)=0$.

The gradient is $f'(x)=2(x-2)$ and the Hessian is $f''(x)=2$.

Iteration 1:

To calculate, begin the initial point at $x_{0}=0$ and a trust region radius as $1.0$. From this initial point, the following is obtained:

Step 1: evaluate the current point:

$f(x_{0})=(0-2)^{2}=4$

Gradient: $f'(x_{0})=2(0-2)=-4$

Hessian: $2$

Step 2: form the quadratic model

$m_{0}(p)=f(x_{0})+\nabla f_{0}^{T}p+{\frac {1}{2}}p^{T}H_{0}=m_{0}(p)=4+(-4)p+{\frac {1}{2}}p^{2}(2)=4-4p+p^{2}$

Step 3: solve the subproblem

$m_{0}'(p)=-4+2p=0$ $p=2$

However, $p=2$ is outside the trust region radius $1.0$. Hence, $|p|\leq 1$ will be utilized to find the best step.

$m_{0}(1)=4-4(1)+1^{2}=1$

$m_{0}(-1)=4-4(-1)+(-1)^{2}=9$

The lower value is $p=1$

Step 4: check function reduction

Proposed new point: $x_{1}=x_{0}+p=0+1=1$

Actual function at new point: $f(1)=(1-2)^{2}=1$

Step 5: compute ratio

Actual reduction: $f(x_{0})-f(x_{1})=4-1=3$

Prediction reduction: $f(x_{0})-m_{0}(1)=4-1=3$

Hence $p={\frac {3}{3}}=1$

Step 6: update trust region and accept/reject step

Acceptant criteria for the ratio are typically as follows (may vary):

If $p<0.25$, reduce the trust region radius, if $p>0.75$, expand the trust region radius.

In the example, $p$ is greater than $p>0.75$, thus the trust region should be expanded and the step is accepted. Suppose the trust region radius is doubled (i.e. to $2.0$).

Iteration 2:

The point now is at $x_{1}=1$ and a radius as $2.0$. From this point, the following is obtained:

Step 1: evaluate the current point:

$f(1)=1$

Gradient: $f'(1)=2(1-2)=-2$

Hessian: $2$

Step 2: form the quadratic model

$m_{1}(p)=f(1)+\nabla f_{0}^{T}p+{\frac {1}{2}}p^{T}H_{1}=1-2p+p^{2}$

Step 3: solve the subproblem

$m_{1}'(p)=-2+2p=0$   $p=1$

$p\leq 2$, then $p=1$ is valid

Step 4: check function reduction

Proposed new point: $x_{2}=x_{1}+1=2$

Actual function at new point: $f(2)=(2-2)^{2}=0$

Step 5: compute ratio

Actual reduction: $f(1)-f(2)=1-0=1$

Prediction reduction: $f(1)-m_{1}(1)=1-0=1$

Hence $p={\frac {1}{1}}=1$

Step 6: update trust region and accept/reject step

In the example, since $p$ is greater than $p>0.75$, the proposed step is accepted. By taking this step, the problem reaches the exact minimum is reached at $x=2$, and therefore terminates.

Example Two - Himmulblau’s Function

The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research . It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.

The function is defined as the following:

$f(x,y)=(x^{2}+y-11)^{2}+(x+y^{2}-7)^{2}$

where $x$ and $y$ are real numbers.

The four global minima of the function are at:

1. $(3.0,2.0)$
2. $(-2.805,3.131)$
3. $(-3.779,-3.283)$
4. $(3.584,-1.848)$

The figure illustrates how the trust region radius adjusts throughout the optimization process, reflecting the optimizer’s confidence in the model’s predictions.

Due to the complexities in the calculations involved in the trust region method algorithm, the minimize function with the 'trust-constr' method from the SciPy library in Python can be utilized to solve this problem. Consider the following implementation:

minimize(method=’trust-constr’)

Iteration 1:

To calculate, begin the optimization with the initial guess as $(-4.0,0)$ and trust region radius as $1.0$. The optimal solution achieved from this iteration is $(-3.382,-0.786)$, yield a function value of $95.453$. The initial point gives a sufficient prediction, thus, increase the trust region radius to $7.0$.

The figure shows the trajectory of the optimizer from the initial guess to the found minimum over the contour plot of Hummuelblau’s function.

Iteration 2:

In this iteration, the updated point $(-4.0,0)$ and radius $7.0$ are used to find a new step. However, an insufficient prediction was obtained, leading to a decrease in the trust region radius to $0.7$. The optimal solution obtained from the previous iteration is retained for the next step.

Iteration 3:

With the updated point $(-3.382,-0.786)$ trust region radius $0.7$, a new point at $(-3.072,-1.413)$ was obtained.

The following shows the remaining iterations:

The convergence achieved at iteration 11 with $x=-3.779,y=-3.283$ and $f(x)=0$.

Applications

Trust region methods are applied in optimization problems across various domains due to their robustness, adaptability, and efficiency in handling complex constraints. Their ability to balance local and global optimization strategies makes them invaluable in solving high-dimensional, nonlinear, and constrained problems. These application areas include:

Engineering

Trust region methods are widely used in engineering, particularly in structural optimization, to improve the stability and efficiency of design processes. These methods address challenges in high-dimensional design problems by iteratively refining solutions with defined trust regions,making them effective for complex objectives such as optimization of material distribution, minimizing stress, or improving flow geometries. For instance, Yano et al. introduce a globally convergent method to accelerate topology optimization with trust region frameworks. This approach significantly reduces computational costs while maintaining accuracy in optimal design solutions.

Finance

Trust region methods are also increasingly applied in the financial sector as these methods ensure stable and reliable convergence even when dealing with complex, non-linear and volatile financial data. For example, in the study by Phua et al. , trust region methods were employed during the optimization of neural network training. This approach significantly improved the forecasting accuracy of major stick indices like DAX and NASDAQ by effectively managing high-dimensional and noisy financial datasets.

Machine Learning

Algorithms like ACKTR (Actor-Critic using Kronecker-Factored Trust Region) use trust regions to improve training stabilities and sample efficiencies in deep reinforcement learning. Specifically, ACKTR uses an approximation of the natural gradient to maintain a trust region during updates, preventing large and unstable parameter changes. This benefits facilitation of applications in robotics and autonomous systems .

Conclusion

Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence . Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling , and developing more efficient techniques to handle constraints and uncertainties in real-world applications.