Метод наискорейшего спуска

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM GPT-5.6 Sol и проверена участником Kirill Solovev 12:13, 19 июля 2026 (MSD)

Содержание

1 История и терминология
2 Постановка задачи
3 Направление наискорейшего спуска
- 3.1 Евклидова норма
- 3.2 Произвольная норма
4 Алгоритм
5 Выбор длины шага
- 5.1 Точный линейный поиск
- 5.2 Неточный линейный поиск
6 Отличие от градиентного спуска
7 Квадратичная функция
8 Сходимость
9 Преимущества и недостатки
10 Применение в машинном обучении
11 Связанные методы
12 См. также
13 Литература

Метод наискорейшего спуска (англ. steepest descent method, также метод Коши) — итерационный метод оптимизации первого порядка для минимизации дифференцируемой функции. На каждой итерации метод выбирает направление, в котором линейное приближение функции убывает быстрее всего среди направлений единичной длины, а затем определяет длину шага с помощью одномерной минимизации или приближённого линейного поиска.

В евклидовой норме направлением наискорейшего спуска является направление, противоположное градиенту, то есть антиградиент. Поэтому евклидова версия метода тесно связана с градиентным спуском. Названия этих методов нередко употребляются как синонимы, однако термин «наискорейший спуск» подчёркивает геометрический выбор направления относительно заданной нормы, а в классической формулировке часто предполагает точный линейный поиск.

История и терминология

Один из первых вариантов метода был предложен Огюстеном Луи Коши в 1847 году при рассмотрении численного решения систем нелинейных уравнений. Поэтому метод наискорейшего спуска также называют методом Коши.

В литературе используются две близкие трактовки метода:

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

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

Постановка задачи

Рассматривается задача безусловной минимизации

$\min_{x\in\mathbb{R}^n} f(x),$

где $f:\mathbb{R}^n\to\mathbb{R}$ — непрерывно дифференцируемая функция. В точке $x$ её градиент имеет вид

$\nabla f(x)=\left(\frac{\partial f(x)}{\partial x_1},\ldots,\frac{\partial f(x)}{\partial x_n}\right)^{\mathsf T}.$

Для малого смещения $h$ справедливо разложение первого порядка

$f(x+h)=f(x)+\langle \nabla f(x),h\rangle+o(\left\| h\right\|).$

Следовательно, величина

$f'(x;d)=\langle\nabla f(x),d\rangle$

является производной по направлению $d$ . Направление $d$ называется направлением спуска, если

$\langle\nabla f(x),d\rangle<0.$

При достаточно малом положительном шаге движение в таком направлении уменьшает значение функции.

Направление наискорейшего спуска

Евклидова норма

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

$d_{\mathrm{sd}}\in\operatorname*{arg\,min}_{\left\|d\right\|_2 \leq 1}\langle\nabla f(x),d\rangle.$

По неравенству Коши — Буняковского

Если $\nabla f(x)\neq 0$ , равенство достигается при

$d_{\mathrm{sd}}=-\frac{\nabla f(x)}{\left\|\nabla f(x)\right\|_2}.$

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

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

Если $\nabla f(x)=0$ , точка является стационарной. Для невыпуклой функции она может быть минимумом, максимумом или седловой точкой.

Произвольная норма

Понятие «самого быстрого» направления не имеет смысла без способа измерения длины перемещения. Пусть на пространстве задана норма $\left\|\cdot\right\|$ . Тогда нормированное направление наискорейшего спуска определяется как

$d_{\mathrm{sd}}\in\operatorname*{arg\,min}_{\left\| d\right\|\leq 1}\langle\nabla f(x),d\rangle.$

Связанная с исходной нормой двойственная норма задаётся равенством

$\left\| g\right\|_*=\max_{\left\| d\right\|\leq 1}\langle g,d\rangle.$

Поэтому

$\min_{\left\| d\right\|\leq 1}\langle\nabla f(x),d\rangle=-\left\|\nabla f(x)\right\|_*.$

