Skip to main content

Advertisement

SpringerLink
Log in

On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

Abstract

Assuming that the primal part of the sequence generated by a Newton-type (e.g., SQP) method applied to an equality-constrained problem converges to a solution where the constraints are degenerate, we investigate whether the dual part of the sequence is attracted by those Lagrange multipliers which satisfy second-order sufficient condition (SOSC) for optimality, or by those multipliers which violate it. This question is relevant at least for two reasons: one is speed of convergence of standard methods; the other is applicability of some recently proposed approaches for handling degenerate constraints. We show that for the class of damped Newton methods, convergence of the dual sequence to multipliers satisfying SOSC is unlikely to occur. We support our findings by numerical experiments. We also suggest a simple auxiliary procedure for computing multiplier estimates, which does not have this undesirable property. Finally, some consequences for the case of mixed equality and inequality constraints are discussed.

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. Anitescu, M.: Nonlinear programs with unbounded Lagrange multiplier sets. Preprint ANL/MCS-P796-0200, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne (2000)

  2. Anitescu M. (2005). On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15: 1203–1236

    Article  MATH  MathSciNet  Google Scholar 

  3. Anitescu, M., Tseng, P., Wright, S.J.: Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math. Program. (in press)

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

    MATH  Google Scholar 

  5. Arutyunov A.V. (1992). Optimality conditions of higher order for abnormal minimization problems. Siberian Math. J. 33: 557–565

    Article  MathSciNet  Google Scholar 

  6. Bonnans J.F. and Shapiro A. (2000). Perturbation Analysis of Optimization Problems. Springer, New York

    MATH  Google Scholar 

  7. Fischer A. (1999). Modified Wilson’s method for nonlinear programs with nonunique multipliers. Math. Oper. Res. 24: 699–727

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  9. Fletcher R., Leyffer S., Ralph D. and Scholtes S. (2006). Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17: 259–286

    Article  MATH  MathSciNet  Google Scholar 

  10. Golubitsky M. and Schaeffer D.G. (1985). Singularities and Groups in Bifurcation Theory, vol 1. Springer, Heidelberg

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

  14. Izmailov A.F. (2000). 2-Regularity and reversibility of quadratic mappings. Contemporary Math. 272: 127–134

    MathSciNet  Google Scholar 

  15. Izmailov A.F. and Solodov M.V. (2001). Optimality conditions for irregular inequality-constrained problems. SIAM J. Control Optim. 40: 1280–1295

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  17. Izmailov A.F. and Solodov M.V. (2002). Complementarity constraint qualification via the theory of 2-regularity. SIAM J. Optim. 13: 368–385

    Article  MATH  MathSciNet  Google Scholar 

  18. Izmailov A.F. and Solodov M.V. (2004). Newton-type methods for optimization problems without constraint qualifications. SIAM J. Optim. 15: 210–228

    Article  MATH  MathSciNet  Google Scholar 

  19. Izmailov, A.~F., Tretyakov, A.~A.: 2-Regular Solutions of Nonlinear Problems. Theory and Numerical Methods (in Russian). Fizmatlit, Moscow (1999)

  20. Leyffer, S.: MacMPEC: AMPL collection of MPECs. www.mcs.anl.gov/leyffer/MacMPEC/

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

  22. Luo Z.-Q., Pang J.-S. and Ralph D. (1996). Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge

    Google Scholar 

  23. Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. PhD thesis, Imperial College, London (1978)

  24. Robinson, S.M.: False numerical convergence in some generalized Newton methods. In: Equilibrium problems and variational models (Erice, 2000), Nonconvex Optim. Appl., vol. 68, pp 401–416. Kluwer, Norwell (2003)

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

    Article  MATH  MathSciNet  Google Scholar 

  26. Scheel H. and Scholtes S. (2000). Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25: 1–22

    Article  MATH  MathSciNet  Google Scholar 

  27. Scholtes S. and Stöhr M. (1999). Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37: 617–652

    Article  MATH  MathSciNet  Google Scholar 

  28. Scholtes S. and Stöhr M. (2001). How stringent is the linear independence assumption for mathematical programs with complementarity constraints?. Math. Oper. Res. 26: 851–863

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computational Mathematics and Cybernetics, Department of Operations Research, Moscow State University, Leninskiye Gori, GSP-2, 119992, Moscow, Russia

    A. F. Izmailov

  2. 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. 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

Dedicated to Professor Stephen Robinson on the occasion of his 65th birthday. The second author remembers, with a sense of privilege, the courses and advice he received from Professor Robinson during his stay at UW-Madison.

The first author is supported by the Russian Foundation for Basic Research Grant 04-01-00341, by RF President’s Grant NS-9344.2006.1 for the support of leading scientific schools, and by RF President’s Grant MD-2723.2005.1 for the support of young doctors of sciences. The second author is supported by CNPq Grants 301508/2005-4, 490200/2005-2, 550317/2005-8, by PRONEX, and by FAPERJ.

Rights and permissions

Reprints and permissions

About this article

Cite this article

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). https://doi.org/10.1007/s10107-007-0158-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-007-0158-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation