{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T18:10:27Z","timestamp":1772302227822,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T00:00:00Z","timestamp":1437004800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10107-015-0933-y","type":"journal-article","created":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T09:07:03Z","timestamp":1436951223000},"page":"363-381","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["A linear-time algorithm for trust region problems"],"prefix":"10.1007","volume":"158","author":[{"given":"Elad","family":"Hazan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9061-0448","authenticated-orcid":false,"given":"Tomer","family":"Koren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"issue":"1","key":"933_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"key":"933_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In: 46th IEEE Symposium on Foundations of Computer Science, pp. 339\u2013348 (2005)","DOI":"10.1109\/SFCS.2005.35"},{"issue":"1","key":"933_CR3","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02592331","volume":"72","author":"A Ben-Tal","year":"1996","unstructured":"Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72(1), 51\u201363 (1996)","journal-title":"Math. Program."},{"issue":"15","key":"933_CR4","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1016\/j.dam.2005.04.010","volume":"154","author":"S Busygin","year":"2006","unstructured":"Busygin, S.: A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. 154(15), 2080\u20132096 (2006)","journal-title":"Discrete Appl. Math."},{"key":"933_CR5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719857","volume-title":"Trust Region Methods","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I., Toint, P.L.: Trust Region Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)"},{"issue":"3","key":"933_CR6","doi-asserted-by":"crossref","first-page":"1439","DOI":"10.1137\/08072440X","volume":"20","author":"JB Erway","year":"2009","unstructured":"Erway, J.B., Gill, P.E.: A subspace minimization method for the trust-region step. SIAM J. Optim. 20(3), 1439\u20131461 (2009)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"933_CR7","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1137\/070708494","volume":"20","author":"JB Erway","year":"2009","unstructured":"Erway, J.B., Gill, P.E., Griffin, J.D.: Iterative methods for finding a trust-region step. SIAM J. Optim. 20(2), 1110\u20131131 (2009)","journal-title":"SIAM J. Optim."},{"key":"933_CR8","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1016\/0024-3795(89)90494-1","volume":"114","author":"W Gander","year":"1989","unstructured":"Gander, W., Golub, G.H., von Matt, U.: A constrained eigenvalue problem. Linear Algebra Appl. 114, 815\u2013839 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"933_CR9","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0902016","volume":"2","author":"DM Gay","year":"1981","unstructured":"Gay, D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2(2), 186\u2013197 (1981)","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"933_CR10","volume-title":"Matrix Computations","author":"GH Golub","year":"1989","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore (1989)"},{"issue":"2","key":"933_CR11","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1137\/S1052623497322735","volume":"9","author":"NI Gould","year":"1999","unstructured":"Gould, N.I., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504\u2013525 (1999)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"933_CR12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s12532-010-0011-7","volume":"2","author":"NI Gould","year":"2010","unstructured":"Gould, N.I., Robinson, D.P., Thorne, H.S.: On solving trust-region and other regularised subproblems in optimization. Math. Program. Comput. 2(1), 21\u201357 (2010)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"933_CR13","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczynski","year":"1992","unstructured":"Kuczynski, J., Wozniakowski, H.: Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"933_CR14","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/0904038","volume":"4","author":"JJ Mor\u00e9","year":"1983","unstructured":"Mor\u00e9, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553\u2013572 (1983)","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"2","key":"933_CR15","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $${O}(1\/k^2)$$ O ( 1 \/ k 2 ) . Sov. Math. Dokl. 27(2), 372\u2013376 (1983)","journal-title":"Sov. Math. Dokl."},{"key":"933_CR16","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-point polynomial algorithms in convex programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.S., Ye, Y.: Interior-point polynomial algorithms in convex programming, vol. 13. SIAM, Philadelphia (1994)"},{"issue":"3","key":"933_CR17","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1379759.1379762","volume":"55","author":"CH Papadimitriou","year":"2008","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM (JACM) 55(3), 14 (2008)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"933_CR18","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02614438","volume":"77","author":"F Rendl","year":"1997","unstructured":"Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(1), 273\u2013299 (1997)","journal-title":"Math. Program."},{"issue":"6","key":"933_CR19","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1137\/S1064827500378167","volume":"23","author":"M Rojas","year":"2002","unstructured":"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. 23(6), 1842\u20131860 (2002)","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"933_CR20","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1137\/S105262349928887X","volume":"11","author":"M Rojas","year":"2001","unstructured":"Rojas, M., Santos, S.A., Sorensen, D.C.: A new matrix-free algorithm for the large-scale trust-region subproblem. SIAM J. Optim. 11(3), 611\u2013646 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"933_CR21","doi-asserted-by":"crossref","first-page":"171","DOI":"10.2140\/pjm.1958.8.171","volume":"8","author":"M Sion","year":"1958","unstructured":"Sion, M.: On general minimax theorems. Pac. J. Math. 8(1), 171\u2013176 (1958)","journal-title":"Pac. J. Math."},{"issue":"1","key":"933_CR22","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1137\/S1052623494274374","volume":"7","author":"D Sorensen","year":"1997","unstructured":"Sorensen, D.: Minimization of a large-scale quadratic function subject to a spherical constraint. SIAM J. Optim. 7(1), 141\u2013161 (1997)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"933_CR23","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1137\/0805016","volume":"5","author":"RJ Stern","year":"1995","unstructured":"Stern, R.J., Wolkowicz, H.: Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM J. Optim. 5(2), 286\u2013313 (1995)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"933_CR24","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1287\/moor.28.2.246.14485","volume":"28","author":"JF Sturm","year":"2003","unstructured":"Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2), 246\u2013267 (2003)","journal-title":"Math. Oper. Res."},{"key":"933_CR25","doi-asserted-by":"crossref","unstructured":"Ye, Y.: A new complexity result on minimization of a quadratic function with a sphere constraint. In: Floudas, C., Pardalos, P. (eds.) Recent Advances in Global Optimization, pp. 19\u201331. Princeton University Press, NJ (1992)","DOI":"10.1515\/9781400862528.19"},{"issue":"1","key":"933_CR26","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1137\/S105262340139001X","volume":"14","author":"Y Ye","year":"2003","unstructured":"Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14(1), 245\u2013267 (2003)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"933_CR27","doi-asserted-by":"crossref","first-page":"3555","DOI":"10.1137\/09075531X","volume":"20","author":"H Zhang","year":"2010","unstructured":"Zhang, H., Conn, A.R., Scheinberg, K.: A derivative-free algorithm for least-squares minimization. SIAM J. Optim. 20(6), 3555\u20133576 (2010)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0933-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0933-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0933-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T03:54:41Z","timestamp":1566964481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0933-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,16]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["933"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0933-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,16]]}}}