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

В Алгоритм Франка – Вульфа является итеративный первый заказ оптимизация алгоритм за сдержанный выпуклая оптимизация. Также известен как метод условного градиента,^[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}\!}$.)

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

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

• Маргарита Франк рассказывает об истории алгоритма.

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

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