Алгоритм Франка-Вульфа (метод условного градиента) в выпуклой оптимизации

Математическая суть алгоритма заключается в замене сложной нелинейной целевой функции $f(x)$ ее линейной аппроксимацией Тейлора первого порядка в текущей точке $x_k$. На каждой итерации алгоритм решает вспомогательную задачу линейного программирования: минимизировать $\langle \nabla f(x_k), s \rangle$ по всем $s$ из допустимого выпуклого множества $D$. Найденная оптимальная точка $s_k$ указывает направление наискорейшего убывания линеаризованной функции. Следующая точка $x_{k+1}$ вычисляется как выпуклая комбинация текущей точки и найденной вершины: $x_{k+1} = (1 - \gamma_k)x_k + \gamma_k s_k$, где $\gamma_k \in [0, 1]$ — длина шага, которая может выбираться по правилу убывающей последовательности (например, $2/(k+2)$) или с помощью точного линейного поиска.

Фундаментальное преимущество метода перед классическим проективным градиентным спуском состоит в замене дорогостоящей операции проекции $\arg\min_{y \in D} ||y - (x - \alpha \nabla f(x))||_2^2$ на решение задачи линейной оптимизации (LMO - Linear Minimization Oracle). Для многих сложных выпуклых множеств (таких как симплексы, многогранники перестновок, ядерные нормы матриц) решение LMO на порядки быстрее. Например, если допустимое множество $D$ представляет собой матричную норму следа (Nuclear Norm Ball), используемую в задачах матричного заполнения (Matrix Completion) и рекомендательных системах, LMO требует лишь вычисления максимального сингулярного вектора (Lanczos algorithm), тогда как проекция требовала бы полного сингулярного разложения матрицы (SVD), что делает проективный метод абсолютно неприменимым для матриц размером миллион на миллион.

Теоретические оценки показывают, что алгоритм Франка-Вульфа сходится к глобальному оптимуму гладкой выпуклой функции со скоростью $O(1/k)$, где $k$ — номер итерации. Кроме того, алгоритм генерирует последовательность точек, которые математически являются разреженными комбинациями вершин допустимого множества (Sparse Representation). На итерации $k$ решение $x_k$ является выпуклой комбинацией не более чем $k$ крайних точек. Это свойство структурной разреженности (структурного спарсинга) бесценно при обучении интерпретируемых моделей искусственного интеллекта и в задачах восстановления сигналов (Compressed Sensing).

В транспортной логистике алгоритм Франка-Вульфа является стандартом де-факто для поиска пользовательского равновесия (User Equilibrium) в сетях — равновесия Вардропа. В этом контексте LMO сводится к поиску кратчайших путей на графе (алгоритм Дейкстры) при фиксированных временах проезда, после чего транспортный поток перераспределяется в найденном направлении. Спустя десятилетия после своего создания, метод условного градиента остается непревзойденным примером того, как глубокое понимание геометрии выпуклых множеств позволяет обходить фундаментальные вычислительные барьеры в прикладной математике.

Список литературы:
1. Frank M., Wolfe P. An algorithm for quadratic programming. — Naval Research Logistics Quarterly, 1956.
2. Jaggi M. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. — ICML, 2013.
3. Демьянов В.Ф., Рубинов А.М. Приближенные методы решения экстремальных задач. — М.: Изд-во ЛГУ, 1968.