Математика / Начала анализа

Метод Франка — Вульфа: линейный подшаг на симплексе

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

Опубликовано: 28 октября 2026 г.Обновлено: 28 октября 2026 г.

Математический анализ Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

s_k\in\arg\min_{s\in C}\nabla f(x_k)^Ts,\quad x_{k+1}=(1-\gamma_k)x_k+\gamma_k s_k

Схема Линейная вершина и минимум на отрезке

На симплексе x₁+x₂=1 путь между вершинами проходит через оптимальную смесь(1/2,1/2).

Обозначения

$C$: компактная выпуклая допустимая область, безразмерная
$sₖ$: решение линейной подзадачи, безразмерная
$γₖ$: вес новой вершины, от 0 до 1, безразмерная
$xₖ$: текущая допустимая точка, безразмерная
$g_FW$: разрыв Франка — Вульфа ∇f(xₖ)ᵀ(xₖ−sₖ), безразмерная

Условия применения

Рассматривается гладкая выпуклая f на окрестности непустого компактного выпуклого C. Старт принадлежит C, линейная подзадача решается точно, а γₖ находится в[0,1]. Стандартные оценки скорости требуют дополнительного контроля гладкости и подходящего выбора шага.

Ограничения

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

Подробное объяснение

В точке x линейная модель цели равна f(x)+∇f(x)ᵀ(s−x). Все не зависящие от s слагаемые можно отбросить, так что достаточно минимизировать ∇f(x)ᵀs по C. Найденная точка s задаёт направление s−x, а не новое решение исходной нелинейной задачи.

На вероятностном симплексе sᵢ≥0, ∑sᵢ=1 линейная форма является взвешенным средним компонент градиента. Её минимум равен наименьшей компоненте. Поэтому допустимо взять базисную вершину eⱼ для любого номера j с минимальным градиентом; при равенстве минимумов выбор неединственен.

Выпуклая комбинация(1−γ)x+γs сохраняет допустимость при 0≤γ≤1. Если старт уже разложен в смесь вершин, одна итерация добавляет не более одной новой вершины. Эта особенность полезна, когда нужно разреженное представление, хотя число ненулевых весов может постепенно расти.

Разрыв g_FW=∇f(x)ᵀ(x−s) неотрицателен, ведь x тоже допустима для линейной подзадачи. Из выпуклости следует f(x)−f*≤g_FW. Он даёт вычислимую верхнюю оценку ошибки по значению цели. Нулевой разрыв означает оптимальность в выпуклой постановке; это сильнее произвольного малого изменения итераций.

Как пользоваться формулой

Вычислите все компоненты градиента в текущей допустимой точке; на симплексе выберите номер с наименьшей компонентой.
Решите линейную подзадачу и найдите направление sₖ−xₖ; отдельно вычислите разрыв для контроля качества текущего решения.
Выберите γ в пределах[0,1] по одномерному поиску или подходящему правилу; вся следующая точка должна остаться на отрезке.
Пересчитайте цель и разрыв после перехода; прекращайте вычисление по оценке ошибки, а не по факту выбора знакомой вершины.

Историческая справка

Метод носит имена Marguerite Frank и Philip Wolfe; их работа об алгоритме квадратичного программирования опубликована в 1956 году. Его ключевая идея — использовать линейную подзадачу вместо непосредственного решения нелинейной задачи на всей допустимой области.

В литературе также используется название «условный градиент». Обзор Braun и соавторов «Conditional Gradient Methods» 2022 года рассматривает исходный алгоритм и развитие его вариантов. Он подчёркивает различие между доступом к области через линейную минимизацию и через проекцию.

Современные приложения добавили интерес к разреженным выпуклым комбинациям, задачам большого размера и вычислимым разрывам оптимальности. При этом базовая геометрия остаётся простой: линейная модель выбирает опорную точку, а движение идёт по допустимому отрезку. Модификации выбора шага и вершин требуют собственного анализа.

Историческая линия формулы

Именование связано с работой Frank и Wolfe1956 года по квадратичному программированию. Термин «условный градиент» и многочисленные последующие варианты относятся к более широкой истории метода; оценки и ускорения нельзя автоматически приписывать исходной статье.

Пример

На симплексе x₁+x₂=1, xᵢ≥0 минимизируем f=(x₁²+x₂²)/2. Из x=(1,0) градиент=(1,0), поэтому линейный минимум s=(0,1). Разрыв равен(1,0)·((1,0)−(0,1))=1. На отрезке x(γ)=(1−γ,γ) цель равна((1−γ)²+γ²)/2; производная−1+2γ, минимум при γ=1/2. Получаем x⁺=(1/2,1/2), f=1/4 вместо 1/2. В новой точке компоненты градиента равны, любая вершина решает линейную подзадачу, и g_FW=0. Проверка по неравенству x₁²+x₂²≥(x₁+x₂)²/2=1/2 независимо подтверждает найденный глобальный минимум. Вся проверка использует одну и ту же допустимую сумму координат, равную единице.

Частая ошибка

Не принимайте выбранную вершину за решение исходной квадратичной задачи: нужен ещё вес γ. Не выбирайте максимальную компоненту градиента вместо минимальной. Разрыв требует текущего градиента и точной линейной подзадачи. За пределами выпуклой постановки не называйте его гарантией глобального минимума.

Практика

Задачи с решением

Линейный минимум

Условие. На трёхмерном симплексе градиент=(2,−1,3), x=(0,2;0,5;0,3). Найдите s и разрыв.

Решение. Минимальна вторая компонента, s=(0,1,0). gᵀx=0,4−0,5+0,9=0,8; gᵀs=−1, разрыв 1,8.

Ответ. s=(0,1,0); g_FW=1,8.

Сохранение суммы

Условие. Для x=(1,0,0), s=(0,0,1), γ=1/4 найдите обновление.

Решение. (1−1/4)x+(1/4)s=(3/4,0,1/4). Все компоненты неотрицательны; сумма равна 1.

Ответ. (0,75;0;0,25), точка допустима.

Дополнительные источники

https://conditional-gradients.org/
https://www.cambridge.org/core/books/optimization-for-data-analysis/firstorder-methods-for-constrained-optimization/A7AE6A1D5FE6BBAE9C387A001DAE0E6F

Связанные формулы

Математика

Проекционный градиент: минимум с ограничениями на переменные

$x_{k+1}=\Pi_C(x_k-\alpha\nabla f(x_k))$

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

Математика

Правило Армихо: обратный поиск длины шага спуска

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

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

Математика

Градиентный спуск с постоянным шагом: условие убывания

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

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