Conjugate Gradient Algorithm For Solving The Trust Region Subproblem

Trust region (TR) method is an important class of numerical method for solving nonlinear optimization problems. This method is not only an alternative to conjugate gradient method of one-dimensional line search,and the algorithm is reliable,with strong convergence. Also, this method can solve the Hesse matrix is not positive defineite and difficulties such as the saddle point.So the TR method for the past 20 years the field of nonlinear programming is an important research direction, it is currently seeking to construct a new calculation of the direction of the means of optimization.The conjugate gradient method is simple in structure, small calculation, store less, do not need to construct the search direction for solving linear equations, etc, which makes it very suitable for solving large scale problems.Therefore, this article from the perspective of the subproblem, and conjugate gradient algorithm for unconstrainednonlinear optimization discussed the TR algorithm. For high-dimensional TR problem, first with pre-conditions for processing lower condition number of coefficient matrix. On this basis, propose effective solution algorithm, and made the corresponding convergence analysis and numerical demonstration.This article is divided into fore chapters. The first chapter is an introduction, mainly introduced to solve the subproblem of three methods, and this innovative,breakthrough and practical significance.In chapter II, combined conjugate gradient method and the advantages of re-start strategy and the introduction of non-monotonic techniques, proposed a new conjugate gradient algorithm. Improve the effectiveness of the algorithm. The algorithm is the traditional TR algorithm and conjugate gradient method to promote. Under the right conditions,given the global convergence of the new algorithm, numerical results show that the new algorithm is effective.In chapter III, for solving large linear equations with coefficient matrix preconditioning technique first decomposed into a from more easily solved, to reduce the condition number of coefficient matrix,combined with conjugate gradient method to improve the convergence rate, the final numerical experiment demonstrates that the new algorithm.ChapterⅣcombines the strategy and pre-conditioning techniques,for the coefficient matrix condition number for uncertain or large-scale optimization,and the introduction of non-monotonic technology,presents a new TR of the conjugate gradient method,that the convergence of the new algorithm,test results show that the algorithm is effective.