Геометрически направление определяется точкой единичного шара, в которой линейная функция $\langle\nabla f(x),d\rangle$ принимает минимальное значение. Если единичный шар не является строго выпуклым, направление может быть не единственным.

Норма перемещения	Направление наискорейшего спуска	Интерпретация
$\left\\| d\right\\|_2$	$d=-\nabla f/\left\\|\nabla f\right\\|_2$	Обычное направление антиградиента
$\left\\| d\right\\|_B=\sqrt{d^{\mathsf T}Bd}$ , $B\succ 0$	Удобное ненормированное направление $p=-B^{-1}\nabla f$	Масштабирование координат или предобусловленный градиентный метод
$\left\\| d\right\\|_1$	$d=-\operatorname{sign}(g_{i_})e_{i_}$ , где $i_\in\operatorname{arg\,max}_i \|g_i\|$	Изменяется координата с наибольшей по модулю компонентой градиента
$\left\\| d\right\\|_\infty$	$d_i=-\operatorname{sign}(g_i)$	Все координаты могут изменяться одновременно с одинаковым предельным модулем

Здесь $g=\nabla f(x)$ , $e_i$ — стандартный базисный вектор. Для квадратичной нормы нормированное направление имеет вид

$d_{\mathrm{sd}}=-\frac{B^{-1}\nabla f(x)}{\sqrt{\nabla f(x)^{\mathsf T}B^{-1}\nabla f(x)}}.$

Выбор матрицы $B$ эквивалентен изменению геометрии пространства или линейному преобразованию координат. Удачно выбранная метрика может существенно ускорить движение по вытянутым линиям уровня. На этой идее основаны методы предобуславливания и некоторые обобщения градиентных методов.

Строго говоря, дифференциал функции является линейным функционалом, а представление этого функционала вектором-градиентом зависит от выбранного скалярного произведения. Обычный вектор $\nabla f$ соответствует стандартному евклидову скалярному произведению.

Алгоритм

Пусть задано начальное приближение $x_0$ . Одна итерация метода состоит из следующих действий.

Вычислить градиент
$g_k=\nabla f(x_k).$
Если градиент достаточно мал, завершить работу.
Выбрать направление наискорейшего спуска. В евклидовой норме удобно использовать ненормированное направление
$p_k=-g_k.$
Определить длину шага $\alpha_k>0$ .
Выполнить обновление
$x_{k+1}=x_k+\alpha_k p_k.$

Масштабирование направления и обратное масштабирование длины шага не изменяют новую точку. Поэтому при точном линейном поиске можно использовать как нормированное направление $-g_k/\left\| g_k\right\|_2$ , так и ненормированный антиградиент $-g_k$ .

В качестве критериев остановки применяются условия

$\left\|\nabla f(x_k)\right\|_*\leq\varepsilon,$

$\left\| x_{k+1}-x_k\right\|\leq\varepsilon_x(1+\left\| x_k\right\|)$

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

Выбор длины шага

Точный линейный поиск

В классическом методе наискорейшего спуска длина шага является решением одномерной задачи

$\alpha_k\in\operatorname*{arg\,min}_{\alpha\geq 0}f(x_k+\alpha p_k).$

Если минимум достигается во внутренней точке и функция дифференцируема, то

$\frac{d}{d\alpha}f(x_k+\alpha p_k)\|_{\alpha=\alpha_k}=\nabla f(x_{k+1})^{\mathsf T}p_k=0.$

Следовательно, после точного линейного поиска новый градиент ортогонален предыдущему направлению движения.

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

Неточный линейный поиск

На практике часто достаточно найти шаг, обеспечивающий приемлемое уменьшение функции. Условие Армихо имеет вид

$f(x_k+\alpha_kp_k)\leq f(x_k)+c_1\alpha_k\nabla f(x_k)^{\mathsf T}p_k,\qquad 0<c_1<1.$

Обычно оно проверяется методом возврата шага: начальное значение $\alpha$ последовательно умножается на число из интервала $(0,1)$ , пока условие не будет выполнено.

