Solving Large Scale Trust-region Subproblems Using Krylov Subspace Iterative Methods

Solving the trust-region subproblem(TRS)plays a key role in numerical optimization and many other applications.The generalized Lanczos trust-region(GLTR)method is a popular approach for solving a large-scale TRS.The convergence theory of the GLTR method is very incomplete at present.Specifically,there have been some a-priori bounds available for the errors of the approximate solutions and approximate objective values obtained by the GLTR method,but no a-priori bound exist on the errors of the approximate Lagrangian multipliers and the residual norms of approximate solutions obtained by the GLTR method.In particular,the computable residual norm is of crucial importance in both theory and practice as other three quantities are all uncomputable.In this thesis,we establish a general convergence theory of the GLTR method,and show that the a-priori bounds for these four quantities are closely interrelated.Moreover,we find that the computable residual norm can predict the sizes of other three uncomputable errors reliably.Numerical experiments demonstrate that our bounds are realistic and predict the convergence rates of the four quantities accurately.On the other side,based on a fundamental result that the solution of TRS of size 2n is mathematically equivalent to finding the rightmost eigenpair of a certain matrix pair of size 29),eigenvalue-based methods are promising due to their simplicity.Naturally,we want to compare the efficiency of the GLTR algorithm and the eigenvalue-based algorithms.For a reasonable comparison of overall efficiency of the GLTR algorithm and eigenvalue-based algorithms,a vital premise is that the two kinds of algorithms must compute the approximate solutions of TRS with(almost)the same accuracy,but such premise has been ignored in the literature.To this end,in this thesis,we establish close relationships between the two kinds of residual norms,so that,given a stopping tolerance for the eigenvalue-based algorithms,we are able to determine a reliable one that GLTR should use so as to ensure that GLTR and the eigenvalue-based algorithms deliver the converged approximate solutions with similar accuracy.Finally,we consider the perturbation analysis of TRS.There is no doubt that the perturbation analysis of TRS is of great significance to the study of TRS.However,there has been no relevant results about this perturbation problem.In this thesis,from the views of the perturbation analysis of linear systems and matrix eigenproblems,we establish the perturbation bounds for Lagrangian multiplier,the solution,the objective value and the residual norm of the TRS with the solution inside the trust region and the TRS with the solution on the trust region boundary,respectively.