Современные методы оптимизации

В последние 10–15 лет резко возрос интерес к численным методам оптимизации. В основном это связано с приложениями к анализу данных. И мне хотелось бы кратко рассказать, что произошло в этой области за последнее время и в целом за последние 50–60 лет — именно столько насчитывает данная область.

Началось все, по-видимому, с Коши, который во второй половине XIX века предложил метод градиентного спуска как численный метод решения задач оптимизации. Но давайте начнем еще раньше, с того, где вообще стали возникать задачи оптимизации. Хорошо известно, что природа говорит на языке оптимизации, на языке вариационных принципов. Если мы хотим найти уравнение движения какого-нибудь объекта, хотим понять, как оптимально что-то сделать, природа сама часто хочет это сделать, то надо решить какую-то задачу оптимизации. В XVIII веке Лагранж и Эйлер предложили уравнение, которое описывает траекторию движения механической системы, и эту траекторию можно получать из решения вариационной задачи.

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

Менее очевидные вещи возникают, когда, например, нам надо решить систему уравнений или какую-нибудь обратную задачу. Скажем, есть какая-нибудь система дифференциальных уравнений, у нее есть правая часть или какие-то коэффициенты. Мы их не знаем, но наблюдаем решение на каком-то отрезке времени и должны восстановить неизвестные коэффициенты, неизвестные краевые условия, исходя из наблюдаемого решения. Эти задачи играют чрезвычайно важную роль, потому что это нефтедобыча, это медицинская томография и многие другие области, где тоже такие задачи возникают, но эти уже задачи — уравнения.

Надо обратно решить задачу ax=b, найти x. Казалось бы, при чем здесь оптимизация? Но оказывается, что ax=b можно записать как ax-b — это некий вектор, норма этого вектора в квадрате на минимум. И минимум достигается в той точке, где решение этого уравнения. То есть та точка x, которая доставляет решению уравнения ax=b, и есть минимум функционала ax-b два норма в квадрате.

Таким образом, надо решать задачи оптимизации, и часто это задачи оптимизации бесконечномерных пространств. Когда я упоминал дифференциальные уравнения, то решением является функция. И понятно, что все это требует разработки методов. Более того, многие задачи надо решать много раз. Например, взаимодействуя с биологами в компании «Биокад», я столкнулся с задачей белкового фолдинга и докинга. Это индустриальная задача, огромные масштабы, каждый день эта задача сотни раз перерешивается. И от того, насколько эффективен метод решения этой задачи, столько вы раз успеете разные формы посопоставлять, зависит, как много вариантов лекарств вы попробуете успеть проверить, потому что мощности ограничены в энергетическом плане, то есть энергию это все поглощает, и ограничены во времени. И чем эффективнее алгоритм, тем больше вариантов вы посмотрите. Таким образом, очень много разных задач сводится именно к оптимизации.

Важно сразу разделить эти задачи на два класса: выпуклые и невыпуклые. Дело в том, что если оптимизируемая функция обладает свойством, которое называется выпуклость (это слово уже на бытовом уровне ассоциируется с чем-то хорошим), то множество точек, которое выше графика функции (то есть надграфик функции, который у вас есть), должно быть выпуклым. Это означает, что оно содержит любой отрезок с любыми двумя своими точками: мы берем любые две точки из этого множества, и это множество содержит целый отрезок. Такие функции, надграфик которых представляет собой выпуклое множество, — это хорошие функции, хороший класс задач. Потому что их можно более-менее эффективно решать.

А вот невыпуклые функции — плохой класс функций (недавно были получены довольно интересные результаты на эту тему, и их упомянуть будет интересно). Мы хотим найти решение задачи оптимизации с точностью эпсилон, с какой-то маленькой точностью, то есть решить задачу так, чтобы значение функции в найденной точке отличалось от оптимального не больше чем на эпсилон.

Чтобы гарантированно это иметь, нужно обратиться к так называемому оракулу: нужно что-то посчитать относительно этой функции, например градиент, производные, значения функции. Это выражается как единица на эту точность эпсилон в степени n, где n — размерность пространства. Если мы хотим решить задачу с точностью эпсилон, задачу в пространстве размерности n, где большое число, то сложность, количество обращений к оракулу, количество вычислений пропорционально единица на эпсилон в степени n. Это экспоненциально увеличивается с ростом числа n. Это пессимистичный результат, и, к сожалению, его нельзя улучшить.

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

Другая история — когда мы имеем выпуклую задачу. Но в заключение темы с невыпуклыми задачами я все-таки еще один пример хотел привести. Это пример о том, что проблема невыпуклой оптимизации не в многоэкстремальности. Точнее, в многоэкстремальности функционала проблемы есть, но можно привести пример функции, которая имеет всего один экстремум. И эта функция по сложности оптимизации соответствует тому, о чем я до этого сказал. Не стоит думать, что только многоэкстремальность обуславливает все эти проблемы. То есть сходимость по функции, что это общая проблема невыпуклой оптимизации. По градиенту, по норме градиента можно сходиться, но это всего лишь локальный экстремум. А чтобы именно функцию сделать маленькой — это проблема.

Переходим к выпуклой оптимизации. Здесь действительно есть много интересных результатов — как классических, так и недавних. И начнем мы опять с градиентного метода. Он был предложен в XIX веке. Градиентным спуском активно стали пользоваться в 1950–1960-е годы. Вкратце обсудим идею этого метода. Общая идея численных методов оптимизации заключается в принципе «разделяй и властвуй». Мы хотим оптимизировать сложную функцию. Мы имеем текущее положение, линеаризуем или как-то упрощаем функцию, заменяем ее более простой моделью. И говорим, что вместо того, чтобы минимизировать, решать исходную сложную задачу, мы аппроксимируем каким-то образом эту функцию в данной точке. Аппроксимация структурно более простая, чем исходная функция, и мы решаем эту задачу минимизацией этой аппроксимации. В случае градиентного спуска этой аппроксимацией является парабола. Если мы говорим о многомерном пространстве, то это параболоид вращения. Заменяем исходную функцию таким параболоидом вращения, который касается ее в данной точке. И идея метода заключается в том, что вместо минимизации функции мы минимизируем параболоид.

Это мы можем сделать по явным формулам, перейти к минимуму параболоида. Уравнение параболоида определяем однозначно. Это делается по явным формулам, из условия касания. И это есть градиентный метод. Он имеет вид: есть новая точка, есть старая точка минус некий шаг на градиент, на вектор градиента. Тем, кто увлекается альпинизмом или просто походами по горам, я думаю, эти все термины хорошо известны, например градиент. Для этого не обязательно иметь специальное математическое образование. В каком-то смысле градиентный спуск — такой способ блуждать по горам, когда вы идете по направлению наибыстрейшего спуска. Но это локально, потому что, когда вы пройдете какое-то расстояние, направление изменится. Собственно градиентный спуск — такая дискретизация этого непрерывного процесса хождения по направлению наибыстрейшего спуска.

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

И на каждой итерации решаем вместо многомерной задачи двумерную задачу. Но двумерная задача решается по явным формулам в случае квадратичного функционала. И было обнаружено, что такой метод сходится заметно быстрее, а именно: если градиентный спуск сходится, это число обусловленности, число обращений к оракулу, число вычислений градиента, число обусловленности оптимизированного функционала. Для сопряженных градиентов это корень из числа обусловленности. И возникло желание получить такую же оценку, но уже для общих задач выпуклой оптимизации. И до конца 1970-х годов эта программа не была реализована, то есть почти 20 лет. Не было найдено метода, который бы так работал. Но было понимание, что сопряженные градиенты так работают, но только на квадратичных задачах.

А в конце 1970-х годов это было предложено Немировским. В начале 1980-х был предложен вариант так называемого ускоренного метода — вариант сопряженных градиентов, получивший название «ускоренный градиентный спуск», который не требует вспомогательных оптимизаций. Был предложен некий метод, который по виду очень сильно напоминает градиентный спуск. Более того, у него такая же сложность итерации. И оказалось, что этот метод совершил революцию в численных методах оптимизации.

Большинство специалистов-прикладников, которые до недавнего времени пользовались градиентным спуском, с восторгом обнаружили, что метод, предложенный в начале 1980-х годов, замечательным образом ускоряет градиентный спуск, но при этом у него сложность итерации такая же, как у градиентного спуска. То есть он просто ускоряет. Конечно, это замечательно, если у нас задача решалась за 10 часов, а сейчас за 20 минут — масштаб ускорения приблизительно такой. И это ничего не стоит. Это связано исключительно с наукой, не с технологиями. И в разных областях, понимая это, люди стали использовать этот ускоренный градиентный метод, но возник следующий вопрос.

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

В эту оболочку ускорения, которая связана с привлечением предыдущей итерации, в двухшаговый метод, мы новую точку рассчитываем не по текущей, а по текущей и прошлой. Таким образом, мы используем историю в один шаг. Следующую точку строим не с текущей, а как бы двухшагово. И этого оказалось достаточно, что удивительно. Потому что потенциально мы накапливаем огромное количество информации итерационным процессом по ходу решения задачи. Казалось бы, вся эта информация полезна, ее надо как-то использовать. Так оно и есть, но, если это правильно используется, это агрегируется в небольшом числе показателей. Эти ускоренные методы — это методы с очень короткой памятью, памятью два. И поэтому они такие дешевые. Они по стоимости итерации такие же, как градиентный спуск.

Оказалось, что методы высокого порядка оптимальные, к примеру типа Ньютона, и их ускоренные варианты, даже уже третьего порядка, которые в эту же оболочку погружаются. Результат действительно удивительный, потому что надо понять, что есть некоторая конструкция, ускоряющая обычные градиентные методы, и таким образом можно ускорять методы любого порядка, любые методы. Заменяя в конструкции градиентного спуска параболоид вращения какой-то другой функцией, вы можете предлагать разнообразные методы, накручивая на это ускорение. Вы генерируете огромное многообразие методов, которые и используются в современной оптимизации.

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