Условия Вольфе дополняют достаточное уменьшение условием кривизны

$\nabla f(x_k+\alpha_kp_k)^{\mathsf T}p_k\geq c_2\nabla f(x_k)^{\mathsf T}p_k,\qquad 0<c_1<c_2<1.$

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

Если градиент функции липшицев с константой $L$ , то в евклидовой версии можно использовать постоянный шаг. Например, шаг $\alpha=1/L$ гарантирует уменьшение функции.

Отличие от градиентного спуска

Градиентный спуск обычно записывается в виде

$x_{k+1}=x_k-\eta_k\nabla f(x_k),$

где $\eta_k$ может быть постоянным, убывающим, адаптивным или найденным линейным поиском.

Основные различия в употреблении терминов состоят в следующем.

Свойство	Метод наискорейшего спуска	Градиентный спуск в широком смысле
Выбор направления	Решается задача максимального локального убывания относительно заданной нормы	Обычно используется отрицательный евклидов градиент
Выбор шага	В классической формулировке применяется точный линейный поиск; возможен и неточный	Шаг может задаваться практически любым правилом
Геометрия	Явно зависит от нормы или метрики	Обычно подразумевается стандартная евклидова геометрия
Используемый градиент	Как правило, полный градиент целевой функции	Может использоваться полный, пакетный или стохастический градиент

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

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

Квадратичная функция

Для квадратичной функции

$f(x)=\frac{1}{2}x^{\mathsf T}Ax-b^{\mathsf T}x+c,$

где $A=A^{\mathsf T}\succ 0$ , градиент равен

$g_k=Ax_k-b.$

При направлении $p_k=-g_k$ точная длина шага вычисляется явно:

$\alpha_k=\frac{g_k^{\mathsf T}g_k}{g_k^{\mathsf T}Ag_k}.$

Действительно, подстановка $x_k-\alpha g_k$ в квадратичную функцию даёт одномерный квадратный трёхчлен, минимум которого достигается при указанном значении $\alpha_k$ .

Для последовательных градиентов выполняется равенство

$g_{k+1}^{\mathsf T}g_k=0.$

Таким образом, при точном линейном поиске последовательные направления движения ортогональны. Это свойство не означает быстрой сходимости. Если линии уровня сильно вытянуты, метод может многократно пересекать узкую долину, двигаясь зигзагообразно.

Пусть

$\kappa(A)=\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$

— спектральное число обусловленности матрицы. Для минимума $x_*=A^{-1}b$ справедлива оценка

$f(x_{k+1})-f(x_*)\leq\left(\frac{\kappa(A)-1}{\kappa(A)+1}\right)^2\bigl(f(x_k)-f(x_*)\bigr).$

При большом $\kappa(A)$ коэффициент близок к единице, и сходимость становится медленной. Предобуславливание стремится заменить исходную геометрию такой, в которой эффективное число обусловленности меньше.

Сходимость

Пусть градиент функции липшицев с константой $L$ :

$\left\|\nabla f(x)-\nabla f(y)\right\|_2\leq L\left\| x-y\right\|_2.$

Для евклидова градиентного шага справедлива оценка

$f(x-\alpha\nabla f(x))\leq f(x)-\alpha\left(1-\frac{L\alpha}{2}\right)\left\|\nabla f(x)\right\|_2^2.$

Поэтому любой постоянный шаг $0<\alpha<2/L$ обеспечивает уменьшение функции, пока градиент отличен от нуля. В частности, при $\alpha=1/L$

$f(x_{k+1})\leq f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|_2^2.$

Если функция ограничена снизу значением $f_{\inf}$ , то

$\min_{0\leq i<k}\left\|\nabla f(x_i)\right\|_2^2\leq\frac{2L\bigl(f(x_0)-f_{\inf}\bigr)}{k}.$

Для выпуклой функции с точкой минимума $x_*$ градиентный метод с шагом $1/L$ имеет оценку

$f(x_k)-f(x_*)\leq\frac{L\left\| x_0-x_*\right\|_2^2}{2k}.$

