1. Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations.
- Author
-
Zhou, G. and Toh, K. C.
- Subjects
- *
LINEAR systems , *STOCHASTIC convergence , *ALGORITHMS , *MONOTONE operators , *EQUATIONS , *MATHEMATICS - Abstract
We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 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. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF