Abstract
We propose an algorithm for solving systems of monotone equations which combines Newton, proximal point, and projection methodologies. An important property of the algorithm is that the whole sequence of iterates is always globally convergent to a solution of the system without any additional regularity assumptions. Moreover, under standard assumptions the local superlinear rate of convergence is achieved. As opposed to classical globalization strategies for Newton methods, for computing the stepsize we do not use linesearch aimed at decreasing the value of some merit function. Instead, linesearch in the approximate Newton direction is used to construct an appropriate hyperplane which separates the current iterate from the solution set. This step is followed by projecting the current iterate onto this hyperplane, which ensures global convergence of the algorithm. Computational cost of each iteration of our method is of the same order as that of the classical damped Newton method. The crucial advantage is that our method is truly globally convergent. In particular, it cannot get trapped in a stationary point of a merit function. The presented algorithm is motivated by the hybrid projection-proximal point method proposed in [25].
Research of the first author is supported by CNPq Grant 300734/95-6 and by PRONEX-Optimization, research of the second author is supported by CNPq Grant 301200/93-9(RN) and by PRONEX-Optimization.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16: 1–3, 1966.
D.P. Bertsekas. Nonlinear programming. Athena Scientific, Belmont, Massachusetts, 1995.
J.V. Burke and Maijian Qian. The variable metric proximal point algorithm, I: Basic convergence theory, 1996. Department of Mathematics, University of Washington, Seattle, WA.
R.S. Dembo, S.0 Eisenstat, and T. Steihaug. Inexact Newton methods. SIAM Journal of Numerical Analysis, 19: 400–408, 1982.
J.E. Dennis and R.B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, N.J., 1983.
J. Eckstein and D.P. Bertsekas. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55: 293–318, 1992.
J. Eckstein and M.C. Ferris. Smooth methods of multipliers for cornplementarity problems. Technical Report RRR 27–96, Rutgers Center for Operations Research, Rutgers University, New Brunswick, New Jersey, August 1996. Revised February 1997.
M.C. Ferris. Finite termination of the proximal point algorithm. Mathematical Programming, 50: 359–366, 1991.
A.N. Iusem and M.V. Solodov. Newton-type methods with generalized distances for constrained optimization. Optimization, 41: 257–278, 1997.
H. Jiang, L. Qi, X. Chen, and D. Sun. Semismoothness and superlinear copnvergence in nonsmooth optimization and nonsmooth equations. In G. Di Pillo and F. Giannessi, editors, Nonlinear Optimization and Applications, pages 197–212. Plenum Press, 1996.
H. Jiang and D. Ralph. Global and local superlinear convergence analysis of Newton-type methods for semismooth equations with smooth least squares. Department of Mathematics, The University of Melbourne, Australia. July 1997.
B. Lemaire. The proximal algorithm. In J.P. Penot, editor, International Series of Numerical Mathematics, pages 73–87. Birkhauser, Basel, 1989.
F.J. Luque. Asymptotic convergence analysis of the proximal point algorithm. SIAM Journal on Control and Optimization, 22: 277–293, 1984.
J.M. Martínez. Local convergence theory for inexact Newton methods based on structural least-squares updates. Mathematics of Computation, 55: 143–168, 1990.
J.M. Martinez and L. Qi. Inexact Newton methods for solving nonsm000th equations. Journal of Computational and Applied Mathematics, 60: 127145, 1995.
J.M. Ortega and W.C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, 1970.
J.-S. Pang and S.A. Gabriel. An inexact NE/SQP method for solving the nonlinear complementarity problem. Computational Optimization and Applications, 1: 67–92, 1992.
J.-S. Pang and L. Qi. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 3: 443–465, 1995.
B.T. Polyak. Introduction to Optimization. Optimization Software, Inc., Publications Division, New York, 1987.
L. Qi. Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 18: 227–244, 1993.
L. Qi and J. Sun. A nonsmooth version of Newton’s method. Mathematical Programming, 58: 353–367, 1993.
R.T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14: 877–898, 1976.
M.V. Solodov and B.F. Svaiter. A new projection method for variational inequality problems. Technical Report B-109, Instituto de Matematica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460, Brazil, November 1996. SIAM Journal on Control and Optimization,submitted.
M.V. Solodov and B.F. Svaiter. Forcing strong convergence of proximal point iterations in a Hilbert space, 1997. Mathematical Programming,submitted.
M.V. Solodov and B.F. Svaiter. A hybrid projection - proximal point algorithm. Technical Report B-115, Instituto de Matematica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, Ri 22460, Brazil, January 1997. Journal of Convex Analysis,submitted.
T.J. Ypma. Local convergence of inexact Newton methods. SIAM Journal of Numerical Analysis, 21: 583–590, 1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Solodov, M.V., Svaiter, B.F. (1998). A Globally Convergent Inexact Newton Method for Systems of Monotone Equations. In: Fukushima, M., Qi, L. (eds) Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Applied Optimization, vol 22. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-6388-1_18
Download citation
DOI: https://doi.org/10.1007/978-1-4757-6388-1_18
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4419-4805-2
Online ISBN: 978-1-4757-6388-1
eBook Packages: Springer Book Archive