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

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

Постановка задачи

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

Свернуть

f(\mathbf {x} )

при условии

\mathbf {x} \in {\mathcal {D}}

.

Алгоритм

Инициализация: Пусть

k\leftarrow 0

, и пусть

\mathbf {x} _{0}\!

быть любой точкой

{\mathcal {D}}

.

Шаг 1. Подзадача пеленгации: Найти

\mathbf {s} _{k}

решение

Свернуть

\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})

С учетом

\mathbf {s} \in {\mathcal {D}}

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

Шаг 2. Определение размера шага: Установите

\alpha \leftarrow {\frac {2}{k+2}}

или альтернативно найти

\alpha

что сводит к минимуму

f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))

при условии

0\leq \alpha \leq 1

.

Шаг 3. Обновление: пусть

\mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})

, позволять

k\leftarrow k+1

и перейдите к шагу 1.

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

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

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

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

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

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

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

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

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

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

{\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}}

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

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

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

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

Примечания

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

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

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

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

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

См. также

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

[1] Левитин Е.С.; Поляк, Б.Т. (1966). «Методы ограниченной минимизации». Вычислительная математика и математическая физика СССР . 6 (5): 1. дои : 10.1016/0041-5553(66)90114-5 .

[2] Франк, М.; Вулф, П. (1956). «Алгоритм квадратичного программирования». Ежеквартальный журнал военно-морских исследований по логистике . 3 (1–2): 95–110. дои : 10.1002/nav.3800030109 .

[3] Данн, Джей Си; Харшбаргер, С. (1978). «Алгоритмы условного градиента с правилами размера шага разомкнутого цикла» . Журнал математического анализа и приложений . 62 (2): 432. дои : 10.1016/0022-247X(78)90137-3 .

[4] Кларксон, КЛ (2010). «Наборы ядер, разреженная жадная аппроксимация и алгоритм Франка-Вульфа». Транзакции 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). Нелинейное программирование . Афина Сайентифик. п. 215. ИСБН 978-1-886529-00-7 .

[1]

[2]

[3]

[4]

[5]

[6]