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

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

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

Предположим, что $𝒟$ является компактным выпуклым множеством в векторном пространстве, а $f:𝒟\to ℝ$ является выпуклой, дифференцируемой вещественнозначной функцией. Алгоритм Франк — Вульфа решает задачу оптимизации

Минимизировать $f(𝐱)$

при условии $𝐱\in 𝒟$.

Алгоритм

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

Инициализация: Пусть $k\leftarrow 0$ и пусть ${𝐱}_0$ будет точкой в $𝒟$.

Шаг 1. Подзадача поиска направления: Находим ${𝐬}_k$, решающее задачу

Минимизировать ${𝐬}^T\mathrm{\nabla }f({𝐱}_k)$

при условиях $𝐬\in 𝒟$

(Интерпретация: Минимизируем линейное приближение задачи, полученное аппроксимацией Тейлора первого порядка функции $f$ около ${𝐱}_k$.)

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

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

Свойства

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

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

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

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

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

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

Поскольку функция $f$ выпукла, для любых двух точек $𝐱,𝐲\in 𝒟$ имеем:

$f(𝐲)⩾f(𝐱)+(𝐲-𝐱{)}^T\mathrm{\nabla }f(𝐱)$

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

$\begin{array}{cc}f({𝐱}^{*})& ⩾f(𝐱)+({𝐱}^{*}-𝐱{)}^T\mathrm{\nabla }f(𝐱)\\ & ⩾\underset{𝐲\in D}{\min }\{f(𝐱)+(𝐲-𝐱{)}^T\mathrm{\nabla }f(𝐱)\}\\ & =f(𝐱)-{𝐱}^T\mathrm{\nabla }f(𝐱)+\underset{𝐲\in D}{\min }{𝐲}^T\mathrm{\nabla }f(𝐱)\end{array}$

Эта последняя задача решается на каждой итерации алгоритма Франк — Вульфа, поэтому решение ${𝐬}_k$ подзадачи нахождения направления на $k$-й итерации может быть использовано для определения возрастающих нижних границ $l_k$ на каждой итерации путём присвоения $l_0=-\mathrm{\infty }$ и

$l_k:=\max (l_{k-1},f({𝐱}_k)+({𝐬}_k-{𝐱}_k{)}^T\mathrm{\nabla }f({𝐱}_k))$

Такие нижние границы на неизвестное оптимальное значение на практике очень важны, поскольку могут быть использованы как критерий остановки алгоритма и дают эффективный показатель качества приближения на каждой итерации, поскольку всегда $l_k⩽f({𝐱}^{*})⩽f({𝐱}_k)$.

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья (Обзорная статья)
• Описание алгоритма Франк – Вульфа
• Шаблон:Книга
• Шаблон:Cite journal

Ссылка

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

См. также

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