Advanced search
Publication Cover
Optimization Methods and Software Volume 35, 2020 - Issue 2: Part I of the special issue dedicated to the 60th birthday of Professor Ya-xiang Yuan. Guest-Editors: Yu-Hong Dai, Xin Liu, Jiawang Nie, Zaiwen Wen
Submit an article Journal homepage
170
Views
10
CrossRef citations to date
0
Altmetric
Original Articles

A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

C. CartisMathematical Institute, Oxford University, Oxford, UKCorrespondence[email protected]
ORCID Iconhttps://orcid.org/0000-0002-0963-5550View further author information
ORCID Icon,
N. I. M. GouldComputational Mathematics Group, STFC-Rutherford Appleton Laboratory, Chilton, UKORCID Iconhttps://orcid.org/0000-0002-1031-1588View further author information
ORCID Icon &
Ph. L. TointDepartment of Mathematics, University of Namur, Namur, BelgiumView further author information
Pages 243-256 | Received 04 Jun 2019, Accepted 01 Oct 2019, Published online: 24 Oct 2019

References

  • N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan and T. Ma, Finding Approximate Local Minima Faster Than Gradient Descent. Princeton University, Technical Report, ArXiv: 1611.01146. 2016.
  • E.G. Birgin, J.L. Gardenghi, J.M. Martínez, S.A. Santos and Ph.L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Program. Ser. A 163(1) (2017), pp. 359–368.
  • E.G. Birgin and J.M. Martínez, The use of quadratic regularization with a cubic descent condition for unconstrained optimization, SIAM J. Optim. 27(2) (2017), pp. 1049–1074.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Prog. Ser. A 127(2) (2011), pp. 245–295.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function and derivative-evaluation complexity, Math. Prog. Ser. A 130(2) (2011), pp. 295–319.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, Complexity bounds for second-order optimality in unconstrained optimization, J. Complex. 28 (2012), pp. 93–108.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, How much patience do you have? a worst-case perspective on smooth nonconvex optimization, Optima 88 (2012), pp. 1–10.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, Second-order optimality and beyond: characterization and evaluation complexity in nonconvex convexly-constrained optimization, Found. Comput. Math 18(5) (2018), pp. 1073–1107.
  • C. Cartis, N.I.M. Gould and Ph.L. Toint, Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints. arXiv:1811.01220, 2018.
  • A.R. Conn, N.I.M. Gould and Ph.L. Toint, Trust-Region Methods, SIAM, Philadelphia, PA, 2000.
  • F.E. Curtis, D.P. Robinson and M. Samadi, A trust region algorithm with a worst-case iteration complexity of O(ϵ−3/2) for nonconvex optimization, Math. Prog. Ser. A 162(1) (2017), pp. 1–32.
  • G.N. Grapiglia, J. Yuan and Y. Yuan, Nonlinear stepsize control algorithms: Complexity bounds for first and second-order optimality, J. Optim. Theory. Appl. 17(3) (2016), pp. 980–997.
  • Y. Carmon and J.C. Duchi, Gradient Descent Efficiently Finds the Cubic-Regularized Nonconvex Newton Step. Stanford University, Technical Report. ArXiv:1612.00547. 2016.
  • S. Gratton, C.W. Royer and L.N. Vicente, A Decoupled First/Second-Order Steps Technique for Nonconvex Nonlinear Unconstrained Optimization With Improved Complexity Bounds. Technical Report 17-21, Department of Mathematics, University of Coimbra. 2017.
  • J.M. Martínez and M. Raydan, Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization. J. Global Opt. 2016. DOI: 10.1007/s10898-016-0475-8.
  • Y. Nesterov, Introductory Lectures on Convex Optimization, Kluwer Academic Publishers, Dordrecht, 2004.
  • Yu. Nesterov and B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Prog. Ser. A 108(1) (2006), pp. 177–205.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.