Модифицированный метод Гаусса–Ньютона для решения гладкой системы нелинейных уравнений

Компьютерные исследования и моделирование. 2021. Т. 13. № 4. С. 697–723.

Yudin N.

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-Łojasiewicz 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: системы нелинейных уравнений, нелинейная регрессия, невыпуклая оптимизация, неточный оракул, inexact oracle, Complexity estimate, Nonlinear regression, nonconvex optimization, Polyak-Łojasiewicz condition, systems of nonlinear equations, inexact proximal mapping, Gauss-Newton method, Levenberg-Marquardt algorithm, trust rergion methods, метод Гаусса-Ньютона, алгоритм Левенберга-Марквардта, методы доверительной области, неточное проксимальное отображение, условие Поляка-Лоясиевича, оценка сложности