New versions of Newton method: step-size choice, convergence domain and under-determined equations. (1st November 2020)

• Record Type: Journal Article
• Authors: Polyak, Boris; Tremba, Andrey
• Is Part Of: Optimization methods and software. Volume 35:Number 6(2020)
• Page Start: 1272
• Page End: 1303
• Publication Date: 2020-11-01
• Subjects: Nonlinear equations -- Newton method -- under-determined equations -- global convergence -- adaptive algorithms -- metric regularity; 49M15 -- 65H10 -- 90C30 -- 58C15; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1669154
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: Newton method is one of the most powerful methods for finding solutions of nonlinear equations and for proving their existence. In its 'pure' form it has fast convergence near the solution, but small convergence domain. On the other hand damped Newton method has slower convergence rate, but weaker conditions on the initial point. We provide new versions of Newton-like algorithms, resulting in combinations of Newton and damped Newton method with special step-size choice, and estimate its convergence domain. Under some assumptions the convergence is global. Explicit complexity results are also addressed. The adaptive version of the algorithm (with no a priori constants knowledge) is presented. The method is applicable for under-determined equations (with m < n, m being the number of equations and n being the number of variables). The results are specified for systems of quadratic equations, for composite mappings and for one-dimensional equations and inequalities.