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

Bernd Kummer

Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 20 (2000), p. 209-244 / Harvested from The Polish Digital Mathematics Library

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

Publié le : 2000-01-01

Zbl 1016.90058

EUDML-ID : urn:eudml:doc:271515

Bibliographie

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

[001] [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. | Zbl 0873.90095

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

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

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

[005] [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. | Zbl 0899.49004

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

[007] [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. | Zbl 0734.90098

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

[009] [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. | Zbl 0911.49014

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

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

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

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

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

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

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

[017] [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. | Zbl 0611.65032

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

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

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

[021] [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. | Zbl 0894.49013

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

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

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

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

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

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

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

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

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

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

[032] [33] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton 1970. | Zbl 0193.18401

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

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