Trust-region methods

From optimization
Revision as of 19:07, 27 May 2014 by Yewenhe0904 (Talk | contribs)

Jump to: navigation, search

Authors: Wenhe (Wayne) Ye (ChE 345 Spring 2014) Steward: Dajun Yue, Fengqi You Date Presented: Apr. 10, 2014



Trust-region method (TRM) is one of the most important numerical optimization method in solving nonlinear programing (NLP) problems. It works in a way that first define a region around the current best solution, in which a certain model (usually a quadratic model) can to some extent approximate the original objective function. TRM then take a step forward according to the model depicts within the region. Unlike the line search method, TRM usually determines both the step size and direction at the same time. If a notable decrease (our following discussion will based on minimization problems) is gained after the step forward, then the model is believed to be a good representation of the original objective function. If the improvement is too subtle or even a negative improvement is gained, the region is not to be believed as a good representation of the original objective function. The convergence is thus ensured that the size of the “trust region” (usually the radius in Euclidean norm) in each iteration would depend on the improvement previously made.

Trust-Region Method Overview.png

A pictorial view of trust-region method optimization pathway

Important Concepts


In most cases, the trust-region is defined as a spherical area of radius \Delta_k in which the trust-region subproblem lies.

Trust-region subproblem

If we are using the quadratic model to approximate the original objective function, then our optimization problem is essentially reduced to solving a sequence of trust-region subporblems



Where \Delta_k is the trust region radius, g_k is the gradient at current point and B_k is the hessian (or a hessian approximation). It is easy to find the solution to the trust-region subproblem if B_k is positive definite.

Actual reduction and predicted reduction

The most critical issue underlying the trust-region method is to update the size of the trust-region at every iteration. If the current iteration makes a satisfactory reduction, we may exploits our model more in the next iteration by setting a larger \Delta_k. If we only achieved a limited improvement after the current iteration, the radius of the trust-region then should not have any increase, or in the worst cases, we may decrease the size of the trust-region by adjusting the radius to a smaller value to check the model’s validity.


Whether to take a more ambitious step or a more conservative one is depend on the ratio between the actual reduction gained by true reduction in the original objective function and the predicted reduction expected in the model function. Empirical threshold values of the ratio \rho_k will guide us in determining the size of the trust-region.

TRM stepsize.png

The picture shows both the stepsize and the improving direction is a consequence of a pre-determined trust-region size

Trust Region Algorithm

Before implementing the trust-region algorithm, we should first determine several parameters. \Delta_M is the upper bound for the size of the trust region. \eta_1, \eta_2 and \eta_3,t_1,t_2 are the threshold values for evaluating the goodness of the quadratic model thus for determining the trust-region’s size in the next iteration.


Decide the starting point at x_0, set the iteration number k=1

For k=1,2...

Get the improving step by solving trust-region subproblem ()

Evaluate \rho_k from equation()

If \rho_k<\eta_2



If \rho_k>\eta_3 and p_k=||\Delta_k|| (full step and model is a good approximation)




If \rho_k>\eta_1



x_{k+1}=x_k(the model is not a good approximation and need to solve another trust-region subproblem within a smaller trust-region)

end >

Methods of Solving the Trust-region Subproblem

Cauchy point calculation

In line search methods, we may find an improving direction from the gradient information, that is, by taking the steepest descent direction with regard to the maximum range we could make. We can solve the trust-region subproblem in an inexpensive way. This method is also denoted as the Cauchy point calculation. We can also express the improving step explicitly by the following closed-form equations


if {g_k}^TB_kg_k<=0 \tau_k=1

otherwise \tau_k=min~ ({||g_k||}^3/(\Delta_k{g_k}^TB_kg_k),1)

TRM CauchyPoint.png

Illustration of Cauchy Point Calculation

Limitations and Further Improvements

Though Cauchy point is cheap to implement, like the steepest descent method, it performs poorly in some cases. Varies kinds of improvements are based on including the curvature information from B_k.

Dogleg Method

If B_k is positive definite (we can use quasi-Newton hessian approximation to guarantee), then a V-shaped trajectory can be determined by

if 0<=\tau<=1,~~p(\tau)=\tau p^U

if 1<=\tau<=2,~~p(\tau)=\tau p^U+(\tau-1)(p^B-p^U)

where p^U=-\frac{g^Tg}{g^TBg}g is the steepest descent direction

Note that hessian or approximate hessian will be evaluated

TRM Dogleg.png

Illustration of dogleg method trajectory

Conjugated Gradient Steihaug’s Method