Пусть дополнительно функция является $\mu$ -сильно выпуклой. Для метода с точным линейным поиском установлена точная оценка наихудшего случая

$f(x_{k+1})-f(x_*)\leq\left(\frac{L-\mu}{L+\mu}\right)^2\bigl(f(x_k)-f(x_*)\bigr).$

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

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

Преимущества и недостатки

К преимуществам метода относятся:

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

Основные недостатки:

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

Применение в машинном обучении

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

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

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

Связанные методы

Метод сопряжённых градиентов строит взаимно сопряжённые направления и для положительно определённой квадратичной задачи в точной арифметике находит решение не более чем за $n$ итераций.
Метод Ньютона использует направление $-\nabla^2 f(x)^{-1}\nabla f(x)$ и учитывает локальную кривизну функции.
Квазиньютоновские методы приближают обратный гессиан по информации, накопленной на предыдущих итерациях.
Координатный спуск связан с направлением наискорейшего спуска относительно нормы $\ell_1$ .
Проекционный градиентный метод дополняет градиентный шаг проекцией на допустимое множество.
Зеркальный спуск задаёт геометрию перемещения с помощью дивергенции, а не только фиксированной нормы.

См. также

Литература

Cauchy A.-L. Méthode générale pour la résolution des systèmes d'équations simultanées // Comptes rendus hebdomadaires des séances de l'Académie des sciences. — 1847. — Т. 25. — С. 536—538.

Goldstein A. A. Cauchy's Method of Minimization // Numerische Mathematik. — 1962. — Т. 4. — С. 146—150.

Armijo L. Minimization of Functions Having Lipschitz Continuous First Partial Derivatives // Pacific Journal of Mathematics. — 1966. — Т. 16. — № 1. — С. 1—3.

Wolfe P. Convergence Conditions for Ascent Methods // SIAM Review. — 1969. — Т. 11. — № 2. — С. 226—235.

de Klerk E., Glineur F., Taylor A. B. On the Worst-Case Complexity of the Gradient Method with Exact Line Search for Smooth Strongly Convex Functions // Optimization Letters. — 2017. — Т. 11. — № 7. — С. 1185—1199.

Hestenes M. R., Stiefel E. Methods of Conjugate Gradients for Solving Linear Systems // Journal of Research of the National Bureau of Standards. — 1952. — Т. 49. — № 6. — С. 409—436.

Nocedal J., Wright S. J. Numerical Optimization. — 2-е изд.. — New York: Springer, 2006. — 664 с. — ISBN 978-0-387-30303-1

Boyd S., Vandenberghe L. Convex Optimization. — Cambridge: Cambridge University Press, 2004. — 716 с. — ISBN 978-0-521-83378-3

Boyd S.; Vandenberghe L. Convex Optimization — Boyd and Vandenberghe // Stanford University. 2026-07-19.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D1%81%D0%BA%D0%BE%D1%80%D0%B5%D0%B9%D1%88%D0%B5%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0»

Категории: Методы оптимизации | Выпуклая оптимизация | Машинное обучение

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM '''Название Версия''' и проверена участником [[Участник:Kirill Solovev|Kirill Solovev]] 12:13, 19 июля 2026 (MSD)}}
+{{well|Статья написана с использованием LLM '''GPT-5.6 Sol''' и проверена участником [[Участник:Kirill Solovev|Kirill Solovev]] 12:13, 19 июля 2026 (MSD)}}
 {{TOCright}}
 '''Метод наискорейшего спуска''' (англ. ''steepest descent method'', также '''метод Коши''') — итерационный [[Методы оптимизации|метод оптимизации]] первого порядка для минимизации [[Дифференцируемая функция|дифференцируемой функции]]. На каждой итерации метод выбирает направление, в котором линейное приближение функции убывает быстрее всего среди направлений единичной длины, а затем определяет длину шага с помощью [[Одномерная оптимизация|одномерной минимизации]] или приближённого [[Линейный поиск|линейного поиска]].