Error bounds of Lanczos approach for trust-region subproblem

Abstract

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 subspaces 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.

Keywords

Trust-region method / trust-region subproblem (TRS) / Lanczos method / Steihaug–Toint conjugate-gradient iteration / error bound

References

[1] Conn A R, Gould N I M, Toint P L. Trust-Region Methods. Philadelphia: SIAM, 2000

[2] Demmel J. Applied Numerical Linear Algebra. Philadelphia: SIAM, 1997

[3] Gay D M. Computing optimal locally constrained steps. SIAM J Sci Statist Comput, 1981, 2: 186–197

[4] Golub G H, Van Loan C F. Matrix Computations. 3rd ed. Baltimore: Johns Hopkins University Press, 1996

[5] Golub G H, von Matt U. Quadratically constrained least squares and quadratic problems. Numer Math, 1991, 59: 561–580

[6] Gould N I M, Lucidi S, Roma M, Toint P L. Solving the trust-region subproblem using the Lanczos method. SIAM J Optim, 1999, 9: 504–525

[7] Hager W W. Minimizing a quadratic over a sphere. SIAM J Optim, 2001, 12: 188–208

[8] Hager W W, Krylyuk Y. Graph partitioning and continuous quadratic programming. SIAM J Discrete Math, 1999, 12(4): 500–523

[9] Li C K, Li R C. A note on eigenvalues of perturbed Hermitian matrices. Linear Algebra Appl, 2005, 395: 183–190

[10] Li R C. On Meinardus’ examples for the conjugate gradient method. Math Comp, 2008, 77(261): 335–352

[11] Li R C. Sharpness in rates of convergence for symmetric Lanczos method. Math Comp, 2010, 79(269): 419–435

[12] Li R C, Zhang L H. Convergence of block Lanczos method for eigenvalue clusters. Numer Math, 2015, 131: 83–113

[13] Luk˘san L, Matonoha C, Vl˘cek J. On Lagrange multipliers of trust-region subproblems. BIT, 2008, 48: 763–768

[14] Moŕe J, Sorensen D C. Computing a trust region step. SIAM J Sci Statist Comput, 1983, 4(3): 553–572

[15] Nocedal J, Wright S. Numerical Optimization. 2nd ed. Berlin: Springer, 2006

[16] Parlett B N. The Symmetric Eigenvalue Problem. Philadelphia: SIAM, 1998

[17] Rendl R, Wolkowicz H. A semidefinite framework for trust region subproblems with applications to large scale minimization. Math Program, 1997, 77(2): 273–299

[18] Rojas M, Santos S A, Sorensen D C. Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization. ACM Trans Math Software, 2008, 34(2): 1–28

[19] Rojas M, Santos S A, Sorensen D C. A new matrix-free algorithm for the large-scale trust-region subproblem. SIAM J Optim, 2000, 11: 611–646

[20] Rojas M, Sorensen D C. A trust-region approach to the regularization of large-scale discrete forms of ill-posed problems. SIAM J Sci Comput, 2002, 23: 1843–1861

[21] Saad Y. Iterative Methods for Sparse Linear Systems. 2nd ed. Philadelphia: SIAM, 2003

[22] Sorensen D C. Minimization of a large-scale quadratic function subject to a spherical constraint. SIAM J Optim, 1997, 7: 141–161

[23] Steihaug T. The conjugate gradient method and trust regions in large scale optimization. SIAM J Numer Anal, 1983, 20: 626–637

[24] Tarantola A. Inverse Problem Theory. Amsterdam: Elsevier, 1987

[25] Tikhonov A N. Regularization of incorrectly posed problems. Soviet Math, 1963, 4: 1624–1627

[26] Toint P L. Towards an efficient sparsity exploiting Newton method for minimization. In: Duff I, ed. Sparse Matrices and Their Uses. London: Academic Press, 1981, 57–88

[27] Zhang L H, Shen C G, Li R C. On the generalized Lanczos trust-region method. SIAM J Optim, 2017, 27(3): 2110–2142

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature