Abstract
This paper presents some new results in the theory of Newton-type methods for variational inequalities, and their application to nonlinear programming. A condition of semistability is shown to ensure the quadratic convergence of Newton's method and the superlinear convergence of some quasi-Newton algorithms, provided the sequence defined by the algorithm exists and converges. A partial extension of these results to nonsmooth functions is given. The second part of the paper considers some particular variational inequalities with unknowns (x, λ), generalizing optimality systems. Here only the question of superlinear convergence of {x k} is considered. Some necessary or sufficient conditions are given. Applied to some quasi-Newton algorithms they allow us to obtain the superlinear convergence of {x k}. Application of the previous results to nonlinear programming allows us to strengthen the known results, the main point being a characterization of the superlinear convergence of {x k} assuming a weak second-order condition without strict complementarity.
Similar content being viewed by others
References
Ben-Tal A (1980) Second-order and related extremality conditions in nonlinear programming. J Optim Theory Appl 21:143–165
Bertsekas DP (1982) Constrained Optimization and Lagrange Multipliers Methods. Academic Press, New York
Boggs PT, Tolle JW, Wang P (1982) On the local convergence of quasi-Newton methods for constrained optimization. SIAM J Control Optim 20:161–171
Bonnans JF (1989) Local study of Newton-type algorithms for constrained problems. Proc 5th Franco-German Conf on Optimization, Dolecki S, ed. Lectures Notes in Mathematics, vol 1405. Springer-Verlag, Berlin, pp 13–24
Bonnans JF, Launay G (1992) An implicit trust region algorithm for constrained optimization. INRIA Report.
Brézis H (1973) Opérateurs maximaux monotones. North-Holland, Amsterdam
Broyden CG, Dennis JE, Moré JJ (1973) On the local and superlinear convergence of quasi-Newton methods. J Inst Math Applic 12:223–245
Dennis JE, Moré JJ (1974) A characterization of superlinear convergence and its application to quasi-Newton methods. Math Comput 28:549–560
Dennis JE, More JJ (1977) Quasi-Newton methods, motivation and theory. SIAM Rev 19:46–89
Fletcher R (1987) Practical Methods of Optimization, 2nd edn. Wiley, Chichester
Gabay D (1982) Application de la méthode des multiplicateurs aux inéquations variationnelles. In: Méthodes de lagrangien augmenté, Fortin M, Glowinski R, eds. Dunod, Paris, pp 279–308
Grzegòrski SM (1985) Orthogonal projections on convex sets for Newton-like methods, SIAM J Numer Anal 22:1208–1219
Harker PT, Pang JS (1990) Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math Programming 48:161–220
Josephy NH (1979) Newton's method for generalized equations. Technical Summary Report No 1965, Mathematics Research Center, University of Wisconsin-Madison
Josephy NH (1979) Quasi-Newton methods for generalized equations. Summary Report No 1966, Mathematics Research Center, University of Wisconsin-Madison
Lions JL, Stampacchia G (1967) Variational inequalities. Comm Pure Appl Math 20:493–519
Mangasarian OL, Fromovitz S (1967) The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J Math Anal Appl 17:37–47
Reinoza A (1985) The strong positivity condition. Math Oper Res 10:54–62
Robinson SM (1980) Strongly regular generalized equations. Math Oper Res 5:43–62
Robinson SM (1982) Generalized equations and their applications, part II: application to nonlinear programming. Math Programming Stud 19:200–221
Robinson SM (1983) Generalized equations. In: Mathematical Programming, the State of the Art, Bachem A, Grötschel M, Korte B, eds. Springer-Verlag, New York, pp 346–367
Robinson SM (1987) Local structure of feasible sets in nonlinear programming, part III: stability and sensitivity. Math Programming Stud 30:45–66
Robinson SM (to appear) Newton's method for a class of nonsmooth functions
Shapiro A (1990) On concepts of directional differentiability. J Optim Theory Appl 66:477–487
Author information
Authors and Affiliations
Additional information
Communicated by J. Stoer
Rights and permissions
About this article
Cite this article
Bonnans, J.F. Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl Math Optim 29, 161–186 (1994). https://doi.org/10.1007/BF01204181
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01204181
Key words
- Variational inequalities
- Nonlinear programming
- Successive
- quadratic programming superlinear convergence