Учёные превратили трёхсотлетний метод Ньютона в универсальный инструмент оптимизации

Учёные каждый день решают задачи, в которых нужно найти наилучшее решение — от выбора места для строительства крупного авиационного узла до управления инвестициями и создания беспилотных автомобилей. Такие задачи сводятся к поиску минимума некой функции. Но часто сами функции оказываются настолько сложными, что напрямую с ними не справиться, и приходится довольствоваться приближёнными решениями.

Один из самых эффективных способов найти минимум был придуман ещё в XVII веке Исааком Ньютоном. Его метод по сути напоминает движение с завязанными глазами по неровной местности: вы делаете шаг вперёд, зная только, становилось ли идти труднее или легче. Этого достаточно, чтобы быстро приблизиться к наинизшей точке. Метод Ньютона, несмотря на возраст, до сих пор используется для решения сложных задач в логистике, финансах, компьютерном зрении и даже в чистой математике. Однако он работает не на всех функциях, и учёные продолжают искать способы сделать его более универсальным.

Летом 2023 года исследователи Амир Али Ахмади из Принстона, а также его бывшие студенты Абраар Чоудри и Джеффри Чжан, предложили усовершенствование , которое расширяет возможности метода Ньютона на самый широкий класс функций из всех возможных на сегодня. По словам Ахмади, их алгоритм потенциально может полностью заменить метод Ньютона.

Суть задачи в том, чтобы найти минимальное значение функции, то есть такой набор входных данных, при котором выходное значение будет наименьшим. Но когда функция сложная, с множеством переменных и степеней, классические приёмы перестают работать. Функция превращается в многомерный пейзаж, в котором нужно нащупать самую глубокую долину. При этом у нас есть два главных инструмента — производные. Первая показывает наклон функции в точке, а вторая — насколько быстро этот наклон меняется. Используя их, можно создать упрощённую версию функции в виде параболы (или её многомерного аналога), найти её минимум и таким образом приблизиться к настоящему минимуму исходной функции. Повторяя этот процесс, можно шаг за шагом добраться до цели.

Метод Ньютона отличается от других, более простых методов вроде градиентного спуска тем, что сходится к минимуму гораздо быстрее — квадратично, а не линейно. Правда, за это приходится платить: каждый шаг требует больших вычислительных затрат, поэтому в задачах вроде обучения нейросетей всё ещё чаще используют градиентный спуск.

Ньютон использовал только вторую производную, потому что в его время никто не умел работать с производными более высокого порядка. Позже математики пытались расширить метод, включая третьи, четвёртые и более высокие производные, но наталкивались на ограничения. Например, Чебышёв в XIX веке предложил использовать кубические приближения, но его метод не работал с несколькими переменными. В 2021 году Юрий Нестеров нашёл способ использовать кубические уравнения при любом числе переменных, но этот подход нельзя было распространить на функции четвёртой, пятой и более высоких степеней без потери эффективности.

Новая работа Ахмади и его коллег пошла дальше. Их алгоритм работает с функциями любой сложности и с любым числом производных — и при этом остаётся эффективным. Ключ к успеху — идея "подправить" исходное приближение, чтобы оно стало легче в обработке. В математике есть особые классы уравнений, с которыми легко работать: они выпуклые (имеют только одну долину) и представимы как сумма квадратов. Обычно тейлоровские разложения , используемые в методе Ньютона, такими не являются. Но исследователи применили технику, известную как полуопределённое программирование , чтобы слегка изменить разложение и превратить его в выпуклую сумму квадратов, не отходя далеко от исходной функции.

Таким образом, они создали новую версию метода Ньютона, которая использует произвольно высокие производные и при этом сходится к минимуму быстрее: при использовании третьей производной — кубически, четвёртой — в четвёртой степени и так далее. Это значит, что нужный результат можно получить за меньшее число итераций.

Пока что новый метод остаётся теоретически привлекательным, но слишком дорогим с вычислительной точки зрения, чтобы заменить существующие решения вроде градиентного спуска в таких сферах, как беспилотники или ИИ. Однако, как отмечают специалисты, многие идеи в оптимизации проходят долгий путь от теории до практики. Если со временем нужные вычисления станут дешевле, метод Ахмади и его команды может стать новым стандартом для сложных задач оптимизации.

По словам самого Ахмади, алгоритм уже сейчас гарантированно быстрее с теоретической точки зрения. Осталось дождаться, когда он станет таким же и на практике — возможно, через 10–20 лет.