Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for \(p\ge 1\)) and to assume Lipschitz continuity of the p-th derivative, then an \(\epsilon \)-approximate first-order critical point can be computed in at most \(O(\epsilon ^{-(p+1)/p})\) evaluations of the problem’s objective function and its derivatives. This generalizes and subsumes results known for \(p=1\) and \(p=2\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bellavia, S., Cartis, C., Gould, N.I.M., Morini, B., Toint, PhL: Convergence of a regularized Euclidean residual algorithm for nonlinear least-squares. SIAM J. Numer. Anal. 48(1), 1–29 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. Ser. A 149, 301–327 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cartis, C., Gould, N.I.M., Toint, PhL: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization. SIAM J. Optim. 20(6), 2833–2852 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cartis, C., Gould, N.I.M., Toint, PhL: Adaptive cubic overestimation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Progr. Ser. A 127(2), 245–295 (2011)

    Article  MATH  Google Scholar 

  5. Cartis, C., Gould, N.I.M., Toint, PhL: Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-evaluation complexity. Math. Progr. Ser. A 130(2), 295–319 (2011)

    Article  MATH  Google Scholar 

  6. Cartis, C., Gould, N.I.M., Toint, Ph.L.: Optimal Newton-type methods for nonconvex optimization. Technical Report naXys-17-2011, Namur Center for Complex Systems (naXys), University of Namur, Namur, Belgium (2011)

  7. Cartis, C., Gould, N.I.M., Toint, PhL: An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity. IMA J. Numer. Anal. 32(4), 1662–1695 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cartis, C., Gould, N.I.M., Toint, PhL: Complexity bounds for second-order optimality in unconstrained optimization. J. Complex. 28, 93–108 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cartis, C., Gould, N.I.M., Toint, PhL: Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization. Optim. Methods Softw. 27(2), 197–219 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cartis, C., Gould, N.I.M., Toint, Ph.L.: Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization. Part I: a basic complexity bound using a trust-region algorithm. Technical Report (in preparation), Namur Center for Complex Systems (naXys), University of Namur, Namur, Belgium (2016)

  11. Dussault, J.P.: Simple unified convergence proofs for the trust-region and a new ARC variant. Technical report, University of Sherbrooke, Sherbrooke, Canada (2015)

  12. Grapiglia, G.N., Yuan, J., Yuan, Y.: On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization. Math. Progr. Ser. A 152, 491–520 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gratton, S., Sartenaer, A., Toint, PhL: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19(1), 414–444 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Nesterov, Yu.: Introductory Lectures on Convex Optimization. Applied Optimization. Kluwer Academic Publishers, Dordrecht (2004)

    Book  MATH  Google Scholar 

  15. Nesterov, Yu.: Modified Gauss–Newton scheme with worst-case guarantees for global performance. Optim. Methods Softw. 22(3), 469–483 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Nesterov, Yu., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Progr. Ser. A 108(1), 177–205 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Vavasis, S.A.: Black-box complexity of local minimization. SIAM J. Optim. 3(1), 60–80 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  18. Vicente, L.N.: Worst case complexity of direct search. EURO J. Comput. Optim. 1, 143–153 (2013)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

The authors are pleased to thank Coralia Cartis and Nick Gould for valuable comments, in particular on the definition of the tensor Lipschitz condition and associated material. Two anonymous referees also helped to improve the final manuscript.

Author information

Authors and Affiliations

  1. Department of Computer Science, Institute of Mathematics and Statistics, University of São Paulo, Rua do Matão, 1010, Cidade Universitária, São Paulo, SP, 05508-090, Brazil

    E. G. Birgin & J. L. Gardenghi

  2. Department of Applied Mathematics, Institute of Mathematics, Statistics, and Scientific Computing, University of Campinas, Campinas, SP, Brazil

    J. M. Martínez & S. A. Santos

  3. Namur Center for Complex Systems (naXys) and Department of Mathematics, University of Namur, 61, rue de Bruxelles, 5000, Namur, Belgium

    Ph. L. Toint

Authors
  1. E. G. Birgin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. L. Gardenghi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. M. Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. A. Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ph. L. Toint
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ph. L. Toint.

Additional information

This work has been partially supported by the Brazilian agencies FAPESP (Grants 2010/10133-0, 2013/03447-6, 2013/05475-7, 2013/07375-0, and 2013/23494-9) and CNPq (Grants 304032/2010-7, 309517/2014-1, 303750/2014-6, and 490326/2013-7) and by the Belgian Fund for Scientific Research (FNRS).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Birgin, E.G., Gardenghi, J.L., Martínez, J.M. et al. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Program. 163, 359–368 (2017). https://doi.org/10.1007/s10107-016-1065-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1065-8

Keywords

Mathematics Subject Classification

Search

Navigation