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

Critical solutions of nonlinear equations: local attraction for Newton-type methods

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

Abstract

We show that if the equation mapping is 2-regular at a solution in some nonzero direction in the null space of its Jacobian (in which case this solution is critical; in particular, the local Lipschitzian error bound does not hold), then this direction defines a star-like domain with nonempty interior from which the iterates generated by a certain class of Newton-type methods necessarily converge to the solution in question. This is despite the solution being degenerate, and possibly non-isolated (so that there are other solutions nearby). In this sense, Newtonian iterates are attracted to the specific (critical) solution. Those results are related to the ones due to A. Griewank for the basic Newton method but are also applicable, for example, to some methods developed specially for tackling the case of potentially non-isolated solutions, including the Levenberg–Marquardt and the LP-Newton methods for equations, and the stabilized sequential quadratic programming for optimization.

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

References

  1. Arutyunov, A.V.: Optimality Conditions: Abnormal and Degenerate Problems. Kluwer Academic Publishers, Dordrecht (2000)

    Book  MATH  Google Scholar 

  2. Avakov, E.R.: Extremum conditions for smooth problems with equality-type constraints. USSR Comput. Math. Math. Phys. 25, 24–32 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  3. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  4. DEGEN. http://w3.impa.br/~optim/DEGEN_collection.zip

  5. Facchinei, F., Fischer, A., Herrich, M.: A family of Newton methods for nonsmooth constrained systems with nonisolated solutions. Math. Methods Oper. Res. 77, 433–443 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Facchinei, F., Fischer, A., Herrich, M.: An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions. Math. Program. 146, 1–36 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fernández, D., Solodov, M.: Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems. Math. Program. 125, 47–73 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fischer, A., Herrich, M., Izmailov, A.F., Solodov, M.V.: Convergence conditions for Newton-type methods applied to complementarity systems with nonisolated solutions. Comput. Optim. Appl. 63, 425–459 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gfrerer, H., Mordukhovich, B.S.: Complete characterizations of tilt stability in nonlinear programming under weakest qualification conditions. SIAM J. Optim. 25, 2081–2119 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gfrerer, H., Outrata, J.V.: On computation of limiting coderivatives of the normal-cone mapping to inequality systems and their applications. Optimization 65, 671–700 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  11. Griewank, A.: Starlike domains of convergence for Newton’s method at singularities. Numer. Math. 35, 95–111 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12, 253–273 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  13. Izmailov, A.F.: On the analytical and numerical stability of critical Lagrange multipliers. Comput. Math. Math. Phys. 45, 930–946 (2005)

    MathSciNet  Google Scholar 

  14. Izmailov, A.F., Kurennoy, A.S., Solodov, M.V.: A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems. Math. Program. 142, 591–604 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Izmailov, A.F., Kurennoy, A.S., Solodov, M.V.: Critical solutions of nonlinear equations: stability issues. Math. Program. (2016). doi:10.1007/s10107-016-1047-x

    MATH  Google Scholar 

  16. Izmailov, A.F., Solodov, M.V.: Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications. Math. Program. 89, 413–435 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  17. Izmailov, A.F., Solodov, M.V.: The theory of 2-regularity for mappings with Lipschitzian derivatives and its applications to optimality conditions. Math. Oper. Res. 27, 614–635 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  18. Izmailov, A.F., Solodov, M.V.: On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions. Math. Program. 117, 271–304 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Izmailov, A.F., Solodov, M.V.: On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers. Math. Program. 126, 231–257 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Izmailov, A.F., Solodov, M.V.: Stabilized SQP revisited. Math. Program. 122, 93–120 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  21. Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering. Springer, Cham (2014)

    Google Scholar 

  22. Izmailov, A.E., Solodov, M.V.: Critical Lagrange multipliers: what we currently know about them, how they spoil our lives, and what we can do about it. TOP 23, 1–26 (2015). (Rejoinder of the discussion: TOP 23 (2015), 48–52)

    Article  MathSciNet  MATH  Google Scholar 

  23. Izmailov, A.F., Uskov, E.I.: Attraction of Newton method to critical Lagrange multipliers: fully quadratic case. Math. Program. 152, 33–73 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)

    MATH  Google Scholar 

  25. Oberlin, C., Wright, S.J.: An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems. Math. Program. 117, 355–386 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  27. Uskov, E.I.: On the attraction of Newton method to critical Lagrange multipliers. Comp. Math. Math. Phys. 53, 1099–1112 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  28. Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11, 253–275 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yamashita, N., Fukushima, M.: On the rate of convergence of the Levenberg–Marquardt method. Computing. Suppl. 15, 237–249 (2001)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank the two anonymous referees for their comments on the original version of this article.

Author information

Authors and Affiliations

  1. VMK Faculty, OR Department, Lomonosov Moscow State University (MSU), Uchebniy Korpus 2, Leninskiye Gory, Moscow, 119991, Russia

    A. F. Izmailov

  2. Peoples’ Friendship University of Russia, Miklukho-Maklaya Str. 6, Moscow, 117198, Russia

    A. F. Izmailov

  3. Department of Mathematics, Physics and Computer Sciences, Derzhavin Tambov State University, TSU, Internationalnaya 33, Tambov, 392000, Russia

    A. S. Kurennoy

  4. IMPA—Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, 22460-320, Brazil

    M. V. Solodov

Authors
  1. A. F. Izmailov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. S. Kurennoy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. V. Solodov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. V. Solodov.

Additional information

This research is supported in part by the Russian Foundation for Basic Research Grant 17-01-00125, by the Russian Science Foundation Grant 15-11-10021, by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.a03.21.0008), by VolkswagenStiftung Grant 115540, by CNPq Grants PVE 401119/2014-9 and 303724/2015-3, and by FAPERJ.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Izmailov, A.F., Kurennoy, A.S. & Solodov, M.V. Critical solutions of nonlinear equations: local attraction for Newton-type methods. Math. Program. 167, 355–379 (2018). https://doi.org/10.1007/s10107-017-1128-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-017-1128-5

Keywords

Mathematics Subject Classification

Search

Navigation