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

Kummer, Bernd

Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 20 (2000) no. 2, pp. 209-244.

Résumé

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.

Détail

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

Bibliographie

[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¹ equations, Journ. of Operations Research Soc. of Japan 29 (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^{1.1}$-Optimization, Journal of Optimization Theory and Appl. 70 (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.