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

Покоординатный спуск для выпуклой квадратичной функции

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

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

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

Формула

x_i^{+}=x_i-\frac{(Ax-b)_i}{A_{ii}},\quad f(x)=\tfrac12x^TAx-b^Tx

Схема Последовательные координатные шаги

Траектория для A=((2,1),(1,2)), b=(1,1): (0,0) → (0,5;0) → (0,5;0,25) → (0,375;0,25) → (0,375;0,3125).

Обозначения

$A$: симметричная положительно определённая матрица цели, безразмерная
$b$: вектор линейной части, безразмерная
$xᵢ,xᵢ⁺$: старая и новая выбранная координата, безразмерная
$(Ax−b)ᵢ$: компонента градиента до этого обновления, безразмерная
$i$: номер выбранной координаты, безразмерная

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

Здесь рассматривается безусловная квадратичная задача с A=Aᵀ≻0. Координата выбирается из фиксированного набора, например циклически; после каждого обновления используются уже изменённые значения предыдущих координат. Диагональные элементы Aᵢᵢ строго положительны.

Ограничения

Формула с Aᵢᵢ относится к квадратичной цели; для произвольной гладкой функции одномерный минимум может требовать отдельного поиска. Корреляция координат способна замедлять сходимость. При ограничениях на переменные свободное обновление может оказаться недопустимым.

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

При сдвиге только координаты i на δ изменение цели равно δ(Ax−b)ᵢ+Aᵢᵢδ²/2. Производная этой параболы по δ обращается в нуль при δ=−(Ax−b)ᵢ/Aᵢᵢ. Так как Aᵢᵢ>0, найденная точка действительно минимизирует функцию вдоль выбранной координатной прямой.

Уменьшение цели за точное обновление равно −gᵢ²/(2Aᵢᵢ). Поэтому функция не возрастает; равенство получается, если выбранная компонента градиента уже нулевая. При этом остальные компоненты после шага обычно изменяются, и нулевая ранее производная может снова стать ненулевой.

В циклическом варианте координаты проходят по очереди. В формуле для второй координаты уже участвует новое значение первой. Это важное отличие от одновременного диагонального шага: применение всех поправок к одной старой точке является другим алгоритмом и не наследует автоматически монотонность покоординатной минимизации.

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

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

Запишите цель в виде xᵀAx/2−bᵀx и проверьте симметрию с положительной определённостью A; особенно внимательно учтите смешанный член.
Для выбранного номера i вычислите текущую компоненту Ax−b и разделите её на Aᵢᵢ, сохранив знак минус в поправке.
Измените только координату i и обновите градиент или невязку; следующая координата должна видеть уже обновлённый вектор.
После полного обхода сравните цель и норму полного градиента с предыдущими значениями; продолжайте до выбранного допуска.

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

Покоординатная минимизация принадлежит традиции сведения многомерной задачи к последовательности одномерных. Для квадратичной цели условия стационарности образуют линейную систему, поэтому последовательные обновления тесно связаны с итерацией Гаусса — Зейделя. Это связь алгоритмов, а не основание приписать всю современную оптимизацию одному автору.

Вычислительная литература XX и XXI веков рассматривает разные правила выбора координат: циклические, случайные и основанные на величине производной. Они не взаимозаменяемы при доказательствах скорости. Работа Dahl, Vandenberghe и Roychowdhury о выборе ковариаций описывает конкретное применение точных обновлений одной переменной.

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

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

У точного покоординатного обновления квадратичной функции нет необходимости назначать единственного изобретателя: это следствие минимизации одномерной параболы. Последовательный обход связан с методом Гаусса — Зейделя для линейных систем, но современные варианты выбора координат имеют собственный анализ.

Пример

Пусть A=((2,1),(1,2)), b=(1,1), x⁰=(0,0); тогда f=x₁²+x₁x₂+x₂²−x₁−x₂. Сначала g₁=−1 и A₁₁=2, поэтому x₁=0−(−1)/2=1/2. Затем с новым x₁ получаем g₂=1/2−1=−1/2, так что x₂=1/4. После первого цикла x=(1/2,1/4), f=1/4+1/8+1/16−3/4=−5/16. Второй цикл даёт x₁=(1−1/4)/2=3/8, x₂=(1−3/8)/2=5/16. Точный минимум системы Ax=b равен (1/3,1/3). Последовательные координаты приближаются к нему, а значения цели−0,3125 и−0,33203125 согласуются с минимальным−1/3. Ненулевой остаточный градиент после первого цикла равен(1/4,0); он показывает, что одного обхода недостаточно.

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

Не берите коэффициент при xᵢ² за Aᵢᵢ без множителя 1/2 из определения цели. Не обновляйте все координаты из старого градиента, называя это тем же циклическим методом. Не останавливайтесь по одной нулевой производной. Снижение функции за один шаг не говорит, что уже найден общий минимум.

Практика

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

Диагональная цель

Условие. A=diag(2,8), b=(4,8), старт(0,0). Выполните один цикл.

Решение. x₁=0−(−4)/2=2; x₂=0−(−8)/8=1. Смешанного члена нет; Ax−b=(0,0).

Ответ. Минимум(2,1) за один цикл.

Падение цели за координату

Условие. Для A₁₁=4 и текущего g₁=6 найдите δ и изменение f.

Решение. δ=−6/4=−1,5. Δf=6·(−1,5)+4·2,25/2=−9+4,5=−4,5.

Ответ. δ=−1,5; Δf=−4,5.

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

https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
https://seas.ucla.edu/~vandenbe/publications/covsel1.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$

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

Математика

Метод Ньютона для минимума: шаг через матрицу Гессе

$H_k d_k=-g_k,\qquad x_{k+1}=x_k+\alpha_k d_k$

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

Математика

Критерий наименьших квадратов

$\hat x_{\mathrm{LS}}=\arg\min_{x\in\mathbb R^n} \|Ax-b\|_2^2 = \arg\min_x (Ax-b)^\top (Ax-b).$

Критерий наименьших квадратов измеряет суммарную квадратичную ошибку между наблюдаемым вектором b и моделью Ax, поэтому превращает переопределенную систему в задачу минимизации.