СПЕЦИАЛЬНЫЙ ВЫПУСК

Регуляризация и ускорение метода Гаусса – Ньютона

Н. Е. Юдин^abcdef, А. В. Гасников<sup>ab

a</sup> Университет Иннополис, Россия, 420500, г. Иннополис, ул. Университетская, д. 1
^b Национальный исследовательский университет «Московский физико-технический институт», Россия, 141701, Московская область, г. Долгопрудный, Институтский пер., д. 9
^c Национальный исследовательский университет «Высшая школа экономики», Россия, 109028, г. Москва, Покровский бульвар, д. 11
^d Федеральное государственное бюджетное учреждение науки «Институт проблем передачи информации им. А. А. Харкевича» Российской академии наук, Россия, 127051, г. Москва, Большой Каретный пер., д. 19, стр. 1
^e Федеральный исследовательский центр «Информатика и управление» Российской академии наук, Россия, 119333, г. Москва, ул. Вавилова, д. 44, корп. 2
^f Федеральное государственное бюджетное учреждение науки «Институт системного программирования им. В. П. Иванникова» Российской академии наук, Россия, 109004, г. Москва, ул. А. Солженицына, д. 25

Аннотация: Предлагается семейство методов Гаусса – Ньютона для решения оптимизационных задачи систем нелинейных уравнений, основанное на идеях использования верхней оценки нормы невязки системы уравнений и квадратичной регуляризации. В работе представлено развитие схемы метода трех квадратов с добавлением моментного члена к правилу обновления искомых параметров в решаемой задаче. Получившаяся схема обладает несколькими замечательными свойствами. Во-первых, в работе алгоритмически описано целое параметрическое семейство методов, минимизирующих функционалы специального вида: композиции невязки нелинейного уравнения и унимодального функционала. Такой функционал, целиком согласующийся с парадигмой «серого ящика» в описании задачи, объединяет в себе большое количество решаемых задач, связанных с приложениями в машинном обучении, с задачами восстановления регрессионной зависимости. Во-вторых, полученное семейство методов описывается как обобщение нескольких форм алгоритма Левенберга – Марквардта, допускающих реализацию в том числе и в неевклидовых пространствах. В алгоритме, описывающем параметрическое семейство методов Гаусса – Ньютона, используется итеративная процедура, осуществляющая неточное параметризованное проксимальное отображение и сдвиг с помощью моментного члена. Работа содержит детальный анализ эффективности предложенного семейства методов Гаусса – Ньютона, выведенные оценки учитывают количество внешних итераций алгоритма решения основной задачи, точность и вычислительную сложность представления локальной модели и вычисления оракула. Для семейства методов выведены условия сублинейной и линейной сходимости, основанные на неравенстве Поляка – Лоясиевича. В обоих наблюдаемых режимах сходимости локально предполагается наличие свойства Липшица у невязки нелинейной системы уравнений. Кроме теоретического анализа схемы, в работе изучаются вопросы ее практической реализации. В частности, в проведенных экспериментах для субоптимального шага приводятся схемы эффективного вычисления аппроксимации наилучшего шага, что позволяет на практике улучшить сходимость метода по сравнению с оригинальным методом трех квадратов. Предложенная схема объединяет в себе несколько существующих и часто используемых на практике модификаций метода Гаусса – Ньютона, в добавок к этому в работе предложена монотонная моментная модификация семейства разработанных методов, не замедляющая поиск решения в худшем случае и демонстрирующая на практике улучшение сходимости метода.

Ключевые слова: системы нелинейных уравнений, невыпуклая оптимизация, метод Гаусса – Ньютона, условие Поляка – Лоясиевича, оценка сложности

УДК: 519.85

Поступила в редакцию: 28.10.2024
Исправленный вариант: 12.11.2024
Принята в печать: 25.11.2024

DOI: 10.20537/2076-7633-2024-16-7-1829-1840