Skip to main content
SpringerLink
Log in

Newton-type methods for constrained optimization with nonregular constraints

  • Published:
Computational Mathematics and Mathematical Physics Aims and scope Submit manuscript

Abstract

The most important classes of Newton-type methods for solving constrained optimization problems are discussed. These are the sequential quadratic programming methods, active set methods, and semismooth Newton methods for Karush-Kuhn-Tucker systems. The emphasis is placed on the behavior of these methods and their special modifications in the case where assumptions concerning constraint qualifications are relaxed or altogether dropped. Applications to optimization problems with complementarity constraints are examined.

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. A. F. Izmailov, “On the Lagrange Methods for Finding Degenerate Solutions of Constrained Optimization Problems,” Zh. Vychisl. Mat. Mat. Fiz. 36, 10–17 (1996).

    MathSciNet  Google Scholar 

  2. S. J. Wright, “Superlinear Convergence of a Stabilized SQP Method to a Degenerate Solution,” Comput. Optimizat. Appl. 11, 253–275 (1998).

    Article  MATH  Google Scholar 

  3. W. W. Hager, “Stabilized Sequential Quadratic Programming,” Comput. Optim. Appl. 12, 253–273 (1999).

    Article  MathSciNet  MATH  Google Scholar 

  4. W. W. Hager and M. S. Gowda, “Stability in the Presence of Degeneracy and Error Estimation,” Math. Program. 85, 181–192 (1999).

    Article  MathSciNet  MATH  Google Scholar 

  5. A. Fischer, “Modified Wilson’s Method for Nonlinear Programs with Nonunique Multipliers,” Math. Oper. Res. 24, 699–727 (1999).

    Article  MathSciNet  MATH  Google Scholar 

  6. L. Qi and Z. Wei, “On the Constant Positive Linear Dependence Condition and Its Application to SQP Methods,” SIAM J. Optim. 10(4), 963–981 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  7. D. Ralph and S. J. Wright, “Superlinear Convergence of an Interior-Point Method Despite Dependent Constraints,” Math. Oper. Res. 25, 179–194 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  8. M. Anitescu, “Degenerate Nonlinear Programming with a Quadratic Growth Condition,” SIAM J. Optim. 10, 1116–1135 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  9. M. Anitescu, Nonlinear Programs with Unbounded Lagrange Multiplier Sets, Preprint No. ANL/MCS-P796-0200, Math. and Comput. Sci. Div., Argonne Nat. Lab. (Argonne, 2000).

  10. D.-H. Li and L. Qi, Stabilized SQP Method via Linear Equations, Technical Report No. AMR00/5 (Univ. New South Wales, Sydney, 2000).

    Google Scholar 

  11. A. Fischer, “Local Behavior of an Iterative Framework for Generalized Equations with Nonisolated Solutions,” Math. Program. 94, 91–124 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  12. M. Anitescu, “A Superlinearly Convergent Sequential Quadratically Constrained Quadratic Programming Algorithm for Degenerate Nonlinear Programming,” SIAM J. Optim. 12, 949–978 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  13. M. Anitescu, “On the Rate of Convergence of Sequential Quadratic Programming with Nondifferentiable Exact Penalty Function in the Presence of Constraint Degeneracy,” Math. Program. 92, 359–386 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  14. S. J. Wright, “Modifying SQP for Degenerate Problems,” SIAM J. Optim. 13, 470–497 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  15. S. J. Wright, “Constraint Identification and Algorithm Stabilization for Degenerate Nonlinear Programs,” Math. Program. 95, 137–160 (2003).

    Article  MathSciNet  MATH  Google Scholar 

  16. A. F. Izmailov, M. V. Solodov, and K. M. Chokparov, “Globally Convergent Newton-Type Algorithms for Optimization Problems without Constraint Qualifications,” in Problems of Modeling and Analysis in Decision-Making (Vychisl. Tsentr Ross. Akad. Nauk, Moscow, 2003), pp. 63–82 [in Russian].

    Google Scholar 

  17. A. F. Izmailov and M. V. Solodov, “Newton-Type Methods for Optimization Problems without Constraint Qualifications,” SIAM J. Optim. 15(1), 210–228 (2004).

    Article  MathSciNet  MATH  Google Scholar 

  18. A. F. Izmailov, “On the Analytical and Numerical Stability of Critical Lagrange Multipliers,” Zh. Vychisl. Mat. Mat. Fiz. 45, 966–982 (2005) [Comput. Math. Math. Phys. 45, 918–929 (2005)].

    MathSciNet  MATH  Google Scholar 

  19. S. J. Wright, “An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence,” SIAM J. Optim. 15, 673–696 (2005).

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  21. J. V. Outrata, M. Kocvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results (Kluwer, Boston, 1998).

    MATH  Google Scholar 

  22. S. Scholtes and M. Stöhr, “Exact Penalization of Mathematical Programs with Equilibrium Constraints,” SIAM J. Control Optim. 37, 617–652 (1999).

    Article  MathSciNet  MATH  Google Scholar 

  23. H. Scheel and S. Scholtes, “Mathematical Programs with Complementarity Constraints: Stationarity, Optimality and Sensitivity,” Math. Oper. Res. 25, 1–22 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  24. M. Anitescu, On Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs, Preprint No. ANL/MCS-P864-1200, Math. and Comput. Sci. Div., Argonne Nat. Lab. (Argonne, 2000).

  25. S. Scholtes and M. Stöhr, “How Stringent Is the Linear Independence Assumption for Mathematical Programs with Complementarity Constraints?” Math. Oper. Res. 26, 851–863 (2001).

    Article  MathSciNet  MATH  Google Scholar 

  26. R. Fletcher, S. Leyffer, D. Ralph, and S. Scholtes, Local Convergence of SQP Methods for Mathematical Programs with Equilibrium Constraints, Numer. Analys. Report No. NA/209, Department of Mathematics, Univ. of Dundee (Dundee, 2002).

    Google Scholar 

  27. M. Anitescu, “On Using the Elastic Mode in Nonlinear Programming Approaches to Mathematical Programs with Complementarity Constraints,” SIAM J. Optim. 15(4), 1203–1236 (2005).

    Article  MathSciNet  MATH  Google Scholar 

  28. M. Anitescu, P. Tseng, and S. J. Wright, Elastic-Mode Algorithms for Mathematical Programs with Equilibrium Constraints: Global Convergence and Stationarity Properties, Preprint No. ANL/MCS-P1242-0405, Math. and Comput. Sci. Div., Argonne Nat. Lab. (Argonne, 2005).

  29. A. F. Izmailov, Sensitivity in Optimization (Fizmatlit, Moscow, 2006) [in Russian].

    Google Scholar 

  30. W. Achtziger and C. Kanzow, Mathematical Programs with Vanishing Constraints: Optimality Conditions and Constraint Qualifications, Preprint No. 263, Würzburg Inst. of Applied Mathematics and Statistics (Würzburg, 2005).

  31. A. F. Izmailov and M. V. Solodov, Numerical Optimization Methods (Fizmatlit, Moscow, 2003) [in Russian].

    MATH  Google Scholar 

  32. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Mir, Moscow, 1975; Academic Press, New York, 1970.

    Google Scholar 

  33. J. F. Bonnans, “Local Analysis of Newton-Type Methods for Variational Inequalities and Nonlinear Programming,” Appl. Math. Optim. 29, 161–186 (1994).

    Article  MathSciNet  MATH  Google Scholar 

  34. F. Facchinei, A. Fischer, and C. Kanzow, “On the Accurate Identification of Active Constraints,” SIAM J. Optim. 9, 14–32 (1999).

    Article  MathSciNet  Google Scholar 

  35. P. E. Gill, W. Murray, and M. Saunders, “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization,” SIAM Rev. 47(1), 14–32 (2005).

    Article  MathSciNet  Google Scholar 

  36. A. F. Izmailov and A. A. Tret’yakov, 2-Regular Solutions of Nonlinear Problems: Theory and Numerical Methods (Fizmatlit, Moscow, 1999) [in Russian].

    MATH  Google Scholar 

  37. O. A. Brezhneva and A. F. Izmailov, “Construction of Defining Systems for Finding Singular Solutions to Nonlinear Equations,” Zh. Vychisl. Mat. Mat. Fiz. 42, 10–22 (2002) [Comput. Math. Math. Phys. 42, 8–19 (2002)].

    MathSciNet  MATH  Google Scholar 

  38. B. N. Pshenichnyi and Yu. M. Danilin, Numerical Methods in Extremum Problems (Nauka, Moscow, 1975) [in Russian].

    Google Scholar 

  39. X. M. Hu and D. Ralph, “Convergence of a Penalty Method for Mathematical Problems with Complementarity Constraints,” J. Optim. Theory Appl. 123, 365–390 (2004).

    Article  MathSciNet  Google Scholar 

  40. R. Fletcher and S. Leyffer, “Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs,” Optim. Meth. Software 19(1), 15–40 (2004).

    Article  MathSciNet  MATH  Google Scholar 

  41. R. Fletcher and S. Leyffer, “Nonlinear Programming Without a Penalty Function,” Math. Program. 91, 239–270 (2002).

    Article  MathSciNet  MATH  Google Scholar 

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

  43. R. Andreani and J. M. Martinez, “On the Solution of Mathematical Programming Problems with Equilibrium Constraints,” Math. Meth. Oper. Res. 54, 345–358 (2001).

    Article  MathSciNet  MATH  Google Scholar 

  44. W. Hock and K. Schittkowski, “Test Examples for Nonlinear Programming Codes,” in Lect. Notes in Econom. and Math. Systems. (Springer, Berlin, 1981), Vol. 187.

    Google Scholar 

  45. A. V. Arutyunov, “Perturbation of Constraint Extremum Value Problems and Necessary Optimality Conditions,” in Itogi Nauki i Tekhn. Matem. Analiz (VINITI, Moscow, 1989), Vol. 27, pp. 147–253 [in Russian].

    Google Scholar 

  46. A. Baccari and A. Trad, “On the Classical Necessary Second-Order Optimality Conditions in the Presence of Equality and Inequality Constraints,” SIAM J. Optim. 15(2), 394–408 (2004).

    Article  MathSciNet  MATH  Google Scholar 

  47. S. M. Robinson, “Generalized Equations and Their Solutions, Part II: Applications to Nonlinear Programming,” Math. Program. Study 19, 200–221 (1982).

    MATH  Google Scholar 

  48. A. V. Arutyunov, Extremum Conditions: Abnormal and Degenerate Problems (Faktorial, Moscow, 1997) [in Russian].

    MATH  Google Scholar 

  49. H. Jiang and D. Ralph, QPECgen, a MATLAB Generator for Mathematical Programs with Quadratic Objectives and Affine Variational Inequality Constraints, Techn. Report, Department of Mathematics, Univ. of Melbourne, (Melbourne, 1997).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computational Mathematics and Cybernetics, Moscow State University, Leninskie gory, Moscow, 119992, Russia

    M. M. Golishnikov & A. F. Izmailov

Authors
  1. M. M. Golishnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. F. Izmailov
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Original Russian Text © M.M. Golishnikov, A.F. Izmailov, 2006, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2006, Vol. 46, No. 8, pp. 1369–1391.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Golishnikov, M.M., Izmailov, A.F. Newton-type methods for constrained optimization with nonregular constraints. Comput. Math. and Math. Phys. 46, 1299–1319 (2006). https://doi.org/10.1134/S0965542506080045

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0965542506080045

Keywords

Search

Navigation