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

Algebraic rules for quadratic regularization of Newton’s method

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this work we propose a class of quasi-Newton methods to minimize a twice differentiable function with Lipschitz continuous Hessian. These methods are based on the quadratic regularization of Newton’s method, with algebraic explicit rules for computing the regularizing parameter. The convergence properties of this class of methods are analysed. We show that if the sequence generated by the algorithm converges then its limit point is stationary. We also establish local quadratic convergence in a neighborhood of a stationary point with positive definite Hessian. Encouraging numerical experiments are presented.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. http://www.netlib.org/lapack/.

  2. http://www.netlib.org/blas/.

References

  1. Birgin, E.G., Gentil, J.M.: Evaluating bound-constrained minimization software. Comput. Optim. Appl. 53(2), 347–373 (2012)

    Article  MATH  MathSciNet  Google Scholar 

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

  3. Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. 127(2), 245–295 (2011)

  4. Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity. Math. Program. 130(2), 295–319 (2011)

  5. Cartis, C., Gould, N.I.M., Toint, Ph.L.: 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)

  6. Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA (2000)

  7. Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics in Applied Mathematics. SIAM, Philadelphia, PA (1996). (Corrected reprint of the 1983 original)

    Book  Google Scholar 

  8. Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley, Chichester (1987)

    MATH  Google Scholar 

  9. Fuentes, M., Malick, J., Lemaréchal, C.: Descentwise inexact proximal algorithms for smooth optimization. Comput. Optim. Appl. 53(3), 755–769 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gill, P.E., Murray, W., Wright, R.H.: Practical Optimization. Academic Press Inc., San Diego (1981)

    MATH  Google Scholar 

  11. Goldfeld, S.M., Quandt, R.E., Trotter, H.F.: Maximization by quadratic hill-climbing. Econometrica 34, 541–551 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  12. Gould, N.I.M., Porcelli, M., Toint, Ph.L.: Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl. 53(1), 1–22 (2012)

  13. Griewank, A.: The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1981)

  14. Hager, W.W., Zhang, H.: Self-adaptive inexact proximal point methods. Comput. Optim. Appl. 39(2), 161–181 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  15. Hebden, M. D.: An algorithm for minimization using exact second derivatives. Technical Report T.P. 515, AERE Harwell Laboratory, Harwell, Oxfordshire (1973)

  16. Lehoucq, R.B., Sorensen, D.C., Yang, C.: ARPACK Users Guide, Software, Environments, and Tools. SIAM, Philadelphia, PA (1998)

    Book  Google Scholar 

  17. Levenberg, K.: A method for the solution of certain non-linear problems in least squares. Quart. Appl. Math. 2, 164–168 (1944)

    MATH  MathSciNet  Google Scholar 

  18. Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Info Recherche Opérationnelle, 4:154–158 (1970)

  19. Moré, J. J.: Recent developments in algorithms and software for trust region methods. In: Proceedings of the Mathematical programming: the state of the art (Bonn, 1982), pp. 258–287. Springer, Berlin (1983)

  20. Nesterov, Y., Polyak, B. T.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1):177–205 (2006)

  21. Nocedal, J., Wright, S.J.: Numerical Optimization. Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)

    Google Scholar 

  22. Schnabel, R.B., Koontz, J.E., Weiss, B.E.: A modular system of algorithms for unconstrained minimization. ACM Trans. Math. Softw. 11(4), 419–440 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  23. Tikhonov, A. N.: On the stability of inverse problems (39, pp. 176–179). C. R. (Doklady) Acad. Sci. URSS (N.S), Moscow (1943)

  24. Tukey, J.W.: Exploratory Data Analysis. Behavioral Science: Quantitative Methods. Addison-Wesley Publishing Company, Reading, MA (1977)

    Google Scholar 

  25. Weiser, M., Deuflhard, P., Erdmann, B.: Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413–431 (2007)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors are grateful to José Mario Martínez and Ernesto Birgin for their valuable comments and suggestions. We are also thankful to the anonymous referee whose suggestions led to improvements in the paper. Elizabeth W. Karas was partially supported by CNPq Grants 307714/2011-0 and 477611/2013-3. Sandra A. Santos was partially supported by CNPq Grant 304032/2010-7, FAPESP Grants 2013/05475-7, 2013/07375-0 and PRONEX Optimization. Benar F. Svaiter was partially supported by CNPq Grants 302962/2011-5, 474996/2013-1, FAPERJ Grant E-26/102.940/2011 and PRONEX Optimization.

Author information

Authors and Affiliations

  1. Department of Mathematics, Federal University of Paraná, CP 19081, Curitiba, PR , 81531-980, Brazil

    Elizabeth W. Karas

  2. Department of Applied Mathematics, University of Campinas, Campinas, SP, Brazil

    Sandra A. Santos

  3. IMPA, Estrada Dona Castorina 110, Rio de Janeiro , 22460-320, Brazil

    Benar F. Svaiter

Authors
  1. Elizabeth W. Karas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sandra A. Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Benar F. Svaiter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Elizabeth W. Karas.

Appendix

Appendix

The complete computational results are presented next.

Table 1 Numerical results
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Karas, E.W., Santos, S.A. & Svaiter, B.F. Algebraic rules for quadratic regularization of Newton’s method. Comput Optim Appl 60, 343–376 (2015). https://doi.org/10.1007/s10589-014-9671-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-014-9671-y

Keywords

Mathematics Subject Classification

Search

Navigation