Differential
Inclusions, Control and Optimization 20 (2000) 209-244

doi: 10.7151/dmdico.1013

Bernd Kummer

*Humboldt-Universität zu Berlin
Mathematisch-Naturwissenschaftliche Fakultät II
Institut für Mathematik
*

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.

**Keywords:** nonsmooth functions, generalized Newton methods, critical points,
complementarity, SQP methods, inverse mappings, regularity.

**1991 Mathematics Subject Classification:** 90C31, 90C48, 70H30.

[1] | J.P. Aubin and I. Ekeland, Applied Nonlinear Analysis, Wiley, New York 1984. |

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

[3] | F.H. Clarke, On the inverse function theorem, Pacific Journ. Math. 64
(1) (1976), 97-102. |

[4] | R. Cominetti, Metric Regularity, Tangent Sets, and Second-Order Optimality
Conditions, Appl. Math. Optim. 21 (1990), 265-287. |

[5] | A.L. Dontchev, Local convergence of the Newton method for generalized equations,
C.R. Acad. Sc. Paris 332 Ser. I (1996), 327-331. |

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

[7] | A. Fischer, Solutions of monotone complementarity problems with locally
Lipschitzian functions, Math. Progr. B 76 (3) (1997), 513-532. |

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

[9] | C.M. Ip and J. Kyparisis, Local convergence of quasi-Newton methods for
B-diffenrentialble equations, MP 56 (1992), 71-89. |

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

[11] | H.Th. Jongen, D. Klatte and K. Tammer, Implicit functions and sensitivity of
stationary points, Math. Programming 49 (1990), 123-138. |

[12] | C. Kanzow, N. Yamashita and M. Fukushima, New NCP-function and their properties,
JOTA 94 (1997), 115-135. |

[13] | A. Kaplan, On the convergence of the penalty function method, Soviet Math.
Dokl. 17 (4) (1976), 1008-1012. |

[14] | A. King and R.T. Rockafellar, Sensitivity analysis for nonsmooth generalized
equations, MP 55 (1992), 341-364. |

[15] | D. Klatte and B. Kummer, Strong stability in nonlinear programming revisited,
J. Australian Mathem. Soc. Ser. B 40 (1999), 336-352. |

[16] | D. Klatte and B. Kummer, Generalized Kojima functions and Lipschitz stability of
critical points, Computational Otimization and Appl. 13 (1999), 61-85. |

[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] | M. Kojima and S. Shindo, Extensions of Newton and quasi- Newton methods to systems
of PC, Journ. of Operations Research Soc. of Japan ^{1} equations29
(1987), 352-374. |

[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] | B. Kummer, Lipschitzian Inverse Functions, Directional Derivatives and Application
in C, Journal of Optimization Theory and Appl. ^{1.1}-Optimization70
(3) (1991), 559-580. |

[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] | 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. |

[23] | B. Kummer, Metric Regularity: Characterizations, Nonsmooth Variations and
Successive Approximation, Optimization 46 (1999), 247-281. |

[24] | R. Miffin, Semismooth and semiconvex functions in constrained optimization,
SIAM J. Control and Optim. 15 (1977), 957-972. |

[25] | B.S. Mordukhovich, Complete characterization of opennes, metric regularity and
Lipschitzian properties of maps, Trans. Amer. Math. Soc. 340 (1993), 1-35. |

[26] | J.-S. Pang and Liqun Qi, Nonsmooth equations: motivation and algorithms, SIAM
J. Optimization 3 (1993), 443-465. |

[27] | J.-S. Pang, Newton's method for B-differentiable equations, Mathematics of OR 15
(1990), 311-341. |

[28] | J.-P. Penot, Metric Regularity, openness and Lipschitz behavior of multifunctions,
Nonlin. Analysis 13 (1989), 629-643. |

[29] | L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Programming 58
(1993), 353-367. |

[30] | D. Ralph and S. Scholtes, Sensitivity analysis of composite piecewise smooth
equations, Math. Progr. B 76 (3) (1997), 593-612. |

[31] | S.M. Robinson, Strongly regular generalized equations, Math. Oper. Res. 5
(1980), 43-62. |

[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] | R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton 1970. |

[34] | D. Sun and L. Qi, On NCP functions, Computational Optimization and Appl. 13
(1999), 201-220. |

[35] | L. Thibault, Subdifferentials of compactly Lipschitzian vector-valued functions,
Ann. Mat. Pura Appl. (4) 125 (1980), 157-192. |

Received 20 December 1999

Revised 19 May 2000