A globally convergent inexact Newton method for systems of monotone equations. (English) Zbl 0928.65059

Solodov, Michael V.; Svaiter, Benav F.

Fukushima, Masao (ed.) et al., Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods. Session in the 16th international symposium on Mathematical programming (ismp97) held at Lausanne EPFL, Switzerland, August 24–29, 1997. Boston: Kluwer Academic Publishers. Appl. Optim. 22, 355-369 (1999).

Summary: 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 by the authors [A hybrid projection-proximal point algorithm. J. Convex Anal. 6, No. 1, 59–70 (1999; Zbl 0961.90128)].
For the entire collection see [Zbl 0909.00046].

MSC:

65H10	Numerical computation of solutions to systems of equations
90C53	Methods of quasi-Newton type

Keywords:

Newton method; proximal point method; projection method; global convergence; superlinear convergence; algorithm; systems of monotone equations

Citations:

Zbl 0961.90128