The Trust-Region Method

In the unconstrained optimization, two approaches are fundamental: the line-search and the trust-region. Both of them generate steps by using a quadratic model of the minimizing function, but in different ways. The line-search methods, presented in the previous chapters, generate a descent search direction d and then determine a suitable stepsize α along this direction, hoping that the function values will be reduced. On the other hand, the trust-region methods define a region around the current iterate within which we trust the quadratic model to be an adequate representation of the minimizing function and to choose the step which is the approximate minimizer of the model in this region. Therefore, the trust-region methods choose the direction and the stepsize simultaneously. Of course, if a step is not acceptable, the size of the region will be reduced and a new minimizer will be found. The size of the trust-region is important in the economy of each step. If the region is too small, then the algorithm will take small steps. If it is too large, the minimizer of the model may be far from the minimizer of the function. The size of the region is selected based on the performance of the algorithm at the previous iteration.