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

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

• 1 Постановка задачи
• 2 Алгоритм
• 3 Свойства
• 4 Нижние границы значения решения и первично-дуальный анализ
• 5 Примечания
• 6 Библиография
• 7 Внешние ссылки
• 8 См. Также

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

Минимизировать $f\; (x)\; \{\backslash \; displaystyle\; f\; (\backslash \; mathbf\; \{x\})\}$

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

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

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

Minimize $s\; T\; \nabla \; е\; (xk)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{s\}\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\})\}$

с учетом $s\; \in \; D\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{s\}\; \backslash \; in\; \{\backslash \; mathcal\; \{D\}\}\}$

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

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

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

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

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

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

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

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

Поскольку $f\; \{\backslash \; displaystyle\; f\}$равно выпуклый, fo r любые две точки $x,\; y\; \in \; D\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{y\}\; \backslash \; in\; \{\backslash \; mathcal\; \{D\}\}\}$имеем:

$f\; (\; Y)\; \ge \; е\; (Икс)\; +\; (Y\; -\; Икс)\; T\; \nabla \; е\; (Икс)\; \{\backslash \; Displaystyle\; F\; (\backslash \; mathbf\; \{y\})\; \backslash \; GEQ\; F\; (\backslash \; mathbf\; \{x\})\; +\; (\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{x\})\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\})\}$

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

$f\; (x\; \ast )\; \ge \; f\; (x)\; +\; (x\; \ast \; -\; x)\; T\; \nabla \; f\; (x)\; \ge \; min\; y\; \in \; D\; \{f\; (x)\; +\; (y\; -\; x)\; T\; \nabla \; f\; (x)\}\; =\; f\; (x)\; -\; x\; T\; \nabla \; f\; (x)\; +\; min\; y\; \in \; D\; y\; T\; \nabla \; е\; (Икс)\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; f\; (\backslash \; mathbf\; \{x\}\; ^\; \{*\})\; \backslash \; geq\; f\; (\backslash \; mathbf\; \{x\})\; +\; (\backslash \; mathbf\; \{x\}\; ^\; \{*\}\; -\; \backslash \; mathbf\; \{x\})\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\})\; \backslash \backslash \; \backslash \; geq\; \backslash \; min\; \_\; \{\backslash \; mathbf\; \{y\}\; \backslash \; in\; D\}\; \backslash \; left\; \backslash \; \{f\; (\backslash \; mathbf\; \{x\})\; +\; (\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{x\})\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\})\; \backslash \; right\; \backslash \}\; \backslash \backslash \; =\; f\; (\backslash \; mathbf\; \{x\})\; -\; \backslash \; mathbf\; \{x\}\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\})\; +\; \backslash \; min\; \_\; \{\backslash \; mathbf\; \{y\}\; \backslash \; in\; D\}\; \backslash \; mathbf\; \{y\}\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\})\; \backslash \; end\; \{\; выровненный\}\}\}$

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

$lk:\; =\; max\; (lk\; -\; 1,\; f\; (xk)\; +\; (sk\; -\; хк)\; T\; \nabla \; е\; (хк))\; \{\backslash \; displaystyle\; l\_\; \{k\}:\; =\; \backslash \; max\; (l\_\; \{k-1\},\; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\})\; +\; (\backslash \; mathbf\; \{s\}\; \_\; \{\; k\}\; -\; \backslash \; mathbf\; \{x\}\; \_\; \{k\})\; ^\; \{T\}\; \backslash \; nabla\; f\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\}))\}$

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

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

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

• Маргарита Франк дает личную учет истории алгоритма

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