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

Yusen Zhang; Bo Feng; Yusen Zhang; Bo Feng

doi:10.3934/era.2026326

Electronic Research Archive

2026, Volume 34, Issue 10: 7565-7582. doi: 10.3934/era.2026326

Previous Article Next Article

Research article

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

Yusen Zhang ,
Bo Feng ^,

School of Mathematics, Yangzhou University, Yangzhou 225000, China

Received: 24 May 2026 Revised: 09 August 2026 Accepted: 24 August 2026 Published: 02 September 2026

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 (GMRES) 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.
- trust-region subproblem,
- generalized Lanczos trust-region (GLTR) method,
- Krylov subspace,
- minimal residual method
Citation: Yusen Zhang, Bo Feng. A minimal residual method for large-scale trust-region subproblem[J]. Electronic Research Archive, 2026, 34(10): 7565-7582. doi: 10.3934/era.2026326

Related Papers:

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 (GMRES) 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.

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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 10.1007/s10543-008-0197-5
[32]	G. W. Stewart, Matrix Agorithms 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 doi: 10.1016/S0024-3795(96)00238-8

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)