Optimization Online


Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

N.I.M. Gould (n.gould***at***rl.ac.uk)
D. Orban (orban***at***ece.northwestern.edu)
A. Sartenaer (Annick.Sartenaer***at***fundp.ac.be)
Ph.L. Toint (Philippe.Toint***at***fundp.ac.be)

Abstract: The asymptotic convergence of parameterized variants of Newton's method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable path leading to a solution of the original system, the scalar parameter determining the progress along the path. A path-following algorithm, which involves an inner iteration in which the perturbed systems are approximately solved, is outlined. It is shown that asymptotically, a single linear system is solved per update of the scalar parameter. It turns out that a componentwise Q-superlinear rate may be attained under standard assumptions, and that this rate may be made arbitrarily close to quadratic. Numerical experiments illustrate the results and we discuss the relationships that this method shares with interior methods in constrained optimization.

Keywords: nonlinear systems of equations,path-following methods,componentwise Q-superlinear convergence

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Published in Mathematical Programming Online First http://dx.doi.org/10.1007/s101070100287 Published online Feb 14, 2002. This version: Report TR/PA/00/56 CERFACS -- Parallel Algorithms Project 42, Avenue Gaspard Coriolis 31057 Toulouse Cedex 1, France. September 2000, revised August 2001

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 06/11/2001
Entry Accepted: 06/11/2001
Entry Last Modified: 02/25/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society