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

Yudin N.E.
 pdf (650K)

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 in terms 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
Citation in English: Yudin N.E. Modified Gauss–Newton method for solving a smooth system of nonlinear equations // Computer Research and Modeling, 2021, vol. 13, no. 4, pp. 697-723
Citation in English: Yudin N.E. Modified Gauss–Newton method for solving a smooth system of nonlinear equations // Computer Research and Modeling, 2021, vol. 13, no. 4, pp. 697-723
DOI: 10.20537/2076-7633-2021-13-4-697-723
URL: http://crm-en.ics.org.ru/journal/article/3093/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science