A minimal residual method for large-scale trust-region subproblem

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

This paper was devoted to solving the large-scale trust-region subproblem (TRS), a core subproblem in nonlinear optimization with extensive applications in scientific computing fields such as the Lorentz eigenvalue problem, Tikhonov regularization, nonlinear least squares, and so on. The generalized Lanczos trust-region (GLTR) method is one of the most popular iterative algorithms for large-scale TRS. In this method, the approximate solution converged more slowly than the approximate Lagrange multiplier. Inspired by this characteristic and the generalized minimal residual method (GM- RES) and minimal residual method (MINRES), we proposed a minimal residual method based on the GLTR framework (MRTR). The MRTR method fixed the approximate Lagrange multiplier from GLTR and sought the approximate solution that minimized the residual norm within the Krylov subspace. We established some theoretical results to characterize the relationship between the approximate solutions of MRTR and GLTR. The experimental results showed that the MRTR method outperformed the GLTR method in terms of iteration numbers and CPU running time, and its residual norm convergence curve was smoother with better numerical stability, while achieving approximate optimal values with the same high precision as GLTR.

Keywords

trust-region subproblem / generalized Lanczos trust-region (GLTR) method / Krylov subspace / minimal residual method

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] A. R. Conn, N. I. M. Gould, P. L. Toint, Trust-Region Methods , SIAM, Philadelphia, PA, 2000. https://doi.org/10.1137/1.9780898719857

[2] J. Nocedal, S. Wright, Numerical Optimization , 2^nd edition, Springer, New York, 2006.

[3] L. Zhang, C. Shen, W. Yang, J. Júdice, A Lanczos method for large-scale extreme Lorentz eigenvalue problems, SIAM J. Matrix Anal. Appl., 39 (2018), 611-631. https://doi.org/10.1137/17M1111401

[4] W. W. Hager, Y. Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J. Discrete Math., 12 (1999), 500-523. https://doi.org/10.1137/S0895480199335829

[5] M. Rojas, S. A. Santos, D. C. Sorensen, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11 (2001), 611-646. https://doi.org/10.1137/S105262349928887X

[6] M. Rojas, S. Santos, D. Sorensen, Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Software, 34 (2008), 1-28. https://doi.org/10.1145/1326548.1326553

[7] N. M. Gould, D. P. Robinson, H. S. Thorne, On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2 (2010), 21-57. https://doi.org/10.1007/s12532-010-0011-7

[8] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), 626-637, https://doi.org/10.1137/0720042

[9] P. Toint, Towards an efficient sparsity exploiting Newton method for minimization, in Sparse Matrices and Their Uses, Academic Press, London, (1981), 57-88.

[10] W. Gander, G.H. Golub, U. von Matt, A constrained eigenvalue problem, Linear Algebra Appl., 114-115 (1989), 815-839. https://doi.org/10.1016/0024-3795(89)90494-1

[11] S. Adachi, S. Iwata, Y. Nakatsukasa, A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim., 27 (2017), 269-291. https://doi.org/10.1137/16M1058200

[12] N. Gould, S. Lucidi, M. Roma, P. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), 504-525. https://doi.org/10.1137/S1052623497322735

[13] L. Zhang, C. Shen, A nested Lanczos method for the trust-region subproblem, SIAM J. Sci. Comput., 40 (2018), A2005-A2032. https://doi.org/10.1137/17M1145914

[14] F. Rendl, H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program., 77 (1997), 273-299. https://doi.org/10.1007/BF02614438

[15] J. B. Erway, P. E. Gill, J. D. Griffin, Iterative methods for finding a trust-region step, SIAM J. Optim., 20 (2009), 1110-1131. https://doi.org/10.1137/070708494

[16] G. H. Golub, U. von Matt, Quadratically constrained least squares and quadratic problems, Numer. Math., 59 (1991), 561-580. https://doi.org/10.1007/BF01385796

[17] J. J. Moré, D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4 (1983), 553-572. https://doi.org/10.1137/0904038

[18] D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19 (1982), 409-426. https://doi.org/10.1137/0719026

[19] D. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7 (1997), 141-161. https://doi.org/10.1137/S1052623494274374

[20] P. Tao, L. An, A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8 (1998), 476-505. https://doi.org/10.1137/S1052623494274313

[21] G. H. Golub, C. F. Van Loan, Matrix Computations , 4^th edition, Johns Hopkins University Press, Baltimore, MD, 2013.

[22] Y. Carmon, J. C. Duchi, First-order method for nonconvex quadratic minimization, SIAM Rev., 62 (2020), 395-436. https://doi.org/10.1137/20M1321759

[23] Y. Carmon, J. C. Duchi, Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems, in NIPS’18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, (2018), 10728-10738.

[24] B. Feng, G. Wu, On convergence of the generalized Lanczos trust-region method for trust-region subproblems, Adv. Comput. Math., 51 (2025), 4. https://doi.org/10.1007/s10444-024-10217-5

[25] N. I. M. Gould, V. Simoncini, Error estimates for iterative algorithms for minimizing regularized quadratic subproblems, Optim. Methods Software, 35 (2020), 304-328. https://doi.org/10.1080/10556788.2019.1670177

[26] Z. Jia, F. Wang, The convergence of the generalized Lanczos trust-region method for the trust-region subproblem, SIAM J. Optim., 31 (2021), 887-914. https://doi.org/10.1137/19M1279691

[27] L. Zhang, C. Shen, R. Li, On the generalized Lanczos trust-region method, SIAM J. Optim., 27 (2017), 2110-2142. https://doi.org/10.1137/16M1095056

[28] Y. Saad, Iterative Methods for Sparse Linear Systems , 2^nd edition, SIAM, Philadelphia, PA, 2003. https://doi.org/10.1137/1.9780898718003

[29] W. W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), 188-208. https://doi.org/10.1137/S1052623499356071

[30] N. J. Higham, Functions of Matrices: Theory and Computation , SIAM, Philadelphia, 2008. https://doi.org/10.1137/1.9780898717778

[31] L. Lukšan, C. Matonoha, J. Vlček, On Lagrange multipliers of trust-region subproblems, BIT Numer. Math., 48 (2008), 763-768. https://doi.org/10.1007/s10543-008-0197-5

[32] G. W. Stewart, Matrix Algorithms II: Eigensystems , SIAM, Philadelphia, 2001. https://doi.org/10.1137/1.9780898718058

[33] Z. Jia, Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997), 1-23. https://doi.org/10.1016/S0024-3795(96)00238-8