Superlinear convergence of a Newton-type algorithm for monotone equations.

*(English)*Zbl 1114.65055Summary: We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in [M. V. Solodov and B. F. Svaiter, in: Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods (Lausanne, 1997), Boston: Kluwer, Appl. Optim. 22, 355–369 (1999; Zbl 0928.65059)] has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs.

##### MSC:

65H10 | Numerical computation of solutions to systems of equations |

90C53 | Methods of quasi-Newton type |

##### Keywords:

Monotone equations; Newton method; global convergence; superlinear convergence; convex minimization
PDF
BibTeX
XML
Cite

\textit{G. Zhou} and \textit{K. C. Toh}, J. Optim. Theory Appl. 125, No. 1, 205--221 (2005; Zbl 1114.65055)

Full Text:
DOI

##### References:

[8] | Kanzow, C., Yamashita, N., and Fukushima, M., Levenberg-Marquardt Methods for Constrained Nonlinear Equations with Strong Local Convergence Properties, Technical Report 2002-007, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, 2002. · Zbl 1064.65037 |

[9] | Li, D. H., Fukushima, M., Qi, L., and Yamashita, N., Regularized Newton Methods for Convex Minimization Problems with Singular Solutions, Computational Optimization and Applications (to appear). · Zbl 1056.90111 |

[15] | Mangasarian, O. L., A Newton Method for Linear Programming, Data Mining Institute, Technical Report 02-02, 2002. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.