This article is cited in 3 papers

NUMERICAL METHODS AND THE BASIS FOR THEIR APPLICATION

Modified Gauss-Newton method for solving a smooth system of nonlinear equations

N. E. Yudin<sup>ab

a</sup> National Research University «Moscow Institute of Physics and Technology», 9 Institutskiy per., Dolgoprudny, 141701, Russia
^b Federal Research Center «Informatics and Control» of Russian Academy of Sciences, 44/2 Vavilova st., Moscow, 119333, Russia

Abstract: In this paper, we introduce a new version of Gauss–Newton method for solving a system of nonlinear equations based on ideas of the residual upper bound for a system of nonlinear equations and a quadratic regularization term. The introduced Gauss–Newton method in practice virtually forms the whole parameterized family of the methods solving systems of nonlinear equations and regression problems. The developed family of Gauss–Newton methods completely consists of iterative methods with generalization for cases of non-euclidean normed spaces, including special forms of Levenberg–Marquardt algorithms. The developed methods use the local model based on a parameterized proximal mapping allowing us to use an inexact oracle of «black-box» form with restrictions for the computational precision and computational complexity. We perform an efficiency analysis including global and local convergence for the developed family of methods with an arbitrary oracle interms of iteration complexity, precision and complexity of both local model and oracle, problem dimensionality. We present global sublinear convergence rates for methods of the proposed family for solving a system of nonlinear equations, consisting of Lipschitz smooth functions. We prove local superlinear convergence under extra natural non-degeneracy assumptions for system of nonlinear functions. We prove both local and global linear convergence for a system of nonlinear equations under Polyak–Lojasiewicz condition for proposed Gauss-Newton methods. Besides theoretical justifications of methods we also consider practical implementation issues. In particular, for conducted experiments we present effective computational schemes for the exact oracle regarding to the dimensionality of a problem. The proposed family of methods unites several existing and frequent in practice Gauss–Newton method modifications, allowing us to construct a flexible and convenient method implementable using standard convex optimization and computational linear algebra techniques.

Keywords: systems of nonlinear equations, nonlinear regression, Gauss–Newton method, Levenberg–Marquardt algorithm, trust rergion methods, nonconvex optimization, inexact proximal mapping, inexact oracle, Polyak–Lojasiewicz condition, complexity estimate.

UDC: 519.85

Received: 08.05.2021
Revised: 24.06.2021
Accepted: 30.06.2021

DOI: 10.20537/2076-7633-2021-13-4-697-723