Skip to main content
SpringerLink
Log in

Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

Abstract

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve fast convergence despite possible degeneracy of constraints of optimization problems, when the Lagrange multipliers associated to a solution are not unique. Superlinear convergence of sSQP had been previously established under the strong second-order sufficient condition for optimality (without any constraint qualification assumptions). We prove a stronger superlinear convergence result than the above, assuming the usual second-order sufficient condition only. In addition, our analysis is carried out in the more general setting of variational problems, for which we introduce a natural extension of sSQP techniques. In the process, we also obtain a new error bound for Karush–Kuhn–Tucker systems for variational problems that holds under an appropriate second-order condition.

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. Boggs B., Tolle J.: Sequential quadratic programming. Acta Numerica 4, 1–51 (1996)

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  3. Facchinei F., Fischer A., Kanzow C.: On the accurate identification of active constraints. SIAM J. Optim. 9, 14–32 (1999)

    Article  MathSciNet  Google Scholar 

  4. Facchinei F., Pang J.S.: Finite-dimensional variational inequalities and complementarity problems. Springer, New York (2003)

    Google Scholar 

  5. Fischer A.: Local behavior of an iterative framework for generalized equations with nonisolated solutions. Math. Program. 94, 91–124 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Guignard M.: Generalized Kuhn–Tucker conditions for mathematical programming problems in a Banach space. SIAM J. Control 7, 232–241 (1969)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  8. Hager W., Gowda M.: Stability in the presence of degeneracy and error estimation. Math. Program. 85, 181–192 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  9. Izmailov A., Solodov M.: Karush–Kuhn–Tucker systems: regularity conditions, error bounds and a class of Newton-type methods. Math. Program. 95, 631–650 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Izmailov A., Solodov M.: Newton-type methods for optimization problems without constraint qualifications. SIAM J. Optim. 16, 210–228 (2004)

    Article  MathSciNet  Google Scholar 

  11. Izmailov, A.F., Solodov, M.V.: Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints. Comput. Optim. Appl. (2007). doi:10.1007/s10589-007-9074-4

  12. 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  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  14. Li, D.H., Qi, L.: A stabilized SQP method via linear equations. Tech. Rep. Applied mathematics technical report AMR00/5, The University of New South Wales (2000)

  15. Pang J.S.: Error bounds in mathematical programming. Math. Program. 79, 299–332 (1997)

    Google Scholar 

  16. Robinson S.: Some continuity properties of polyhedral multifunctions. Math. Program. Study 14, 206–214 (1981)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  18. Wright S.: Modifying SQP for degenerate problems. SIAM J. Optim. 13, 470–497 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Wright S.: Constraint identification and algorithm stabilization for degenerate nonlinear programs. Math. Program. 95, 137–160 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  20. Wright S.: An algorithm for degenerate nonlinear programming with rapid local convergence. SIAM J. Optim. 15, 673–696 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Author notes

  1. Damián Fernández

    Present address: IMECC-UNICAMP, State University of Campinas, CP 6065, Campinas, SP, 13081-970, Brazil

Authors and Affiliations

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

    Damián Fernández

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

    Mikhail Solodov

Authors
  1. Damián Fernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mikhail Solodov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Damián Fernández.

Rights and permissions

Reprints and permissions

About this article

Cite this article

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). https://doi.org/10.1007/s10107-008-0255-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-008-0255-4

Keywords

Mathematics Subject Classification (2000)

Search

Navigation