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

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

Формулировка задачи

Предположим, что ${\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}\!$.)

Шаг 2. Определение размера шага: Положим $\gamma \leftarrow {\frac {2}{k+2}}$, или, альтернативно, находим $\gamma$, минимизирующее $f(\mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k}))$ при условии $0\leqslant \gamma \leqslant 1$ .

Шаг 3. Пересчёт: Положим $\mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\gamma (\mathbf {s} _{k}-\mathbf {x} _{k})$, $k\leftarrow k+1$ и переходим к шагу 1.

Свойства

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

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

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

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

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

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

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

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

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

${\begin{aligned}f(\mathbf {x} ^{*})&\geqslant f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geqslant \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}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})$.

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

Ссылка

• Marguerite Frank giving a personal account of the history of the algorithm

См. также

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