Skip to main content
SpringerLink
Log in

The Josephy–Newton Method for Semismooth Generalized Equations and Semismooth SQP for Optimization

  • Published:
Set-Valued and Variational Analysis Aims and scope Submit manuscript

Abstract

While generalized equations with differentiable single-valued base mappings and the associated Josephy–Newton method have been studied extensively, the setting with semismooth base mapping had not been previously considered (apart from the two special cases of usual nonlinear equations and of Karush–Kuhn–Tucker optimality systems). We introduce for the general semismooth case appropriate notions of solution regularity and prove local convergence of the corresponding Josephy–Newton method. As an application, we immediately recover the known primal-dual local convergence properties of semismooth sequential quadratic programming algorithm (SQP), but also obtain some new results that complete the analysis of the SQP primal rate of convergence, including its quasi-Newton variant.

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

Access this article

Log in via an institution

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. Andreani, R., Birgin, E., Martínez, J., Schuverdt, M.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Boggs, B., Tolle, J.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1996)

    Article  MathSciNet  Google Scholar 

  3. Bonnans, J.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006)

    MATH  Google Scholar 

  5. Bonnans, J., Sulem, A.: Pseudopower expansion of solutions of generalized equations and constrained optimization. Math. Program. 70, 123–148 (1995)

    MathSciNet  MATH  Google Scholar 

  6. Dontchev, A., Rockafellar, R.: Newton’s method for generalized equations: a sequential implicit function theorem. Math. Program. 123, 139–159 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fabian, M., Preiss, D.: On the Clarke’s generalized Jacobian. In: Proceedings of the 14th Winter School on Abstract Analysis. Circolo Matematico di Palermo, Palermo (1987). Rendiconti del Circolo Matematico di Palermo, Ser. II, Number 4, pp. 305–307

  8. Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

    Google Scholar 

  9. Fernández, D., Izmailov, A., Solodov, M.: Sharp primal superlinear convergence results for some Newtonian methods for constrained optimization. SIAM J. Optim. 20, 3312–3334 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Han, J., Sun, D.: Superlinear convergence of approximate Newton methods for LC1 optimization problems without strict complementarity. In: Du, D.-Z., Qi, L., Womersley, R.S. (eds.) Recent Advances in Nonsmooth Optimization, vol. 58, pp. 353–367. World Scientific Publishing Co, Singapore (1993)

    Google Scholar 

  11. Izmailov, A., Pogosyan, A., Solodov, M.: Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Comput. Optim. Appl. 51, 199–221 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  12. Izmailov, A., Solodov, M.: 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 

  13. Izmailov, A., Solodov, M.: Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization. Comput. Optim. Appl. 46, 347–368 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Izmailov, A., Solodov, M.: A truncated SQP method based on inexact interior-point solutions of subproblems. SIAM J. Optim. 20, 2584–2613 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Josephy, N.: Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin (1979)

  16. Josephy, N.: Quasi-Newton methods for generalized equations. Technical Summary Report 1966, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin (1979)

  17. Klatte, D., Tammer, K.: On the second order sufficient conditions to perturbed C1, 1 optimization problems. Optimization 19, 169–180 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kummer, B.: Newton’s Method for Nondifferentiable Functions, vol. 45, pp. 114–125. Akademie, Berlin (1988)

    Google Scholar 

  19. Kummer, B.: Newton’s Method Based on Generalized Derivatives for Nonsmooth Functions, pp. 171–194. Springer, Berlin (1992)

    Google Scholar 

  20. Mordukhovich, B.: Stability theory for parametric generalized equations and variational inequalities via nonsmooth analysis. Trans. Am. Math. Soc 343, 609–657 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  21. Mordukhovich, B.: Variational Analysis and Generalized Differentiation. Springer, Berlin (2006)

    Google Scholar 

  22. Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006)

    MATH  Google Scholar 

  23. Pang, J.S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  24. Qi, L.: LC1 Functions and LC1 Optimization Problems. Technical Report AMR 91/21, School of Mathematics, The University of New South Wales, Sydney (1991)

  25. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  26. Qi, L.: Superlinearly convergent approximate Newton methods for LC1 optimization problems. Math. Program. 64, 277–294 (1994)

    Article  MATH  Google Scholar 

  27. Qi, L., Jiang, H.: Semismooth Karush–Kuhn–Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations. Math. Oper. Res. 22, 301–325 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  28. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  29. Robinson, S.: Strongly regular generalized equations. Math. Oper. Res. 5, 43–62 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  30. Rockafellar, R.: Computational schemes for solving large-scale problems in extended linear-quadratic programming. Math. Program. 48, 447–474 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  31. Rockafellar, R., Wets, J.: Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time. SIAM J. Control Optim. 28, 810–922 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  32. Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Program. 131, 71–94 (2012). doi:10.1007/s10107-010-0345-y

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Alexey F. Izmailov & Alexey S. Kurennoy

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

    Mikhail V. Solodov

Authors
  1. Alexey F. Izmailov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexey S. Kurennoy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mikhail V. Solodov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mikhail V. Solodov.

Additional information

Research of the first two authors is supported by the Russian Foundation for Basic Research Grant 10-01-00251. The third author is supported in part by CNPq Grant 302637/2011-7, by PRONEX–Optimization, and by FAPERJ.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Izmailov, A.F., Kurennoy, A.S. & Solodov, M.V. The Josephy–Newton Method for Semismooth Generalized Equations and Semismooth SQP for Optimization. Set-Valued Var. Anal 21, 17–45 (2013). https://doi.org/10.1007/s11228-012-0218-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11228-012-0218-z

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation