Error bounds of Lanczos approach for trust-region subproblem

doi:10.1007/s11464-018-0687-y

Front. Math. China

2018, Vol. 13

Issue (2) : 459-481 https://doi.org/10.1007/s11464-018-0687-y

RESEARCH ARTICLE

Error bounds of Lanczos approach for trust-region subproblem

Leihong ZHANG^1,²(

), Weihong YANG³, Chungen SHEN⁴, Jiang FENG¹

¹. School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China
². Shanghai Key Laboratory of Financial Information Technology, Shanghai University of Finance and Economics, Shanghai 200433, China
³. School of Mathematical Sciences, Fudan University, Shanghai 200433, China
⁴. College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China

Download: PDF(250 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Leihong ZHANG

Issue Date: 28 March 2018

Cite this article:

Leihong ZHANG,Weihong YANG,Chungen SHEN, et al. Error bounds of Lanczos approach for trust-region subproblem[J]. Front. Math. China, 2018, 13(2): 459-481.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-018-0687-y
https://academic.hep.com.cn/fmc/EN/Y2018/V13/I2/459

1	Conn A R, Gould N I M, Toint P L. Trust-Region Methods. Philadelphia: SIAM, 2000 https://doi.org/10.1137/1.9780898719857
2	Demmel J. Applied Numerical Linear Algebra. Philadelphia: SIAM, 1997 https://doi.org/10.1137/1.9781611971446
3	Gay D M. Computing optimal locally constrained steps. SIAM J Sci Statist Comput, 1981, 2: 186–197 https://doi.org/10.1137/0902016
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 https://doi.org/10.1007/BF01385796
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 https://doi.org/10.1137/S1052623497322735
7	Hager W W. Minimizing a quadratic over a sphere. SIAM J Optim, 2001, 12: 188–208 https://doi.org/10.1137/S1052623499356071
8	Hager W W, Krylyuk Y. Graph partitioning and continuous quadratic programming. SIAM J Discrete Math, 1999, 12(4): 500–523 https://doi.org/10.1137/S0895480199335829
9	Li C K, Li R C. A note on eigenvalues of perturbed Hermitian matrices. Linear Algebra Appl, 2005, 395: 183–190 https://doi.org/10.1016/j.laa.2004.08.026
10	Li R C. On Meinardus’ examples for the conjugate gradient method. Math Comp, 2008, 77(261): 335–352 https://doi.org/10.1090/S0025-5718-07-01922-9
11	Li R C. Sharpness in rates of convergence for symmetric Lanczos method. Math Comp, 2010, 79(269): 419–435 https://doi.org/10.1090/S0025-5718-09-02258-3
12	Li R C, Zhang L H. Convergence of block Lanczos method for eigenvalue clusters. Numer Math, 2015, 131: 83–113 https://doi.org/10.1007/s00211-014-0681-6
13	Luk˘san L, Matonoha C, Vl˘cek J. On Lagrange multipliers of trust-region subproblems. BIT, 2008, 48: 763–768 https://doi.org/10.1007/s10543-008-0197-5
14	Moŕe J, Sorensen D C. Computing a trust region step. SIAM J Sci Statist Comput, 1983, 4(3): 553–572 https://doi.org/10.1137/0904038
15	Nocedal J, Wright S. Numerical Optimization. 2nd ed. Berlin: Springer, 2006
16	Parlett B N. The Symmetric Eigenvalue Problem. Philadelphia: SIAM, 1998 https://doi.org/10.1137/1.9781611971163
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 https://doi.org/10.1007/BF02614438
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 https://doi.org/10.1145/1326548.1326553
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 https://doi.org/10.1137/S105262349928887X
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 https://doi.org/10.1137/S1064827500378167
21	Saad Y. Iterative Methods for Sparse Linear Systems. 2nd ed. Philadelphia: SIAM, 2003 https://doi.org/10.1137/1.9780898718003
22	Sorensen D C. Minimization of a large-scale quadratic function subject to a spherical constraint. SIAM J Optim, 1997, 7: 141–161 https://doi.org/10.1137/S1052623494274374
23	Steihaug T. The conjugate gradient method and trust regions in large scale optimization. SIAM J Numer Anal, 1983, 20: 626–637 https://doi.org/10.1137/0720042
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 https://doi.org/10.1137/16M1095056

[1]	Changli LIU, Ren-Cang LI. Structured backward error for palindromic polynomial eigenvalue problems, II: Approximate eigentriplets[J]. Front. Math. China, 2018, 13(6): 1397-1426.
[2]	ZHU Detong. Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization[J]. Front. Math. China, 2006, 1(4): 620-628.
[3]	YAN Qingyou, WEI Xiaopeng. Error analysis of symplectic Lanczos method for Hamiltonian eigenvalue problem[J]. Front. Math. China, 2006, 1(3): 430-451.

Viewed

Full text

Abstract

Cited

Shared

Discussed