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

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

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

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

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

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

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

Поскольку функция ${\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).}$

Примечания

Литература

Ссылка

См. также

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