The convergence of the Generalized Lanczos Trust-Region Method for the Trust-Region Subproblem
The convergence of the Generalized Lanczos Trust-Region Method for the Trust-Region Subproblem
复制标题
DOI：
10.1137/19m1279691
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Zhongxiao Jia;Fa Wang
中科院分区：
文献类型：
--
作者：
Zhongxiao Jia;Fa Wang
信赖域子问题（TRS）的求解在数值优化和许多其他应用中起着关键作用。广义Lanczos信任域（GLTR）方法是求解大规模TRS的一种著名的Lanczos型方法。该方法将原始的大规模TRS投影到k维的Krylov子空间上，该Krylov子空间的正交基由对称的Lanczos过程生成，并从底层子空间计算近似解。文献中已有一些最优解和最优目标值的先验误差界，但没有关于投影TRS中涉及的拉格朗日乘子的收敛性和近似解的残差范数的先验结果。本文建立了GLTR方法的一般收敛理论，导出了最优拉格朗日乘子误差、最优解误差、最优目标值误差和近似解残差范数误差的先验界。数值实验表明，我们的边界是真实的，可以准确地预测三种误差和残差范数的收敛速度。
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 well-known Lanczos type approach for solving a large-scale TRS. The method projects the original large-scale TRS onto a $k$ dimensional Krylov subspace, whose orthonormal basis is generated by the symmetric Lanczos process, and computes an approximate solution from the underlying subspace. There have been some a-priori error bounds for the optimal solution and the optimal objective value in the literature, but no a-priori result exists on the convergence of Lagrangian multipliers involved in projected TRS's and the residual norm of approximate solution. In this paper, a general convergence theory of the GLTR method is established, and a-priori bounds are derived for the errors of the optimal Lagrangian multiplier, the optimal solution, the optimal objective value and the residual norm of approximate solution. Numerical experiments demonstrate that our bounds are realistic and predict the convergence rates of the three errors and residual norms accurately.