{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:25:17Z","timestamp":1773797117057,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["401288\/2014-5"],"award-info":[{"award-number":["401288\/2014-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["406269\/2016-5"],"award-info":[{"award-number":["406269\/2016-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11075-020-00987-6","type":"journal-article","created":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T22:02:40Z","timestamp":1596751360000},"page":"779-796","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A generalized worst-case complexity analysis for non-monotone line searches"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3284-3371","authenticated-orcid":false,"given":"Geovani N.","family":"Grapiglia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ekkehard W.","family":"Sachs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,6]]},"reference":[{"key":"987_CR1","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/02331934.2011.641126","volume":"61","author":"M Ahookhosh","year":"2012","unstructured":"Ahookhosh, M., Amini, K., Bahrami, S.: A class of nonmonotone Armijo-type line search method for unconstrained optimization. Optimization 61, 387\u2013404 (2012)","journal-title":"Optimization"},{"key":"987_CR2","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.apm.2016.10.055","volume":"43","author":"M Ahookhosh","year":"2017","unstructured":"Ahookhosh, M., Ghaderi, S.: On efficiency of nonmonotone Armijo-type line searches. Appl. Math. Model. 43, 170\u2013190 (2017)","journal-title":"Appl. Math. Model."},{"key":"987_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s11075-013-9723-x","volume":"60","author":"K Amini","year":"2014","unstructured":"Amini, K., Ahookhosh, M., Nosratipour, H.: An inexact line search approach using modified nonmonotone strategy for unconstrained optimization. Numerical Algorithms 60, 49\u201378 (2014)","journal-title":"Numerical Algorithms"},{"key":"987_CR4","doi-asserted-by":"publisher","unstructured":"Bellavia, S., Gurioli, G., Morini, B.: Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization. IMA Journal of Numerical Analysis, drz076. https:\/\/doi.org\/10.1093\/imanum\/drz076(2020)","DOI":"10.1093\/imanum\/drz076"},{"key":"987_CR5","doi-asserted-by":"publisher","unstructured":"Bellavia, S., Kreji\u0107, N., Jerinki\u0107, N.K.: Subsampled inexact Newton methods for minimizing large sums of convex functions. IMA Journal of Numerical Analysis, drz027. https:\/\/doi.org\/10.1093\/imanum\/drz027https:\/\/doi.org\/10.1093\/imanum\/drz027 (2020)","DOI":"10.1093\/imanum\/drz027 10.1093\/imanum\/drz027"},{"key":"987_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.2478\/caim-2020-0002","volume":"11","author":"S Bellavia","year":"2020","unstructured":"Bellavia, S., Jerinki\u0107, N.K., Malaspina, G.: Subsampled nonmonotone spectral gradient methods. Communications in Applied and Industrial Mathematics 11, 19\u201334 (2020)","journal-title":"Communications in Applied and Industrial Mathematics"},{"key":"987_CR7","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s10957-018-1341-2","volume":"178","author":"E Bergou","year":"2018","unstructured":"Bergou, E., Diouane, Y., Gratton, S.: A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis. Journal on Optimization Theory and Applications 178, 885\u2013913 (2018)","journal-title":"Journal on Optimization Theory and Applications"},{"key":"987_CR8","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10107-016-1065-8","volume":"163","author":"EG Birgin","year":"2017","unstructured":"Birgin, E.G., Gardenghi, J.L., Mart\u00ednez, J.M., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Program. 163, 359\u2013368 (2017)","journal-title":"Math. Program."},{"key":"987_CR9","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.1137\/16M110280X","volume":"27","author":"EG Birgin","year":"2017","unstructured":"Birgin, E.G., Mart\u00ednez, J.M.: The use of quadratic regularization with a cubic descent condition for unconstrained optimization. SIAM J. Optim. 27, 1049\u20131074 (2017)","journal-title":"SIAM J. Optim."},{"key":"987_CR10","doi-asserted-by":"publisher","first-page":"2833","DOI":"10.1137\/090774100","volume":"20","author":"C Cartis","year":"2010","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: On the complexity of steepest descent, Newton\u2019s and regularized Newton\u2019s methods for nonconvex unconstrained optimization problems. SIAM J. Optim. 20, 2833\u20132852 (2010)","journal-title":"SIAM J. Optim."},{"key":"987_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10107-009-0337-y","volume":"130","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularization methods for unconstrained optimization. Part II: worst-case function - and derivative - evaluation complexity. Math. Program. 130, 295\u2013319 (2011)","journal-title":"Math. Program."},{"key":"987_CR12","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1080\/02331934.2013.869809","volume":"64","author":"C Cartis","year":"2015","unstructured":"Cartis, C., Sampaio, P.R., Toint, P.L.: Worst-case evaluation complexity of first-order non-monotone gradient-related algorithms for unconstrained optimization. Optimization 64, 1349\u20131361 (2015)","journal-title":"Optimization"},{"key":"987_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10898-008-9318-6","volume":"44","author":"W La Cruz","year":"2009","unstructured":"La Cruz, W., Noguera, G.: Hybrid spectral gradient method for the unconstrained minimization problem. J. Glob. Optim. 44, 193\u2013212 (2009)","journal-title":"J. Glob. Optim."},{"key":"987_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-1026-2","volume":"162","author":"FE Curtis","year":"2017","unstructured":"Curtis, F.E., Robinson, D.P., Samadi, M.: A trust region algorithm with a worst-case iteration complexity of $\\mathcal {O}(\\epsilon ^{-3\/2})$ for nonconvex optimization. Math. Program. 162, 1\u201332 (2017)","journal-title":"Math. Program."},{"key":"987_CR15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"E Dolan","year":"2002","unstructured":"Dolan, E., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201\u20132013 (2002)","journal-title":"Math. Program."},{"key":"987_CR16","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1080\/10556788.2017.1322080","volume":"33","author":"J-P Dussault","year":"2018","unstructured":"Dussault, J.-P.: ARCq: a new adaptive regularization by Cubics variant. Optimization Methods and Software 33, 322\u2013335 (2018)","journal-title":"Optimization Methods and Software"},{"key":"987_CR17","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s10107-014-0794-9","volume":"152","author":"GN Grapiglia","year":"2015","unstructured":"Grapiglia, G.N., Yuan, J., Yuan, Y.: On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization. Math. Program. 152, 491\u2013520 (2015)","journal-title":"Math. Program."},{"key":"987_CR18","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1007\/s10957-016-1007-x","volume":"171","author":"GN Grapiglia","year":"2016","unstructured":"Grapiglia, G.N., Yuan, J., Yuan, Y.: Nonlinear stepsize control algorithms: complexity bounds for first-and second-order optimality. J. Optim. Theory Appl. 171, 980\u2013997 (2016)","journal-title":"J. Optim. Theory Appl."},{"key":"987_CR19","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s10589-017-9928-3","volume":"68","author":"GN Grapiglia","year":"2017","unstructured":"Grapiglia, G.N., Sachs, E.W.: On the worst-case evaluation complexity of non-monotone line search algorithms. Comput. Optim. Appl. 68, 555\u2013577 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"987_CR20","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1137\/16M1087801","volume":"27","author":"GN Grapiglia","year":"2017","unstructured":"Grapiglia, G.N., Nesterov, Y.: Regularized Newton methods for minimizing functions with H\u00f6lder continuous Hessians. SIAM J. Optim. 27, 478\u2013506 (2017)","journal-title":"SIAM J. Optim."},{"key":"987_CR21","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1137\/050623012","volume":"19","author":"S Gratton","year":"2008","unstructured":"Gratton, S., Sartenaer, A., Toint, P.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19, 414\u2013444 (2008)","journal-title":"SIAM J. Optim."},{"key":"987_CR22","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00933356","volume":"34","author":"AO Griewank","year":"1981","unstructured":"Griewank, A.O.: Generalized descent for global optimization. J. Optim. Theory Appl. 34, 11\u201339 (1981)","journal-title":"J. Optim. Theory Appl."},{"key":"987_CR23","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1137\/0723046","volume":"23","author":"L Grippo","year":"1986","unstructured":"Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton\u2019s method. SIAM J. Numer. Anal. 23, 707\u2013716 (1986)","journal-title":"SIAM J. Numer. Anal."},{"key":"987_CR24","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671\u2013680 (1983)","journal-title":"Science"},{"key":"987_CR25","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1080\/10556780008805782","volume":"13","author":"DH Li","year":"2000","unstructured":"Li, D.H., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optimization Methods & Software 13, 181\u2013201 (2000)","journal-title":"Optimization Methods & Software"},{"key":"987_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1023\/A:1004680806815","volume":"104","author":"M Locatelli","year":"2000","unstructured":"Locatelli, M.: Simulated annealing algorithms for continuous global optimization: convergence conditions. J. Optim. Theory Appl. 104, 121\u2013133 (2000)","journal-title":"J. Optim. Theory Appl."},{"key":"987_CR27","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10898-016-0475-8","volume":"68","author":"JM Mart\u00ednez","year":"2017","unstructured":"Mart\u00ednez, J.M., Raydan, M.: Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization. J. Glob. Optim. 68, 367\u2013385 (2017)","journal-title":"J. Glob. Optim."},{"key":"987_CR28","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H.: Equation of state calculations by fast computer machines. J. Chem. Phys. 21, 1087\u20131092 (1953)","journal-title":"J. Chem. Phys."},{"key":"987_CR29","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cam.2006.10.070","volume":"209","author":"J Mo","year":"2007","unstructured":"Mo, J., Liu, C., Yan, S.: A nonmonotone trust-region method based on nonincreasing technique of weighted average of the sucessive function value. J. Comput. Appl. Math. 209, 97\u2013108 (2007)","journal-title":"J. Comput. Appl. Math."},{"key":"987_CR30","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/355934.355936","volume":"7","author":"JJ Mor\u00e9","year":"1981","unstructured":"Mor\u00e9, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17\u201341 (1981)","journal-title":"ACM Trans. Math. Softw."},{"key":"987_CR31","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"AS Nemirovsky","year":"1983","unstructured":"Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)"},{"key":"987_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: a Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: a Basic Course. Kluwer Academic Publishers, Dordrecht (2004)"},{"key":"987_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program. 108, 177\u2013205 (2006)","journal-title":"Math. Program."},{"key":"987_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on Convex Optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y: Lectures on Convex Optimization. Springer, Berlin (2018)"},{"key":"987_CR35","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1007\/s10092-017-0226-3","volume":"54","author":"H Nosratipour","year":"2017","unstructured":"Nosratipour, H., Borzabadi, A.H., Fard, O.S.: On the nonmonotonicity degree of nonmonotone line searches. Calcolo 54, 1217\u20131242 (2017)","journal-title":"Calcolo"},{"key":"987_CR36","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1137\/17M1134329","volume":"28","author":"CW Royer","year":"2018","unstructured":"Royer, C.W., Wright, S.J.: Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim. 28, 1448\u20131477 (2018)","journal-title":"SIAM J. Optim."},{"key":"987_CR37","first-page":"1059","volume":"40","author":"EW Sachs","year":"2011","unstructured":"Sachs, E.W., Sachs, S.M.: Nonmonotone line searches for optimization algorithms. Control. Cybern. 40, 1059\u20131075 (2011)","journal-title":"Control. Cybern."},{"key":"987_CR38","volume-title":"Optimization Theory and Methods: Nonlinear Programming","author":"W Sun","year":"2006","unstructured":"Sun, W., Yuan, Y.: Optimization Theory and Methods: Nonlinear Programming. Springer, Berlin (2006)"},{"key":"987_CR39","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1080\/10556788.2013.855761","volume":"29","author":"DA Tarzanagh","year":"2014","unstructured":"Tarzanagh, D.A., Peyghami, M.R., Mesgarani, H.: A new nonmonotone trust region method for unconstrained optimization equipped by an efficient adaptive radius. Optimization Methods & Software 29, 819\u2013836 (2014)","journal-title":"Optimization Methods & Software"},{"key":"987_CR40","doi-asserted-by":"publisher","unstructured":"Xu, P., Roosta, F., Mahoney, M.W.: Newton-type methods for non-convex optimization under inexact Hessian information. Mathematical Programming. https:\/\/doi.org\/10.1007\/s10107-019-01405-z (2020)","DOI":"10.1007\/s10107-019-01405-z"},{"key":"987_CR41","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1137\/S1052623403428208","volume":"14","author":"HC Zhang","year":"2004","unstructured":"Zhang, H.C., Hager, W.W.: A nonmonotone line search technique for unconstrained optimization. SIAM Journal on Optimization 14, 1043\u20131056 (2004)","journal-title":"SIAM Journal on Optimization"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-020-00987-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-020-00987-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-020-00987-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T23:10:12Z","timestamp":1628205012000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-020-00987-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,6]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["987"],"URL":"https:\/\/doi.org\/10.1007\/s11075-020-00987-6","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,6]]},"assertion":[{"value":"8 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}