The most widely used method for solving a trust-region sub-problem is by using the idea of conjugated gradient (CG) method for minimizing a quadratic function since CG guarantees convergence within a finite number of iterations for a quadratic programming. Also, CG Steihaug’s method has the merit of Cauchy point and Dogleg method that both in terms of super-linear convergence rate and inexpensiveness to compute.

Pseudo-code for CG Steihaug method in solving trust region sub-problem

Given tolerance \epsilon_k > 0;

Set z_0=0, r_0=\nabla f_k, d_0=-r_0=-\nabla f_k

if ||r_0|| <\epsilon_k

return p_k = z_0 = 0;

for j = 0, 1, 2, . . .

if {d_j}^TB_k d_j <= 0

Find \tau such that p_k = z_j + \tau d_j minimizes m_k(p_k)

and satisfies ||p_k|| =  \Delta_k ;

return p_k ;

Set \alpha_j = {r_j}^Tr_j /{d_j}^TB_kd_j;

Set z_{j+1} = z_j + \alpha_jd_j ;

if ||z_{j+1}|| >= \Delta_k

Find \tau >= 0 such that p_k = z_j + \tau d_j satisfies ||p_k|| =  \Delta_k ;

return p_k ;

Set r_{j+1} = r_j + \alpha_j B_kd_j ;

if ||r_{j+1}|| <\epsilon_k

return p_k = z_{j+1};

Set \beta_{j+1} = \frac{{r_{j+1}}^T{r_{j+1}}}{{r_j}^Tr_j} ;

Set d_{j+1}=-r_{j+1}+\beta_{j+1}d_j



Here we use the trust-region method to solve an unconstrained problem as an example. The trust-region subproblems are solved by calculate the Cauchy point.


Starting point x_1=1.00, x_2=1.00

\Delta_1=0.050, \Delta_M=5.0, t_1=0.25, t_2=2.0, \eta_1=0.2,\eta_2=0.25,\eta_3=0.75


Optimization trajectory

Improving Process

Iteration~~~~  1~~~ Obj.Value=18.3940  ~~~x_1=1.0000~~~ x_2=1.0000~~~  \rho_k=0.9980~~~  \Delta_k=0.0500~~~   norm (p_k)=0.0500~~~   norm( g_k)=18.3940

Iteration~~~~  2~~~ Obj.Value=17.4532  ~~~x_1=1.0000~~~ x_2=1.0500~~~  \rho_k=0.9919~~~  \Delta_k=0.1000~~~   norm (p_k)=0.1000~~~   norm( g_k)=19.2183

Iteration~~~~  3~~~ Obj.Value=15.4707  ~~~x_1=0.9955~~~ x_2=1.1499~~~  \rho_k=0.9693~~~  \Delta_k=0.2000~~~   norm (p_k)=0.2000~~~   norm( g_k)=20.3369

Iteration~~~~  4~~~ Obj.Value=11.3678  ~~~x_1=0.9706~~~ x_2=1.3483~~~  \rho_k=0.9063~~~  \Delta_k=0.4000~~~   norm (p_k)=0.4000~~~   norm( g_k)=20.2425

Iteration~~~~  5~~~ Obj.Value=4.5490  ~~~x_1=0.8723~~~ x_2=1.7361~~~  \rho_k=1.0278~~~  \Delta_k=0.4000~~~   norm (p_k)=0.4000~~~   norm( g_k)=12.9098

Iteration~~~~  6~~~ Obj.Value=1.1522  ~~~x_1=0.7119~~~ x_2=2.1025~~~  \rho_k=1.2072~~~  \Delta_k=0.8000~~~   norm (p_k)=0.3094~~~   norm( g_k)=4.6860

Iteration~~~ ~ 7~~~ Obj.Value=0.2770  ~~~x_1=0.5534~~~ x_2=2.3683~~~  \rho_k=1.2294~~~  \Delta_k=0.8000~~~   norm (p_k)=0.2274~~~   norm( g_k)=1.4368

Iteration~~~ ~ 8~~~ Obj.Value=0.0761  ~~~x_1=0.4190~~~ x_2=2.5516~~~  \rho_k=1.2358~~~  \Delta_k=0.8000~~~   norm (p_k)=0.1870~~~   norm( g_k)=0.4740

Iteration~~~ ~ 9~~~ Obj.Value=0.0214  ~~~x_1=0.2958~~~ x_2=2.6923~~~  \rho_k=1.2359~~~  \Delta_k=0.8000~~~   norm (p_k)=0.1598~~~   norm( g_k)=0.1599

Iteration~~~ 10~~~ Obj.Value=0.0056  ~~~x_1=0.1787~~~ x_2=2.8010~~~  \rho_k=1.2287~~~  \Delta_k=0.8000~~~   norm (p_k)=0.1393~~~   norm( g_k)=0.0542

