×

zbMATH — the first resource for mathematics

Solving the trust-region subproblem by a generalized eigenvalue problem. (English) Zbl 1359.49009

MSC:
49M37 Numerical methods based on nonlinear programming
65K10 Numerical optimization and variational techniques
90C25 Convex programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000, . · Zbl 0965.65058
[2] S. P. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. · Zbl 1058.90049
[3] S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), pp. 432–451, . · Zbl 1298.90062
[4] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust Region Methods, Volume 1. SIAM, Philadelphia, 2000, . · Zbl 0958.65071
[5] J. B. Erway and P. E. Gill, A subspace minimization method for the trust-region step, SIAM J. Optim., 20 (2009), pp. 1439–1461, . · Zbl 1195.49042
[6] J. B. Erway, P. E. Gill, and J. D. Griffin, Iterative methods for finding a trust-region step, SIAM J. Optim., 20 (2009), pp. 1110–1131, . · Zbl 1189.49049
[7] G. E. Forsythe and G. H. Golub, On the stationary values of a second-degree polynomial on the unit sphere, J. Soc. Indust. Appl. Math., 13 (1965), pp. 1050–1068, . · Zbl 0168.03005
[8] C. Fortin and H. Wolkowicz, The trust region subproblem and semidefinite programming, Optim. Methods Softw., 19 (2004), pp. 41–67, . · Zbl 1070.65041
[9] C. Fortin and H. Wolkowicz, Trust region subroutine algorithm: Algorithm and Documentation, 2010, .
[10] W. Gander, G. H. Golub, and U. von Matt, A constrained eigenvalue problem, Linear Algebra Appl., 114 (1989), pp. 815–839, . · Zbl 0666.15006
[11] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. and Stat. Comput., 2 (1981), pp. 186–197, . · Zbl 0467.65027
[12] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[13] N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504–525, . · Zbl 1047.90510
[14] N. I. M. Gould, D. Orban, and P. L. Toint, GALAHAD, a library of thread-safe fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Software, 29 (2003), pp. 353–372, . · Zbl 1068.90525
[15] N. I. M. Gould, D. P. Robinson, and H. S. Thorne, On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2 (2010), pp. 21–57. · Zbl 1193.65098
[16] W. W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), pp. 188–208, . · Zbl 1058.90045
[17] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, .
[18] G. Huber, Gamma function derivation of n-sphere volumes, Amer. Math. Monthly, 89 (1982), pp. 301–302.
[19] S. Iwata, Y. Nakatsukasa, and A. Takeda, Global optimization methods for extended Fisher discriminant analysis, in Proceedings of the Seventh AISTATS, JMLR W and CP 33, 2014, pp. 411–419.
[20] R. Lehoucq, D. C. Sorensen, and C. Yang, Arpack User’s Guide: Solution of Large-Scale Eigenvalue Problems With Implicitly Restorted Arnoldi Methods, Vol. 6, SIAM, Philadelphia, 1998, . · Zbl 0901.65021
[21] S. Lucidi, L. Palagi, and M. Roma, On some properties of quadratic programs with a convex quadratic constraint, SIAM J. Optim., 8 (1998), pp. 105–122, . · Zbl 0910.90227
[22] J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM J. Optim., 4 (1994), pp. 159–176, . · Zbl 0801.65057
[23] J. J. Moré, Recent developments in algorithms and software for trust region methods, Mathematical Programming: the State of the Art, Springer, Berlin, 1983, pp. 258–287.
[24] J. J. Moré, Generalizations of the trust region problem, Optimization Methods and Software, 2 (1993), pp. 189–209, .
[25] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. and Stat. Comput., 4 (1983), pp. 553–572, . · Zbl 0551.65042
[26] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer-Verlag, New York, 1999. · Zbl 0930.65067
[27] C. C. Paige, B. N. Parlett, and H. A. Van der Vorst, Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl., 2 (1995), pp. 115–133, . · Zbl 0831.65036
[28] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617–629, . · Zbl 0319.65025
[29] T. K. Pong and H. Wolkowicz, The generalized trust region subproblem, Comput. Optim. Appl., 58 (2014), pp. 273–322, . · Zbl 1329.90100
[30] F. Rendl and H. Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Programming, 77 (1997), pp. 273–299, . · Zbl 0888.90137
[31] E. Rimon and S. P. Boyd, Obstacle collision detection using best ellipsoid fit, J. Intell. Robot. Syst., 18 (1997), pp. 105–126, . · Zbl 1067.68775
[32] M. Rojas, S. A. Santos, and D. C. Sorensen, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11 (2001), pp. 611–646, . · Zbl 0994.65067
[33] M. Rojas, S. A. Santos, and D. C. Sorensen, Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Softw., 34 (2008), 11, . · Zbl 1291.65177
[34] S. Sakaue, Y. Nakatsukasa, A. Takeda, and S. Iwata, Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim., 26 (2016), pp. 1669–1694, . · Zbl 1346.49050
[35] D. C. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7 (1997), pp. 141–161, . · Zbl 0878.65044
[36] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626–637, . · Zbl 0518.65042
[37] G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Computer Science and Scientific Computing, Academic Press, Boston, 1990. · Zbl 0706.65013
[38] P. D. Tao and L. T. H. An, A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8 (1998), pp. 476–505, . · Zbl 0913.65054
[39] P. L. Toint, Towards an efficient sparsity exploiting Newton method for minimization, Sparse Matrices and Their Uses, I. S. Duff, ed., Academic Press, London, 1981, pp. 57–88.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.