Алгоритм Франка-Вульфа

Алгоритм оптимизации

Алгоритм Франка–Вульфа — это итеративный алгоритм оптимизации первого порядка для ограниченной выпуклой оптимизации . Также известный как метод условного градиента , ^[1] алгоритм редуцированного градиента и алгоритм выпуклой комбинации , этот метод был первоначально предложен Маргерит Франк и Филиппом Вольфом в 1956 году. ^[2] На каждой итерации алгоритм Франка–Вульфа рассматривает линейную аппроксимацию целевой функции и движется к минимизатору этой линейной функции (взятой по той же области).

Постановка проблемы

Предположим, что — компактное выпуклое множество в векторном пространстве , а — выпуклая дифференцируемая функция с действительными значениями . Алгоритм Франка–Вульфа решает задачу оптимизации ${\displaystyle {\mathcal {D}}}$ ${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }$

Свернуть ${\displaystyle f(\mathbf {x} )}$

при условии . ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$

Алгоритм

Шаг алгоритма Франка–Вульфа

Инициализация: Пусть , и пусть будет любой точкой в ​​. ${\displaystyle k\leftarrow 0}$ ${\displaystyle \mathbf {x} _{0}\!}$ ${\displaystyle {\mathcal {D}}}$

Шаг 1. Подзадача определения направления: найти решение ${\displaystyle \mathbf {s} _{k}}$

Свернуть ${\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}$

При условии соблюдения ${\displaystyle \mathbf {s} \in {\mathcal {D}}}$

(Интерпретация: минимизировать линейное приближение задачи, заданное приближением Тейлора первого порядка, вокруг , ограниченного так, чтобы оставаться в пределах .) ${\displaystyle f}$ ${\displaystyle \mathbf {x} _{k}\!}$ ${\displaystyle {\mathcal {D}}}$

Шаг 2. Определение размера шага: Установите или, в качестве альтернативы, найдите значение, которое минимизирует условие . ${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$ ${\displaystyle \alpha }$ ${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$ ${\displaystyle 0\leq \alpha \leq 1}$

Шаг 3. Обновление: Пусть , пусть и перейдите к Шагу 1. ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$ ${\displaystyle k\leftarrow k+1}$

Характеристики

В то время как конкурирующие методы, такие как градиентный спуск для ограниченной оптимизации, требуют проецирования обратного шага к допустимому множеству на каждой итерации, алгоритму Франка–Вульфа требуется только решение выпуклой задачи над тем же множеством на каждой итерации, и он автоматически остается в допустимом множестве.

Сходимость алгоритма Франка–Вульфа в общем случае сублинейна: ошибка целевой функции в оптимуме возникает после k итераций, пока градиент является липшицевым относительно некоторой нормы. Такую же скорость сходимости можно показать, если подзадачи решаются только приближенно. ^[3] ${\displaystyle O(1/k)}$

Итерации алгоритма всегда можно представить в виде разреженной выпуклой комбинации крайних точек допустимого множества, что способствовало популярности алгоритма разреженной жадной оптимизации в задачах машинного обучения и обработки сигналов ^[4] , а также, например, оптимизации потоков минимальной стоимости в транспортных сетях ^[5] .

Если допустимый набор задан набором линейных ограничений, то подзадача, решаемая на каждой итерации, становится линейной программой .

Хотя скорость сходимости в худшем случае в общем случае не может быть улучшена, более быструю сходимость можно получить для специальных классов задач, таких как некоторые сильно выпуклые задачи. ^[6] ${\displaystyle O(1/k)}$

Нижние границы значения решения и прямо-двойственный анализ

Так как является выпуклым , то для любых двух точек имеем: ${\displaystyle f}$ ${\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}}$

${\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$

Это также справедливо для (неизвестного) оптимального решения . То есть, . Лучшая нижняя граница относительно заданной точки задается выражением ${\displaystyle \mathbf {x} ^{*}}$ ${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}$

Последняя задача оптимизации решается на каждой итерации алгоритма Франка–Вульфа, поэтому решение подзадачи пеленгования -й итерации можно использовать для определения возрастающих нижних границ на каждой итерации, устанавливая и ${\displaystyle \mathbf {s} _{k}}$ ${\displaystyle k}$ ${\displaystyle l_{k}}$ ${\displaystyle l_{0}=-\infty }$

${\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))}$

Такие нижние границы неизвестного оптимального значения важны на практике, поскольку их можно использовать в качестве критерия остановки и они дают эффективный сертификат качества аппроксимации на каждой итерации, поскольку всегда . ${\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}$

Было показано, что этот соответствующий разрыв двойственности , то есть разница между и нижней границей , уменьшается с той же скоростью сходимости, т.е. ${\displaystyle f(\mathbf {x} _{k})}$ ${\displaystyle l_{k}}$ ${\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).}$

Примечания

1. Левитин, Е.С.; Поляк, Б.Т. (1966). «Методы условной минимизации». Журнал вычислительной математики и математической физики СССР . 6 (5): 1. doi :10.1016/0041-5553(66)90114-5.
2. Франк, М.; Вулф, П. (1956). «Алгоритм квадратичного программирования». Naval Research Logistics Quarterly . 3 (1–2): 95–110. doi :10.1002/nav.3800030109.
3. Данн, Дж. К.; Харшбаргер, С. (1978). «Условные градиентные алгоритмы с правилами размера шага открытого цикла». Журнал математического анализа и приложений . 62 (2): 432. doi : 10.1016/0022-247X(78)90137-3 .
4. Кларксон, К. Л. (2010). «Coresets, разреженная жадная аппроксимация и алгоритм Франка-Вульфа». Труды ACM по алгоритмам . 6 (4): 1–30. CiteSeerX 10.1.1.145.9299 . doi :10.1145/1824777.1824783. 
5. Фукусима, М. (1984). «Модифицированный алгоритм Франка-Вульфа для решения проблемы распределения трафика». Transportation Research Часть B: Методологические . 18 (2): 169–177. doi :10.1016/0191-2615(84)90029-8.
6. Берцекас, Димитрий (1999). Нелинейное программирование . Athena Scientific. стр. 215. ISBN 978-1-886529-00-7.

Библиография

• Jaggi, Martin (2013). «Возвращаясь к Frank–Wolfe: Projection-Free Sparse Convex Optimization». Журнал исследований машинного обучения: Труды семинаров и конференций . 28 (1): 427–435.(Обзорная статья)
• Описание алгоритма Франка–Вульфа
• Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . ISBN 978-0-387-30303-1..

Внешние ссылки

• https://conditional-gradients.org/: обзор алгоритмов Франка–Вульфа.
• Маргерит Франк дает личный отчет об истории алгоритма

Смотрите также

• Методы проксимального градиента