Error bounds of Lanczos approach for trust-region subproblem  

作　　者：Leihong ZHANG Weihong YANG Chungen SHEN Jiang FENG 

机构地区：[1]School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China [2]Shanghai Key Laboratory of Financial Information Technology,Shanghai University of Finance and Economics, Shanghai 200433, China [3]School of Mathematical Sciences, Fudan University, Shanghai 200433, China [4]College of Science, University of Shanghai for Science and Technology, Shanghai 200093,China

出　　处：《Frontiers of Mathematics in China》2018年第2期459-481,共23页中国高等学校学术文摘·数学（英文）

基　　金：The authors would like to thank the anonymous referees for their careful reading and comments. This work of the first author was supported in part by the National Natural Science Foundation of China （Grant Nos. 11671246, 91730303, 11371102） and the work of the second author was supported in part by the National Natural Science Foundation of China （Grant Nos. 91730304, 11371102, 91330201）.

摘　　要：Because of its vital role of the trust-region subproblem （TRS） in various applications, for example, in optimization and in ill-posed problems, there are several factorization-free algorithms for solving the large-scale sparse TRS. The truncated Lanczos approach proposed by N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint [SIAM J. Optim., 1999, 9： 504-525] is a natural extension of the classical Lanczos method for the symmetric linear system and eigenvalue problem and, indeed follows the classical Rayleigh-Ritz procedure for eigenvalue computations. It consists of 1） projecting the original TRS to the Krylov subspa^es to yield smaller size TRS＇s and then 2） solving the resulted TRS＇s to get the approximates of the original TRS. This paper presents a posterior error bounds for both the global optimal value and the optimal solution between the original TRS and their projected counterparts. Our error bounds mainly rely on the factors from the Lanczos process as well as the data of the original TRS and, could be helpful in designing certain stopping criteria for the truncated Lanczos approach.Because of its vital role of the trust-region subproblem （TRS） in various applications, for example, in optimization and in ill-posed problems, there are several factorization-free algorithms for solving the large-scale sparse TRS. The truncated Lanczos approach proposed by N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint [SIAM J. Optim., 1999, 9： 504-525] is a natural extension of the classical Lanczos method for the symmetric linear system and eigenvalue problem and, indeed follows the classical Rayleigh-Ritz procedure for eigenvalue computations. It consists of 1） projecting the original TRS to the Krylov subspa^es to yield smaller size TRS＇s and then 2） solving the resulted TRS＇s to get the approximates of the original TRS. This paper presents a posterior error bounds for both the global optimal value and the optimal solution between the original TRS and their projected counterparts. Our error bounds mainly rely on the factors from the Lanczos process as well as the data of the original TRS and, could be helpful in designing certain stopping criteria for the truncated Lanczos approach.

关 键 词：Trust-region method trust-region subproblem （TRS） Lanczos method Steihaug-Toint conjugate-gradient iteration error bound 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TN919.8[自动化与计算机技术—计算机科学与技术]