Trust-region methods

From optimization
Revision as of 14:04, 23 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

Authors: Issac Newton, Albert Einstein (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

Date Presented: Apr. 10, 2014

Contents

Introduction

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.

Important Concepts

Trust-region In most cases, the trust-region is defined as a spherical area of radius DELTAk 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 EQUATION 1 Where DELTAk is the trust region radius, gk is the gradient at current point and Bk is the hessian (or a hessian approximation). It is easy to find the solution to the trust-region subproblem if Bk 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 DELTAk. 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. EQUATION 2 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 ROUk will guide us in determining the size of the trust-region.

Pictorial illustration

Trust Region Algorithm

Before implementing the trust-region algorithm, we should first determine several parameters. DELTAmax is the upper bound for the size of the trust region. ETA1, ETA2 and ETA3,T1,T2 are the threshold values for evaluating the goodness of the quadratic model thus for determining the trust-region’s size in the next iteration.

Pseudo-code Decide the starting point at x0, set the iteration number k=1 For k=1,2,… get the improving step by solving trust-region subproblem () evaluate ROUk from equation() if ROUk<ETA2 DELTAk+1=T1*DELTAk Else If ROUk>ETA3 and ||pk||=DELTAk (full step and model is a good approximation) DELTAk+1=min(2DELTAk,DELTAmax) Else DELTAk+1=DELTAk If ROUk>ETA1 Xk+1=xk+pk Else Xk+1=xk(the model is not a good approximation and need to solve another trust-region subproblem within a smaller trust-region) end

Example of Solving the Trust-region Subproblem (Cauchy point calculation)

Conclusion

References

1. T.F. Edgar, D.M. Himmelblau, L.S. Lasdon, Optimization of Chemical Processes, McGraw-Hill, 2001.

2. L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design, Prentice-Hall: Upper Saddle River, 1997.