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

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

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

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

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

Формула

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

Схема Шаг за границу и возврат в квадрат

Для цели (x−2)²+(y+1)² серый вектор идёт к z=(2,−1), красный показывает проекцию z на [0,1]².

Обозначения

$C$: непустое замкнутое выпуклое множество, безразмерная
$Π꜀(z)$: ближайшая к z допустимая точка в евклидовой норме, безразмерная
$α$: положительный размер шага, безразмерная
$∇f(xₖ)$: градиент гладкой цели, безразмерная
$xₖ$: текущая допустимая точка, безразмерная

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

Множество C непусто, замкнуто и выпукло, поэтому евклидова проекция единственна. Для стандартной гарантии берут выпуклую дифференцируемую f с L-липшицевым градиентом и постоянный шаг 0<α≤1/L. Здесь предполагается, что минимум достигается.

Ограничения

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

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

Пусть z=x−α∇f(x) вышла за ограничения. Проекция Π꜀(z) решает задачу minᵤ∈꜀ ‖u−z‖². Она выбирает ближайший допустимый вектор, а не обрезает длину направления до первого пересечения с границей. Эти две операции совпадают лишь в отдельных простых ситуациях.

Для C=∏[lᵢ,uᵢ] расстояние раскладывается в сумму независимых квадратов. Поэтому каждая координата проекции равна min(uᵢ,max(lᵢ,zᵢ)). Для полупространства, симплекса или шара формулы другие: соблюдение одного ограничения может требовать совместного изменения нескольких компонент.

В ограниченном минимуме x* равен Π꜀(x*−α∇f(x*)). На границе градиент способен оставаться ненулевым, поскольку направление уменьшения уходит за допустимую область. Условие оптимальности для выпуклой цели: ∇f(x*)ᵀ(y−x*)≥0 для всех y∈C.

Для оценки остановки удобно использовать градиентное отображение Gα(x)=(x−Π꜀(x−α∇f(x)))/α. Его нуль отражает ограниченную стационарность. Проверять один лишь малый шаг без учёта α опасно: искусственно маленькая длина шага также даёт малое перемещение далеко от решения.

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

Опишите допустимое множество и найдите именно его евклидову проекцию; для связанных ограничений простое отсечение координат неверно.
Вычислите градиент и пробную точку z=xₖ−α∇f(xₖ); до проекции разрешено временно выйти за границу допустимой области.
Вычислите ближайшую допустимую точку Π꜀(z), затем проверьте все ограничения и значение целевой функции в новом векторе.
Контролируйте норму градиентного отображения вместе с целью; ненулевой обычный градиент на активной границе не исключает минимум.

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

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

В книге Wright и Recht «Optimization for Data Analysis», опубликованной в 2022 году, проекционный градиент рассматривается в главе о методах первого порядка с ограничениями. Там операция проекции отделяется от линейного подшага условного градиента. Это полезное историко-учебное сопоставление двух вычислительных традиций.

Современная запись через Π꜀ компактно охватывает интервалы, неотрицательный ортант и другие выпуклые области. Она не делает вычисление проекции одинаково простым во всех случаях. Доступность этой операции остаётся одним из главных оснований выбора алгоритма.

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

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

Пример

Минимизируем f(x,y)=(x−2)²+(y+1)² на квадрате C=[0,1]². Градиент равен(2(x−2),2(y+1)); L=2. Из(0,5;0,5) при α=1/2 получаем z=(2,−1). Проекция отсечением координат даёт(1,0). До шага цель равнялась 2,25+2,25=4,5, после —1+1=2. Безусловный минимум(2,−1) недопустим. В точке(1,0) градиент=(−2,2), но повторный шаг снова проектируется в(1,0). Для любого допустимого y=(u,v) скалярное произведение с y−x* равно 2(1−u)+2v≥0. Это независимо подтверждает ограниченный глобальный минимум и объясняет, почему требование нулевого градиента здесь было бы неверным.

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

Не приравнивайте ограниченный минимум к нулю обычного градиента. Не применяйте отсечение координат к суммарному ограничению вроде x₁+x₂=1. Не путайте евклидову проекцию с нормировкой вектора. Малое перемещение при очень малом α не заменяет проверку градиентного отображения.

Практика

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

Интервал

Условие. f(x)=(x−3)²/2, C=[0,2], x₀=0, α=1. Найдите новый x.

Решение. f′(0)=−3; z=3. Проекция на[0,2] равна 2. f меняется с 4,5 до 0,5; градиент в 2 равен−1.

Ответ. x₁=2 — ограниченный минимум.

Проекция на полупространство

Условие. Проецируйте z=(2,2) на x+y≤1.

Решение. Нормаль a=(1,1); превышение aᵀz−1=3, ‖a‖²=2. Вычитаем(3/2)a: результат(0,5;0,5).

Ответ. (0,5;0,5), сумма координат 1.

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

https://www.cambridge.org/core/books/optimization-for-data-analysis/firstorder-methods-for-constrained-optimization/A7AE6A1D5FE6BBAE9C387A001DAE0E6F
https://www.cs.yale.edu/homes/vishnoi/Nisheeth-VishnoiFall2014-ConvexOptimization.pdf

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

Математика

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

$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$

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

Математика

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

$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$

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

Математика

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

$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$

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