Abstract
We give some convergence results on the generalized Newton method (referred to by some authors as Newton's method) and the chord method when applied to generalized equations. The main results of the paper extend the classical Kantorovich results on Newton's method to (nonsmooth) generalized equations. Our results also extend earlier results on nonsmooth equations due to Eaves, Robinson, Josephy, Pang and Chan.
We also propose inner-iterative schemes for the computation of the generalized Newton iterates. These schemes generalize popular iterative methods (Richardson's method, Jacobi's method and the Gauss-Seidel method) for the solution of linear equations and linear complementarity problems and are shown to be convergent under natural generalizations of classical convergence criteria.
Our results are applicable to equations involving single-valued functions and also to a class of generalized equations which includes variational inequalities, nonlinear complementarity problems and some nonsmooth convex minimization problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Baiocchi, “Disequazioni variazionali”,Bolletino dell' Unione Matematica Italiana 18-A (1981) 173–187.
C. Baiocchi and A. Capelo,Variational and Quasivariational Inequalities: Applications to Free Boundary Problems (Wiley, New York, 1984).
H. Brézis, “Problemes unilateraux,”Journal de Mathematique Pures et Appliqueés 5 (1972) 1–168.
H. Brézis,Opérateur Maximaux Monotones et Semi-groupes de Contractions dans les Espaces de Hilbert (North-Holland, Amsterdam, 1973).
F.E. Browder, “Nonlinear maximal monotone operators in Banach spaces”,Mathematische Annalen 176 (1968) 88–113.
M. Chipot,Variational Inequalities and Flow in Porous Media (Springer, New York, 1984).
G. Cohen, “Auxilliary problem principle and decomposition of optimization problems,”Journal of Optimization Theory and Applications 32 (1980) 277–305.
R.W. Cottle, F. Gianessi and J.L. Lions,Variational Inequalities and Complementarity Problems: Theory and Applications (Wiley, New York, 1980).
C.W. Cryer, “The solution of a quadratic programming problem using systematic overrelaxation,”SIAM Journal on Control 9 (1971) 385–392.
J.E. Dennis and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983).
G. Duvuat and J.L. Lions,Inequalities in Physics and Mechanics (Springer, Berlin, 1976).
B.C. Eaves, “A locally quadratic algorithm for computing stationary points,” Technical Report, Department of Operations Research, Stanford University (Stanford, CA, 1978).
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.
C.M. Ip and J. Kyparisis, “Local convergence of quasi-Newton methods for B-differentiable equations,”Mathematical Programming 56 (1992) 71–90.
N.H. Josephy, “Newton's method for generalized equations,” Technical Report No. 1965, Mathematics Research Center, University of Wisconsin (Madison, WI, 1979).
N.H. Josephy, “A Newton method for the PIES energy model,” Technical Report No. 1977, Mathematics Research Center, University of Wisconsin (Madison, WI, 1979).
L.V. Kantorovich and G.P. Akilov,Functional Analysis (Pergamon, New York, 1982).
S. Karamardian, “The complementarity problem,”Mathematical programming 2 (1972) 107–129.
M. Kojima and S. Shindo, “Extensions of Newton and quasi-Newton methods to systems of PC1 equations,”Journal of the Operations Research Society of Japan 29 (1986) 352–374.
J.L. Lions and G. Stampacchia. “Variational inequalities,”Communications in Pure and Applied Mathematics 20 (1967) 493–519.
O.L. Mangasarian, “Solution of symmetric linear complementarity problems by iterative methods,”Journal of Optimization Theory and applications 22 (1977) 465–485.
G.J. Minty, “On the monotonicity of the gradient of a convex function,”Pacific Journal of Mathematics 14 (1964) 243–247.
G.J. Minty, “Monotone (nonlinear) operators in Hilbert space,”Duke Mathematics Journal 29 (1973) 341–346.
J.M. Ortega,Introduction to Parallel and Vector Solution of Linear Systems (Plenum, New York, 1988).
J.M. Ortega and W.C. Rheinboldt,Interative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).
A.M. Ostrowski,Solution of Equations in Euclidean and Banach Spaces (Academic Press, 1973).
J.S. Pang, “Newton's method for B-differentiable equations,”Mathematics of Operations Research 15 (1990) 311–341.
J.S. Pang and D. Chan, “Iterative methods for variational and complementarity problems,”Mathematical Programming 24 (1982) 284–313.
J.S. Pang and L. Qi, “Nonsmooth equations: motivations and algorithms,”SIAM Journal on Optimization 3 (1993) 443–465.
L. Qi, “Convergence analysis of some algorithms for solving non-smooth equations,”Mathematics of Operations Research 18 (1993) 227–244.
S.M. Robinson, “Generalized equations and their solutions. part I: basic theory,”Mathematical Programming Study 10 (1979) 128–141.
S.M. Robinson, “Strongly regular generalized equations.”Mathematics of Operations Research 5 (1980) 43–62.
S.M. Robinson, “Generalized equations,” in: A. Bachem, M. Grëtschel and B. Korte, eds.,Mathematical Programming: the State of the Art (Springer, Berlin, 1982) pp. 346–367.
G. Stampacchia, “Formes bilineares coercitives sur les ensembles convexes,”Comptes Rendus del L'Academie des Science de Paris 258 (1964) 4413–4416.
R.A. Tapia, “The Kantorovich Theorem for Newton's method,”American Mathematical Monthly 78 (1971) 389–392.
L.U. Uko, “The solution of finite dimensional variational inequalities using systematic relaxation,”Journal of the Nigerian Mathematical Society 8 (1989) 61–75.
L.U. Uko, “The generalized Newton's method,”Journal of the Nigerian Mathematical Society 10 (1991) 55–64.
L.U. Uko, “On a class of general strongly nonlinear quasivariational inequalities,”Rivista di Matematica Pura ed Applicata 11 (1992) 47–55.
L.U. Uko, “Remarks on the generalized Newton method,”Mathematical Programming 59 (1993) 405–412.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Uko, L.U. Generalized equations and the generalized Newton method. Mathematical Programming 73, 251–268 (1996). https://doi.org/10.1007/BF02592214
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02592214