Studies Of Trust Region Subproblem Based On Linear Multistep Method

In the trust region algorithm, solving the trust region subproblem is the key to implementation of the trust region algorithm. Now, the most common trust region subproblem models are: quadratic model, conic model, new conic model, tensor model. However, the most basic and important model is quadratic model. In recent years, the research on solving trust region subproblem with quadratic model have been developing rapidly. Generally speaking, it can be divided into two categories: one is the accurate solution method, the other is the imprecise solution method. In those imprecise solution methods, the dogleg method is the most common method. Dogleg method has the advantage of simple operation and low cost, because of these preponderances, it always been used for solving the trust region subproblem with quadratic model. With the in-depth study of line algorithm, people improve the optimality conditions of solutions of the subproblem, finally, when the Hessian matrix is positive and definite, according to the parameter equation of the optimal curve, a differential equation model was constructed. After that, some new algorithms around this model were proposed. Such as a class of Euler algorithm, Heun algorithm, etc.On the base of differential equations model, this paper does further research on trust region subproblem with quadratic model. Combining with Adams formula which contains two-step, three-step, four-step formula, a new class of algorithm named Adams algorithm for solving trust region subproblem was proposed in this paper. Firstly-take Adams two-step explicit method as an example-this paper described the structure of the Adams two-step dogleg and its property. Then,I analyzed the well-posedness of this algorithm and compared this new algorithm with Euler tangent method. The numerical results indicate that Adams two-step method is much closer to the optimal curve than Euler tangent method and is an effective method for solving trust region subproblem. Secondly-take Adams three-step implicit method as an example-this paper described the structure of the Adams three-step dogleg and its property. Then,I analyzed the well-posedness of this algorithm and compared this new algorithm with implicit Euler tangent method. The numerical results indicate that Adams three-step method is an effective method for solving trust region subproblem. At last, take Adams four-step explicit method as an example-this paper described the structure of the Adams four-step dogleg and its property. Then,I analyzed the well-posedness of this algorithm and compared this new algorithm with average Euler tangent method. The numerical results indicate that Adams four-step method is an effective method for solving trust region subproblem.