Strategy for Choosing the Radius in the Trust Region Method — Part 1/2

Issue 2

5th September, 2022

When one constructs an optimization scheme based on trust, one typically takes recourse to a theorem. In this case we use the Taylor’s expansion to construct an optimization recipe which is popularly called the Trust Region Method.

# We use the Taylor's expansion to expand the function around the current iterate.
# We minimize the below model subject to ||p||<=The Trust Region Radius where B is an approximation to the Hessian - this is the model m(p) which one optimizes: 
f[k,1] + delta[k,1]%*%p[k,1] + (1/2)*(p[k,1]%*%B[k,1])%*%p[k,1] 
# The ratio of actual reduction in the function to the predicted reduction is setup as a metric: 
rho<-(f[k,1]-f[k+1,1])/(m(0)-m(p))
# If rho is close to 1 it means the actual and the predicted reduction are similar and so the trust region can be increased so that the size of cost improvement can increase. 
# When the ratio is near zero or negative we reduce the trust region radius. 
# As in the case of a line search algorithm where Goldstein's conditions need to be satisfied for convergence, a sufficient reduction in the model leads one to a point called the Cauchy Point which guarantees global convergence.

By taking the Cauchy Point as the benchmark we are always implementing the steepest descent method but with a particular choice of step length. Even with an optimal step length, the steepest descent performs poorly.

In the next issue I will talk about methods to improve upon the Cauchy Point method, discuss the sufficient reduction condition more and allude to superlinear convergence.

Originally published at https://www.linkedin.com.