Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations

被引：0

作者：

G. Zhou

K. C. Toh

机构：

[1] Curtin University of Technology,Research Associate, Department of Mathematics and Statistics

[2] National University of Singapore,Associate Professor, Department of Mathematics

来源：

Journal of Optimization Theory and Applications | 2005年 / 125卷

关键词：

Monotone equations; Newton method; global convergence; superlinear convergence; convex minimization;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：205 / 221

页数：16

共 15 条

[1]

Qi L.(1993)A Nonsmooth Version of Newton’s Method Mathematical Programming 58 353-367

[2]

Sun J.(2001)On the Rate of Convergence of the Levenberg-Marquardt Method Computing 15 239-249

[3]

Yamashita N.(2002)Local Behavior of an Iterative Framework for Generalized Equations with Nonisolated Solutions Mathematical Programming 94 91-124

[4]

Fukushima M.(2002)A Superlinearly Convergent Algorithm for the Monotone Complementarity Problem without Uniqueness and Nondegeneracy Conditions Mathematics of Operations Research 27 743-754

[5]

Fischer A.(2001)The Proximal Point Algorithm with Genuine Superlinear Convergence for the Monotone Complementarity Problem SIAM Journal on Optimization 11 364-379

[6]

Dan H.(1981)Some Continuity Properties of Polyhedral Multifunctions Mathematical Programming Study 14 206-214

[7]

Yamashita N.(1984)Normal Solutions of Linear Programs Mathematical Programmming Study 22 206-216

[8]

Fukushima M.(2003)On the Minimum-Norm Solution of Linear Programs Journal of Optimization Theory and Applications 116 333-345

[9]

Yamashita N.(undefined)undefined undefined undefined undefined-undefined

[10]

Fukushima M.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →