Generalized Newton and NCP-methods: convergence, regularity, actions

Bernd Kummer

Discussiones Mathematicae, Differential Inclusions, Control and Optimization (2000)

  • Volume: 20, Issue: 2, page 209-244
  • ISSN: 1509-9407

Abstract

top
Solutions of several problems can be modelled as solutions of nonsmooth equations. Then, Newton-type methods for solving such equations induce particular iteration steps (actions) and regularity requirements in the original problems. We study these actions and requirements for nonlinear complementarity problems (NCP's) and Karush-Kuhn-Tucker systems (KKT) of optimization models. We demonstrate their dependence on the applied Newton techniques and the corresponding reformulations. In this way, connections to SQP-methods, to penalty-barrier methods and to general properties of so-called NCP-functions are shown. Moreover, direct comparisons of the hypotheses and actions in terms of the original problems become possible. Besides, we point out the possibilities and bounds of such methods in dependence of smoothness.

How to cite

top

Bernd Kummer. "Generalized Newton and NCP-methods: convergence, regularity, actions." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 20.2 (2000): 209-244. <http://eudml.org/doc/271515>.

@article{BerndKummer2000,
abstract = {Solutions of several problems can be modelled as solutions of nonsmooth equations. Then, Newton-type methods for solving such equations induce particular iteration steps (actions) and regularity requirements in the original problems. We study these actions and requirements for nonlinear complementarity problems (NCP's) and Karush-Kuhn-Tucker systems (KKT) of optimization models. We demonstrate their dependence on the applied Newton techniques and the corresponding reformulations. In this way, connections to SQP-methods, to penalty-barrier methods and to general properties of so-called NCP-functions are shown. Moreover, direct comparisons of the hypotheses and actions in terms of the original problems become possible. Besides, we point out the possibilities and bounds of such methods in dependence of smoothness.},
author = {Bernd Kummer},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
keywords = {nonsmooth functions; generalized Newton methods; critical points; complementarity; SQP methods; inverse mappings; regularity; nonlinear complementarity problems; nonsmooth equations; Newton-type methods; Karush-Kuhn-Tucker systems; SQP-methods; penalty-barrier methods; NCP-functions; dependence of smoothness},
language = {eng},
number = {2},
pages = {209-244},
title = {Generalized Newton and NCP-methods: convergence, regularity, actions},
url = {http://eudml.org/doc/271515},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Bernd Kummer
TI - Generalized Newton and NCP-methods: convergence, regularity, actions
JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization
PY - 2000
VL - 20
IS - 2
SP - 209
EP - 244
AB - Solutions of several problems can be modelled as solutions of nonsmooth equations. Then, Newton-type methods for solving such equations induce particular iteration steps (actions) and regularity requirements in the original problems. We study these actions and requirements for nonlinear complementarity problems (NCP's) and Karush-Kuhn-Tucker systems (KKT) of optimization models. We demonstrate their dependence on the applied Newton techniques and the corresponding reformulations. In this way, connections to SQP-methods, to penalty-barrier methods and to general properties of so-called NCP-functions are shown. Moreover, direct comparisons of the hypotheses and actions in terms of the original problems become possible. Besides, we point out the possibilities and bounds of such methods in dependence of smoothness.
LA - eng
KW - nonsmooth functions; generalized Newton methods; critical points; complementarity; SQP methods; inverse mappings; regularity; nonlinear complementarity problems; nonsmooth equations; Newton-type methods; Karush-Kuhn-Tucker systems; SQP-methods; penalty-barrier methods; NCP-functions; dependence of smoothness
UR - http://eudml.org/doc/271515
ER -

References

top
  1. [1] J.P. Aubin and I. Ekeland, Applied Nonlinear Analysis, Wiley, New York 1984. Zbl0641.47066
  2. [2] S.C. Billups and M.C. Ferris, QPCOMP: A quadratic programming based solver for mixed complementarity problems, Math. Progr. B 76 (3) (1997), 533-562. Zbl0873.90095
  3. [3] F.H. Clarke, On the inverse function theorem, Pacific Journ. Math. 64 (1) (1976), 97-102. Zbl0331.26013
  4. [4] R. Cominetti, Metric Regularity, Tangent Sets, and Second-Order Optimality Conditions, Appl. Math. Optim. 21 (1990), 265-287. Zbl0692.49018
  5. [5] A.L. Dontchev, Local convergence of the Newton method for generalized equations, C.R. Acad. Sc. Paris 332 Ser. I (1996), 327-331. Zbl0844.47034
  6. [6] A.L. Dontchev and R.T. Rockafellar, Characterizations of Strong Regularity for Variational Inequalities over Polyhedral Convex Sets, SIAM J. Optimization 6 (1996), 1087-1105. Zbl0899.49004
  7. [7] A. Fischer, Solutions of monotone complementarity problems with locally Lipschitzian functions, Math. Progr. B 76 (3) (1997), 513-532. Zbl0871.90097
  8. [8] P.T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming 48 (1990), 161-220. Zbl0734.90098
  9. [9] C.M. Ip and J. Kyparisis, Local convergence of quasi-Newton methods for B-diffenrentialble equations, MP 56 (1992), 71-89. Zbl0761.90088
  10. [10] V. Jeyakumar, D.T. Luc and S. Schaible, Characterization of generalized monotone nonsmooth continuous map using approximate Jacobians, J. Convex Analysis 5 (1) (1998), 119-132. Zbl0911.49014
  11. [11] H.Th. Jongen, D. Klatte and K. Tammer, Implicit functions and sensitivity of stationary points, Math. Programming 49 (1990), 123-138. Zbl0715.65034
  12. [12] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-function and their properties, JOTA 94 (1997), 115-135. Zbl0886.90146
  13. [13] A. Kaplan, On the convergence of the penalty function method, Soviet Math. Dokl. 17 (4) (1976), 1008-1012. Zbl0357.90050
  14. [14] A. King and R.T. Rockafellar, Sensitivity analysis for nonsmooth generalized equations, MP 55 (1992), 341-364. Zbl0766.90075
  15. [15] D. Klatte and B. Kummer, Strong stability in nonlinear programming revisited, J. Australian Mathem. Soc. Ser. B 40 (1999), 336-352. Zbl0926.90084
  16. [16] D. Klatte and B. Kummer, Generalized Kojima functions and Lipschitz stability of critical points, Computational Otimization and Appl. 13 (1999), 61-85. Zbl1017.90104
  17. [17] M. Kojima, Strongly stable stationary solutions in nonlinear programs, in: Analysis and Computation of Fixed Points, S.M. Robinson ed., Academic Press, New York (1980), 93-138. 
  18. [18] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems of PC¹ equations, Journ. of Operations Research Soc. of Japan 29 (1987), 352-374. Zbl0611.65032
  19. [19] B. Kummer, Newton's method for non-differentiable functions, in: Advances in Math. Optimization, J. Guddat et al. ed., Akademie Verlag Berlin, Ser. Mathem. Res. 45 (1988), 114-125. 
  20. [20] B. Kummer, Lipschitzian Inverse Functions, Directional Derivatives and Application in C 1 . 1 -Optimization, Journal of Optimization Theory and Appl. 70 (3) (1991), 559-580. 
  21. [21] B. Kummer, Newton's method based on generalized derivatives for nonsmooth functions: Convergence Analysis, in: Lecture Notes in Economics and Mathematical Systems 382; Advances in Optimization; W. Oettli, D. Pallaschke (eds.), Springer, Berlin (1992), 171-194. 
  22. [22] B. Kummer, Lipschitzian and Pseudo-Lipschitzian Inverse Functions and Applications to Nonlinear Optimization, Lecture Notes in Pure and Applied Mathematics 195 (1997) (Math. Programming with Data Perturbations, ed. A.V. Fiacco), 201-222. Zbl0894.49013
  23. [23] B. Kummer, Metric Regularity: Characterizations, Nonsmooth Variations and Successive Approximation, Optimization 46 (1999), 247-281. Zbl0991.90125
  24. [24] R. Miffin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control and Optim. 15 (1977), 957-972. 
  25. [25] B.S. Mordukhovich, Complete characterization of opennes, metric regularity and Lipschitzian properties of maps, Trans. Amer. Math. Soc. 340 (1993), 1-35. Zbl0791.49018
  26. [26] J.-S. Pang and Liqun Qi, Nonsmooth equations: motivation and algorithms, SIAM J. Optimization 3 (1993), 443-465. 
  27. [27] J.-S. Pang, Newton's method for B-differentiable equations, Mathematics of OR 15 (1990), 311-341. Zbl0716.90090
  28. [28] J.-P. Penot, Metric Regularity, openness and Lipschitz behavior of multifunctions, Nonlin. Analysis 13 (1989), 629-643. Zbl0687.54015
  29. [29] L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Programming 58 (1993), 353-367. Zbl0780.90090
  30. [30] D. Ralph and S. Scholtes, Sensitivity analysis of composite piecewise smooth equations, Math. Progr. B 76 (3) (1997), 593-612. Zbl0871.90094
  31. [31] S.M. Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980), 43-62. Zbl0437.90094
  32. [32] S.M. Robinson, Newton's method for a class of nonsmooth functions, Working Paper, (Aug. 1988) Univ. of Wisconsin-Madison, Department of Industrial Engineering, Madison, WI 53706; in Set-Valued Analysis 2 (1994), 291-305. 
  33. [33] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton 1970. Zbl0193.18401
  34. [34] D. Sun and L. Qi, On NCP functions, Computational Optimization and Appl. 13 (1999), 201-220. Zbl1040.90544
  35. [35] L. Thibault, Subdifferentials of compactly Lipschitzian vector-valued functions, Ann. Mat. Pura Appl. (4) 125 (1980), 157-192. Zbl0486.46037

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.