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

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

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

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

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

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

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

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

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

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

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