Research On Trust Region Subproblem Algorithm Based On Quadratic Model

Trust region method is an important class of numerical methods for solving nonlinear optimization problems, the algorithm attracts optimize researchers’ widespread attention by its strong posedness and global convergence, and it has long been a research focus for nonlinear programming. However, the key to implementation of trust region algorithm is the solution of trust region subproblem, it directly affects the stability and convergence of the algorithm. For solving the trust region subproblem, under the tireless efforts of mathematicians from home and abroad, many kinds of models for trust region subproblem have been established so far. The quadratic model, due to its simple form and convenience to calculate, is the most basic and widely used model to approximate the objective function. Among the methods for solving trust region subproblem with quadratic model, the dogleg method is an important and effective class of calculation method. In this paper, we primarily discuss the quadratic model for solving the trust region subproblem. Based on the subsection secant method and differential equation model, we have made a further research of the dogleg method for solving trust region subproblem and promoted the existing conclusions.This article is started from the two aspects of the piecewise low order interpolation and the differential equation model of the optimal curve. Firstly, for the piecewise low order interpolation, we introduced two kinds of modified decomposition methods for the case of Hessian matrix as an indefinite matrix, a modified subsection secant method for solving the trust region subproblem was constructed by using these methods. Meanwhile, by comparing the new algorithm with hybrid dogleg algorithm, we get a better numerical results. Secondly, under the premise of Hessian matrix as an positive definite matrix, we constructed a piecewise cubic Hermite curve for solving trust region subproblem combining with the idea of piecewise cubic interpolation in numerical analysis, proved the rationality of the curve path, and a piecewise cubic Hermite interpolation method was presented for solving trust region subproblem. Using the new algorithm and piecewise secant algorithm to test the commonly used optimization test functions, we get the ideal results of the numerical experiments. Thirdly, based on the differential equation model of the optimal curve, we mainly discussed the selection strategy of stepsize by considering the global convergence of trust region algorithm, and further analysis of the nature of Heun’s dogleg path was made, proved the posedness of the algorithm, and constructed a variable stepsize Heun’s algorithm for solving trust region subproblem. Numerical experiments show that the new algorithm is effective and feasible. Finally, under the conditions of Hessian matrix as a positive definite matrix and fixed stepsize, we adopted three kinds of high-order Runge-Kutta methods, to solve the differential equation model. Three different Runge-Kutta curves were constructed to approximate the optimal curve respectively to solve trust region subproblem. we analyzed and compared the optimal solutions of test functions by these three methods through MATLAB programming and numerical experiment. The effectiveness and feasibility of the new algorithm are illustrated.