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

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

Предположим, что ${\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\leqslant \gamma \leqslant 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 итераций при условии, что градиент непрерывен по Липшицу по некоторой норме. Та же самая сходимость может быть показана, если подзадачи решаются лишь приближённо^[4].

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

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

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

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

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

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

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

Эта последняя задача решается на каждой итерации алгоритма Франк — Вульфа, поэтому решение ${\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}\leqslant f(\mathbf {x} ^{*})\leqslant f(\mathbf {x} _{k})}$.

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

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

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