Iteration~~~ 11~~~ Obj.Value=0.0009  ~~~x_1=0.0632~~~ x_2=2.8789~~~  \rho_k=1.2061~~~  \Delta_k=0.8000~~~   norm (p_k)=0.1330~~~   norm( g_k)=0.0184

Iteration~~~ 12~~~ Obj.Value=-0.0005  ~~~x_1=-0.0640~~~ x_2=2.9179~~~  \rho_k=0.6843~~~  \Delta_k=0.8000~~~   norm (p_k)=0.8000~~~   norm( g_k)=0.0074

Iteration~~~ 13~~~ Obj.Value=-0.0036  ~~~x_1=-0.7883~~~ x_2=2.5781~~~  \rho_k=3.7923~~~  \Delta_k=0.8000~~~   norm (p_k)=0.8000~~~   norm( g_k)=0.0238

Iteration~~~ 14~~~ Obj.Value=-0.2532  ~~~x_1=-0.4389~~~ x_2=1.8584~~~  \rho_k=1.5730~~~  \Delta_k=1.6000~~~   norm (p_k)=1.6000~~~   norm( g_k)=1.0587

Iteration~~~ 15~~~ Obj.Value=-10.6674  ~~~x_1=-0.2638~~~ x_2=0.2680~~~  \rho_k=0.8272~~~  \Delta_k=3.2000~~~   norm (p_k)=0.5845~~~   norm( g_k)=33.0767

Iteration~~~ 16~~~ Obj.Value=-18.6637  ~~~x_1=-0.8285~~~ x_2=0.1173~~~  \rho_k=0.0744~~~  \Delta_k=3.2000~~~   norm (p_k)=0.7080~~~   norm( g_k)=22.4871

Iteration~~~ 17~~~ Obj.Value=-18.6637  ~~~x_1=-0.8285~~~ x_2=0.1173~~~  \rho_k=0.0744~~~  \Delta_k=0.8000~~~   norm (p_k)=0.7080~~~   norm( g_k)=22.4871

Iteration~~~ 18~~~ Obj.Value=-18.6637  ~~~x_1=-0.8285~~~ x_2=0.1173~~~  \rho_k=0.9378~~~  \Delta_k=0.2000~~~   norm (p_k)=0.2000~~~   norm( g_k)=22.4871

Iteration~~~ 19~~~ Obj.Value=-22.2857  ~~~x_1=-0.7343~~~ x_2=-0.0592~~~  \rho_k=0.8198~~~  \Delta_k=0.4000~~~   norm (p_k)=0.3464~~~   norm( g_k)=13.7680

Iteration~~~ 20~~~ Obj.Value=-24.2409  ~~~x_1=-0.7076~~~ x_2=-0.4046~~~  \rho_k=1.0061~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0994~~~   norm( g_k)=10.0666

Iteration~~~ 21~~~ Obj.Value=-24.7440  ~~~x_1=-0.8039~~~ x_2=-0.3803~~~  \rho_k=1.0000~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0303~~~   norm( g_k)=1.1463

Iteration~~~ 22~~~ Obj.Value=-24.7613  ~~~x_1=-0.8146~~~ x_2=-0.4086~~~  \rho_k=1.0005~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0019~~~   norm( g_k)=0.1859

Iteration~~~ 23~~~ Obj.Value=-24.7615  ~~~x_1=-0.8164~~~ x_2=-0.4080~~~  \rho_k=1.0000~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0003~~~   norm( g_k)=0.0121

Iteration~~~ 24~~~ Obj.Value=-24.7615  ~~~x_1=-0.8165~~~ x_2=-0.4083~~~  \rho_k=1.0000~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0000~~~   norm( g_k)=0.0019

Iteration~~~ 25~~~ Obj.Value=-24.7615  ~~~x_1=-0.8165~~~ x_2=-0.4082~~~  \rho_k=1.0000~~~  \Delta_k=0.4000~~~   norm (p_k)=0.0000~~~   norm( g_k)=0.0001


Trust-Region vs. Line Search

Line search methods:

- Pick improving direction

- Pick stepsize to minimize

- Update the incumbent solution

Trust-region methods:

- Pick the stepsize (the trust-region subproblem is constrained)

- Solving the subproblem using the approximated model

- If the improvement is acceptable, update the incumbent solution and the size of the trust-region


1. J. Nocedal, S. J. Wright, Numerical optimization. Springer, 1999.

2. Wikipedia page for Trust-Region Methods

3. Yuan, Y. "A review of trust region algorithms for optimization" in ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000 Oxford University Press, USA.