Перегляд вихідного коду сторінки Градієнтний спуск

{{Hatnote|Ця стаття про алгоритм оптимізації. Про метод наближення інтегралів у [[Математичний аналіз|математичному аналізі]] див. {{нп|Метод перевалу|||Method of steepest descent}}}}

'''Градіє́нтний спуск''' ({{lang-en|gradient descent}})&nbsp;— це [[Ітераційний метод|ітераційний]] [[алгоритм]] [[Оптимізація (математика)|оптимізації]] [[Чисельні методи#Порядок методу|першого порядку]], в якому для знаходження [[Локальний мінімум|локального мінімуму]] функції здійснюються кроки, пропорційні ''протилежному значенню'' [[градієнт]]у (або наближеного градієнту) функції в поточній точці. Якщо натомість здійснюються кроки пропорційно ''самому'' значенню градієнту, то відбувається наближення до [[Локальний максимум|локального максимуму]] цієї функції; і ця процедура тоді відома як '''градіє́нтний підйо́м''' ({{lang-en|gradient ascent}}).

Градієнтний спуск відомий також як '''найшви́дший спуск''' ({{lang-en|steepest descent}}), або '''ме́тод найшви́дшого спу́ску''' ({{lang-en|method of steepest descent}}). Градієнтний спуск не слід плутати з {{нп|Метод перевалу|методом перевалу||Method of steepest descent}} для наближення інтегралів.

== Опис ==
[[Файл:gradient descent.svg|thumb|350px|Ілюстрація методу найшвидшого спуску на ряді [[Множина рівня|множин рівнів]].]]

Градієнтний спуск ґрунтується на тому спостереженні, що якщо {{нп|Функція кількох дійсних змінних|функція кількох змінних||Function of several real variables}} <math>F(\mathbf{x})</math> є {{нп|Визначеність та невизначеність|визначеною||Defined and undefined}} та [[Диференційовна функція|диференційовною]] в околі точки <math>\mathbf{a}</math>, то <math>F(\mathbf{x})</math> зменшується ''найшвидше'', якщо йти від <math>\mathbf{a}</math> в напрямку, протилежному градієнтові <math>F</math> в <math>\mathbf{a}</math>, <math>-\nabla F(\mathbf{a})</math>. З цього випливає, що якщо

: <math> \mathbf{b} = \mathbf{a}-\gamma\nabla F(\mathbf{a})</math>

для достатньо малого <math>\gamma</math>, то <math>F(\mathbf{a})\geq F(\mathbf{b})</math>. Іншими словами, член <math>\gamma\nabla F(\mathbf{a})</math> віднімається від <math>\mathbf{a}</math>, оскільки ми хочемо рухатися проти градієнту, тобто вниз до мінімуму. Враховуючи це спостереження, починають з припущення <math>\mathbf{x}_0</math> про локальний мінімум <math>F</math>, і розглядають таку послідовність <math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots</math>, що

: <math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>

Ми маємо

: <math>F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,</math>

і тому сподіваємося, що послідовність <math>(\mathbf{x}_n)</math> збігається до бажаного локального мінімуму. Зауважте, що значення ''розміру кроку'' ({{lang-en|step size}}) <math>\gamma</math> дозволено змінювати на кожній ітерації. Для деяких припущень стосовно функції <math>F</math> (наприклад, що <math>F</math> є [[Опукла функція|опуклою]], а <math>\nabla F</math> задовольняє [[Ліпшицеве відображення|умові Ліпшиця]]) і певних варіантах вибору <math>\gamma</math> (наприклад, якщо його вибирають [[Лінійний пошук в оптимізації|лінійним пошуком]], який задовольняє [[умови Вольфе]]), збіжність до локального мінімуму може бути гарантовано. Якщо функція <math>F</math> є [[Опукла функція|опуклою]], то всі локальні мінімуми є також і глобальними мінімумами, тому в такому випадку градієнтний спуск може збігатися до глобального розв'язку.

Цей процес проілюстровано на зображенні праворуч. Тут припускається, що <math>F</math> визначено на площині, і що її графік має форму [[Чаша|чаші]]. Сині криві є [[ізолінія]]ми, тобто областями, в яких значення <math>F</math> є сталим. Червоні стрілки, які виходять з точок, показують напрям, протилежний градієнтові в цій точці. Зауважте, що (анти)градієнт у точці є [[Ортогональність|ортогональним]] до ізолінії, яка проходить цією точкою. Видно, що ''спуск'' градієнтом веде нас до дна чаші, тобто до точки, в якій значення функції <math>F</math> є мінімальним.

=== Приклади ===

Градієнтний спуск має проблеми з патологічними функціями, такими як показана тут [[функція Розенброка]].

: <math>f(x_1, x_2) = (1-x_1)^2 + 100(x_2-x_1^2)^2 .\quad </math>

Функція Розенброка має вузьку вигнуту долину, яка містить мінімум. Дно цієї долини є дуже пологим. Через вигнутість пологої долини оптимізація повільно рухається в напрямку мінімуму зиґзаґом кроками малого розміру.

[[Файл:Banana-SteepDesc.gif|400px]]

«Зиґзаґоподібна» природа цього методу також є очевидною нижче, де градієнтний спуск застосовано до <math>F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)</math>.

{|
[[Файл:gradient ascent (contour).png|350px|The gradient descent algorithm in action. (1: contour)]]
[[Файл:gradient ascent (surface).png|450px|The gradient descent algorithm in action. (2: surface)]]
|}

=== Обмеження ===

Для деяких із наведених вище прикладів градієнтний спуск є відносно повільним поблизу мінімуму: з технічної точки зору, його асимптотичний темп збігання поступається багатьом іншим методам. Для невдало обумовлених опуклих задач градієнтний спуск «зиґзаґує» все більше, коли градієнт вказує майже ортогонально до найкоротшого напряму до точки мінімуму. Докладніше див. [[#Коментарі|коментарі]] нижче.

Для недиференційовних функцій градієнтні методи є недостатньо визначеними. Для локально [[Ліпшицеве відображення|ліпшицевих]] задач, та особливо для задач [[Опукла оптимізація|опуклої оптимізації]], цілком визначеними є [[Субградієнтний метод|в'язкові методи спуску]]. Також можуть застосовуватися не-спускові методи, такі як методи [[Субградієнтний метод|субградієнтної]] проєкції.<ref>{{Cite news|last=Kiwiel|first=Krzysztof C.|title=Convergence and efficiency of subgradient methods for quasiconvex minimization|journal=Mathematical Programming  (Series A)|publisher=Springer|location=Berlin, Heidelberg|issn=0025-5610|pages=1–25|volume=90|issue=1|doi=10.1007/PL00011414|year=2001|mr=1819784}} {{ref-en}}</ref> Ці методи зазвичай є повільнішими за градієнтний спуск. Іншою альтернативою для недиференційовних функцій є «згладжування» цих функцій, або обмеження функції гладкою функцією. За цього підходу розв'язують згладжену задачу в надії, що відповідь для неї є близькою до відповіді на незгладжену задачу (іноді це може бути зроблено строгим).

== Розв'язання лінійної системи ==

Градієнтний спуск може застосовуватися для розв'язання [[Система лінійних алгебраїчних рівнянь|системи лінійних рівнянь]], переформульованого як задача квадратичної мінімізації, наприклад, із застосуванням [[Метод найменших квадратів|методу найменших квадратів]]. Розв'язок

: <math>A\mathbf{x}-\mathbf{b}=0</math>

у сенсі методу найменших квадратів визначається як мінімізація функції

: <math>F(\mathbf{x})=\|A\mathbf{x}-\mathbf{b}\|^2.</math>

В традиційному методі найменших квадратів для дійсних <math>A</math> та <math>\mathbf{b}</math> використовується [[евклідова норма]], і в цьому випадку

: <math>\nabla F(\mathbf{x})=2A^T(A\mathbf{x}-\mathbf{b}).</math>

В такому випадку мінімізація [[Лінійний пошук в оптимізації|лінійним пошуком]], яка знаходить на кожній ітерації локально оптимальний розмір кроку <math>\gamma</math>, може виконуватися аналітично, і явні формули локально оптимального <math>\gamma</math> є відомими.<ref>{{cite journal
 | last = Yuan
 | first = Ya-xiang
 | title = Step-sizes for the gradient method
 | journal = AMS/IP Studies in Advanced Mathematics
 | volume = 42
 | issue = 2
 | pages = 785
 | publisher = American Mathematical Society
 | location = Providence, RI
 | year = 1999
 | url = ftp://lsec.cc.ac.cn/pub/yyx/papers/p0504.pdf
 | url-status = dead
 }} {{ref-en}}</ref>

Для розв'язання лінійних рівнянь градієнтний спуск застосовується рідко, а однією з найпопулярніших альтернатив є [[метод спряжених градієнтів]]. Швидкість збігання градієнтного спуску залежить від максимального та мінімального [[Власне значення матриці|власних значень]] <math>A</math>, тоді як швидкість збігання [[Метод спряженого градієнта|спряжених градієнтів]] має складнішу залежність від цих власних значень, і може отримувати користь від {{нп|передобумовлювання|||Preconditioner}}. Градієнтний спуск також отримує користь від передобумовлювання, але це не роблять так поширено.

== Розв'язання нелінійної системи ==

Градієнтний спуск може також застосовуватися і до розв'язання систем нелінійних рівнянь. Нижче наведено приклад, як застосовувати градієнтний спуск для розв'язання для трьох невідомих змінних, ''x''<sub>1</sub>, ''x''<sub>2</sub> та ''x''<sub>3</sub>. Цей приклад показує одну ітерацію градієнтного спуску.

Розгляньмо систему нелінійних рівнянь

: <math> \begin{cases}
3x_1-\cos(x_2x_3)-\tfrac{3}{2}=0 \\
4x_1^2-625x_2^2+2x_2-1=0  \\
\exp(-x_1x_2)+20x_3+\tfrac{10\pi-3}{3}=0
\end{cases}
</math>

припустімо, що ми маємо функцію

: <math> G(\mathbf{x}) = \begin{bmatrix}
3x_1-\cos(x_2x_3)-\tfrac{3}{2} \\
4x_1^2-625x_2^2+2x_2-1 \\
\exp(-x_1x_2)+20x_3+\tfrac{10\pi-3}{3} \\
\end{bmatrix} </math>

де

: <math> \mathbf{x} =\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
\end{bmatrix}</math>

та цільову функцію

: <math>F(\mathbf{x}) = \tfrac{1}{2} G^\mathrm{T}(\mathbf{x}) G(\mathbf{x}) =\tfrac{1}{2} \left ( \left (3x_1-\cos(x_2x_3)-\tfrac{3}{2} \right)^2 + \left (4x_1^2-625x_2^2+2x_2-1 \right )^2 + \left (\exp(-x_1x_2)+20x_3+\tfrac{1}{3}(10\pi-3) \right )^2 \right) </math>

з початковим припущенням

: <math> \mathbf{x}^{(0)}=\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
\end{bmatrix}
=\begin{bmatrix}
  0 \\
  0 \\
  0 \\ \end{bmatrix}</math>

Ми знаємо, що

: <math>\mathbf{x}^{(1)}=\mathbf{x}^{(0)}-\gamma_0 \nabla F(\mathbf{x}^{(0)})</math>

де

: <math>\nabla F(\mathbf{x}^{(0)})= J_G(\mathbf{x}^{(0)})^\mathrm{T}G(\mathbf{x}^{(0)})</math>

[[Матриця Якобі]] <math> J_G(\mathbf{x}^{(0)}) </math>
: <math>
J_G = \begin{bmatrix}
  3 & \sin(x_2x_3)x_3 & \sin(x_2x_3)x_2   \\
  8x_1 & -1250x_2+2 & 0 \\
  -x_2\exp{(-x_1x_2)} & -x_1\exp(-x_1x_2) & 20\\
\end{bmatrix}
</math>

Потім обчислімо ці члени в <math> \mathbf{x}^{(0)}</math>

: <math>
J_G \left(\mathbf{x}^{(0)}\right) = \begin{bmatrix}
  3 & 0 & 0\\
  0 & 2 & 0\\
  0 & 0 & 20
\end{bmatrix}, \qquad G(\mathbf{x}^{(0)}) = \begin{bmatrix}
  -2.5\\
  -1\\
  10.472
\end{bmatrix}</math>

Отже,

: <math>\mathbf{x}^{(1)}=0-\gamma_0 \begin{bmatrix}
  -7.5\\
  -2\\
  209.44
\end{bmatrix}</math>

та

: <math>F \left(\mathbf{x}^{(0)}\right) = 0.5 \left ((-2.5)^2 + (-1)^2 + (10.472)^2 \right ) = 58.456</math>

[[Файл:Gradient Descent Example Nonlinear Equations.gif|thumb|right|350px|Анімація, яка показує перші 83 ітерації градієнтного спуску, що застосовується до цього прикладу. Поверхні є [[ізоповерхня]]ми <math>F(\mathbf{x}^{(n)})</math> на поточному припущенні <math>\mathbf{x}^{(n)}</math>, а стрілки показують напрямок спуску. З причини малого та незмінного кроку збігання є повільним.]]

Тепер мусить бути знайдено придатний <math>\gamma_0</math>, такий що <math>F(\mathbf{x}^{(1)}) \le F(\mathbf{x}^{(0)})</math>. Це можна зробити за допомогою будь-якого з безлічі алгоритмів [[Лінійний пошук в оптимізації|лінійного пошуку]]. Можна також просто припустити <math>\gamma_0=0.001</math>, що дає

: <math> \mathbf{x}^{(1)}=\begin{bmatrix}
   0.0075  \\
   0.002   \\
  -0.20944 \\
\end{bmatrix}</math>

При обчисленні на цьому значенні

: <math>F \left(\mathbf{x}^{(1)}\right) = 0.5 \left ((-2.48)^2 + (-1.00)^2 + (6.28)^2 \right ) = 23.306</math>

Зменшення з <math> F(\mathbf{x}^{(0)})=58.456 </math> до значення наступного кроку <math> F(\mathbf{x}^{(1)})=23.306 </math> є відчутним зменшенням цільової функції. Подальші кроки знижуватимуть її значення доти, доки не буде знайдено розв'язок системи.

== Коментарі ==

Градієнтний спуск працює в просторах з будь-яким числом вимірів, навіть у [[Нескінченновимірний простір|нескінченновимірних]]. В останньому випадку простір пошуку зазвичай є [[Простір функцій|простором функцій]], і для визначення напрямку спуску здійснюється обчислення [[Похідна Гато|похідної Гато]] функціоналу, який мінімізують.<ref>G. P. Akilov, L. V. Kantorovich, Functional Analysis, Pergamon Pr; 2 Sub edition, ISBN 0-08-023036-9, 1982 {{ref-en}}</ref>

Якщо [[Кривина (математика)|кривина]] заданої функції дуже різниться в різних напрямках, то градієнтному спускові може знадобитися багато ітерацій для обчислення локального мінімуму з потрібною [[Точність|точністю]]. Для таких функцій повільне збігання лікується {{нп|Передобумовлювання|передобумовлюванням||Preconditioning}}, яке змінює геометрію простору так, щоби надати множинам рівнів функції форми [[Концентричність|концентричних кіл]]. Проте побудова та застосування передобумовлювання можуть бути обчислювально витратними.

Градієнтний спуск можна поєднувати з [[Лінійний пошук в оптимізації|лінійним пошуком]], який на кожній ітерації шукає локально оптимальний розмір кроку <math>\gamma</math>. Виконання лінійного пошуку може бути витратним за часом. З іншого боку, застосування незмінного малого <math>\gamma</math> може давати погану збіжність.

Кращими альтернативами можуть бути методи на основі [[Метод Ньютона в оптимізації|методу Ньютона]] та обернення [[Матриця Гессе|гессіану]] із застосуванням методик [[Метод спряженого градієнта|спряжених градієнтів]].<ref>W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, [[Numerical Recipes|Numerical Recipes in C: The Art of Scientific Computing]], 2nd Ed., Cambridge University Press, New York, 1992 {{ref-en}}</ref><ref>T. Strutz: ''Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond).'' 2nd edition, Springer Vieweg, 2016, ISBN 978-3-658-11455-8. {{ref-en}}</ref> Загалом такі методи збігаються за меншу кількість ітерацій, але вартість кожної ітерації є вищою. Прикладом є [[Метод БФГШ]], який складається з обчислення на кожному кроці матриці, на яку множиться вектор градієнту, щоби йти в «найкращому» напрямку, поєднаного зі складнішим алгоритмом [[Лінійний пошук в оптимізації|лінійного пошуку]] для знаходження «найкращого» значення <math>\gamma</math>. Для надзвичайно великих задач, у яких домінують питання комп'ютерної пам'яті, замість БФГШ або найшвидшого спуску повинні застосовуватися методи з обмеженою пам'яттю, такі як {{нп|Метод БФГШ з обмеженою пам'яттю|О-БФГШ||Limited-memory BFGS}}.

Градієнтний спуск може розглядатися як [[метод Ейлера]] для розв'язання [[Звичайне диференційне рівняння|звичайних диференційних рівнянь]] <math>x'(t)=-\nabla f(x(t))</math> [[Векторне поле|потоку градієнта]].

== Обчислювальні приклади ==

=== Python ===

Алгоритм градієнтного спуску застосовується для знаходження локального мінімуму функції ''f''(''x'')=''x''<sup>4</sup>−3''x''<sup>3</sup>+2 з похідною ''f''<nowiki>'</nowiki>(''x'')=4''x''<sup>3</sup>−9''x''<sup>2</sup>. Ось реалізація мовою програмування [[Python]].

<syntaxhighlight lang=python>
# Виходячи з обчислень, ми очікуємо, що локальний мінімум матиме місце в x=9/4

x_old = 0 # Це значення не важливе, оскільки abs(x_new - x_old) > precision
x_new = 6 # Алгоритм стартує з x=6
gamma = 0.01 # розмір кроку
precision = 0.00001

def f_derivative(x):
    return 4 * x**3 - 9 * x**2

while abs(x_new - x_old) > precision:
    x_old = x_new
    x_new = x_old - gamma * f_derivative(x_old)

print("Локальний мінімум має місце в", x_new)
</syntaxhighlight>

Наведений вище фрагмент коду має бути змінено по відношенню до розміру кроку відповідно до системи, яка є під руками, а збіжність може бути зроблено швидшою шляхом застосування адаптивного розміру кроку. В наведеному вище випадку розмір кроку не є адаптивним. Він залишається на рівні 0.01 в усіх напрямках, що може іноді призводити до невдачі методу за рахунок відхилення від мінімуму.

=== MATLAB ===

Наступний код [[MATLAB]] демонструє конкретне рішення для розв'язання системи нелінійних рівнянь, представленої в [[#Розв'язання нелінійної системи|попередньому розділі]]:

: <math>
\begin{cases}
3x_1-\cos(x_2x_3)-\tfrac{3}{2}=0 \\
4x_1^2-625x_2^2+2x_2-1=0  \\
\exp(-x_1x_2)+20x_3+\tfrac{10\pi-3}{3}=0
\end{cases}
</math>

<syntaxhighlight lang=matlab>
% Багатовимірна вектор-функція G(x)
G = @(x) [
    3*x(1) - cos(x(2)*x(3)) - 3/2           ;
    4*x(1)^2 - 625*x(2)^2 + 2*x(2) - 1      ;
    exp(-x(1)*x(2)) + 20*x(3) + (10*pi-3)/3];

% Якобіан G
JG = @(x) [
    3,                     sin(x(2)*x(3))*x(3),   sin(x(2)*x(3))*x(2) ;
    8*x(1),                -1250*x(2)+2,          0                   ;
    -x(2)*exp(-x(1)*x(2)), -x(1)*exp(-x(1)*x(2)), 20                 ];

% Цільова функція F(x), яку потрібно мінімізувати, щоби розв'язати G(x)=0
F = @(x) 0.5 * sum(G(x).^2);

% Градієнт F (часткові похідні)
dF = @(x) JG(x).' * G(x);

% Параметри
GAMMA = 0.001;    % розмір кроку (темп навчання)
MAX_ITER = 1000;  % максимальне число ітерацій
FUNC_TOL = 0.1;   % кінцеве допустиме відхилення F(x)

fvals = [];       % зберігання значень F(x) протягом ітерацій
progress = @(iter,x) fprintf('iter = %3d: x = %-32s, F(x) = %f\n', ...
    iter, mat2str(x,6), F(x));

% Ітерування
iter = 1;         % лічильник ітерацій
x = [0; 0; 0];    % початкове припущення
fvals(iter) = F(x);
progress(iter, x);
while iter < MAX_ITER && fvals(end) > FUNC_TOL
    iter = iter + 1;
    x = x - GAMMA * dF(x);  % градієнтний спуск
    fvals(iter) = F(x);     % обчислити цільову функцію
    progress(iter, x);      % показати перебіг
end

% Накреслити
plot(1:iter, fvals, 'LineWidth',2); grid on;
title('Objective Function'); xlabel('Iteration'); ylabel('F(x)');

% Обчислити кінцевий розв'язок системи рівнянь G(x)=0
disp('G(x) = '); disp(G(x))

% Виведення:
%
% iter =   1: x = [0;0;0]                         , F(x) = 58.456136
% iter =   2: x = [0.0075;0.002;-0.20944]         , F(x) = 23.306394
% iter =   3: x = [0.015005;0.0015482;-0.335103]  , F(x) = 10.617030
% ...
% iter = 187: x = [0.683335;0.0388258;-0.52231]   , F(x) = 0.101161
% iter = 188: x = [0.684666;0.0389831;-0.522302]  , F(x) = 0.099372
%
% (збіглося за 188 ітерацій після перевищення кінцевого допустимого відхилення F(x))
</syntaxhighlight>

== Розширення ==

Градієнтний спуск може бути розширено для підтримки [[Обмеження (математика)|обмежень]] шляхом включення [[Проєкція (лінійна алгебра)|проєкції]] на множину обмежень. Цей метод підходить лише тоді, коли ця проєкція є ефективно обчислюваною на комп'ютері. За зручних припущень цей метод збігається. Цей метод є окремим випадком {{нпні|Послідовно-зворотний алгоритм (опукле програмування)|послідовно-зворотного алгоритму||Forward–backward algorithm (convex programming)}} для монотонних включень (який включає [[опукле програмування]] та {{нп|Варіаційна нерівність|варіаційні нерівності||Variational inequality}}).<ref>P. L. Combettes and J.-C. Pesquet, [http://www.ann.jussieu.fr/~plc/prox.pdf «Proximal splitting methods in signal processing»] {{Webarchive|url=https://web.archive.org/web/20110707200947/http://www.ann.jussieu.fr/~plc/prox.pdf |date=7 липня 2011 }}, in: ''Fixed-Point Algorithms for Inverse Problems in Science and Engineering'', (H. H. Bauschke, [[Регіна Бурачик|R. S. Burachik]], P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Editors), pp. 185—212. Springer, New York, 2011. {{ref-en}}</ref>

=== Швидкий проксимальний градієнтний метод ===

Інше розширення градієнтного спуску виникло завдяки {{нп|Нестеров Юрій|Юрієві Нестерову||Yurii Nesterov}} 1983 року,<ref>Yu. Nesterov, «Introductory Lectures on Convex Optimization. A Basic Course» (Springer, 2004, ISBN 1-4020-7553-7) {{ref-en}}</ref> і було згодом узагальнене. Він пропонує просту видозміну цього алгоритму, яка уможливлює швидке збігання для опуклих задач. А саме, якщо функція <math>F</math> є опуклою, а <math>\nabla F</math> є [[Ліпшицеве відображення|ліпшицевою]], і немає припущення, що <math>F</math> є [[Сильно опукла функція|сильно опуклою]], то похибку цільового значення, породжувану методом градієнтного спуску на кожному кроці <math>k</math>, буде [[Нотація Ландау|обмежено]] <math>\mathcal{O}(1/k)</math>. Із застосуванням методики прискорення Нестерова похибка знижується до <math>\mathcal{O}(1/k^2)</math>.<ref>[http://www.ee.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf Fast Gradient Methods] {{Webarchive|url=https://web.archive.org/web/20121224125445/http://www.ee.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf |date=24 грудня 2012 }}, lecture notes by Prof. Lieven Vandenberghe for EE236C at UCLA {{ref-en}}</ref>

=== Метод імпульсу ===

Ще одним розширенням, яке знижує ризик застрягнути в локальному мінімумі, а також істотно прискорює збіжність у випадках, коли інакше процес би сильно зиґзаґував, є ''метод імпульсу'' ({{lang-en|momentum method}}), який використовує член імпульсу по аналогії з «масою ньютонових частинок, які рухаються в'язким середовищем у консервативному силовому полі».<ref>{{cite journal|last1=Qian|first1=Ning|title=On the momentum term in gradient descent learning algorithms|journal={{нп|Neural Networks (журнал)|Neural Networks||Neural Networks (journal)}}|date=January 1999|volume=12|issue=1|pages=145–151|url=http://brahms.cpmc.columbia.edu/publications/momentum.pdf|accessdate=17 жовтня 2014|archiveurl=https://web.archive.org/web/20140508200053/http://brahms.cpmc.columbia.edu/publications/momentum.pdf|archivedate=8 травня 2014|deadurl=yes}} {{ref-en}}</ref> Цей метод часто використовують як розширення алгоритмів [[Зворотне поширення|зворотного поширення]], що застосовуються для тренування [[Штучна нейронна мережа|штучних нейронних мереж]].<ref>{{cite web|title=Momentum and Learning Rate Adaptation|url=http://www.willamette.edu/~gorr/classes/cs449/momrate.html|publisher={{нп|Університет Вілламет|Willamette University||Willamette University}}|accessdate=17 жовтня 2014|archive-date=21 жовтня 2014|archive-url=https://web.archive.org/web/20141021060651/http://www.willamette.edu/~gorr/classes/cs449/momrate.html}} {{ref-en}}</ref><ref>{{cite web|author1=[[Джефрі Хінтон|Geoffrey Hinton]]|author2=Nitish Srivastava|author3=Kevin Swersky|title=6&nbsp;— 3&nbsp;— The momentum method|url=https://www.youtube.com/watch?v=ts7I5Iw4Y5M|website=[[YouTube]]|accessdate=18 жовтня 2014|archivedate=10 травня 2015|archive-url=https://web.archive.org/web/20150510041653/https://www.youtube.com/watch?v=ts7I5Iw4Y5M}} Частина з серії лекцій для онлайн-курсу [[Coursera]] [https://www.coursera.org/course/neuralnets Neural Networks for Machine Learning] {{Webarchive|url=https://web.archive.org/web/20160629121022/https://www.coursera.org/course/neuralnets |date=29 червня 2016 }}. {{ref-en}}</ref>

== Див. також ==

* [[Метод спряженого градієнта]]
* [[Метод проксимального градієнта]]
* [[Стохастичний градієнтний спуск]]
* {{нп|Rprop}}
* [[Дельта-правило]]
* [[Умови Вольфе]]
* {{нп|Передобумовлювання|||Preconditioner}}
* [[Метод БФГШ]]
* [[Метод Нелдера – Міда]]
* [[Алгоритм Франк — Вульфа]]

== Примітки ==
{{Примітки}}

== Джерела ==

* Mordecai Avriel (2003). ''Nonlinear Programming: Analysis and Methods.'' Dover Publishing. ISBN 0-486-43227-0. {{ref-en}}
* Jan A. Snyman (2005). ''Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms.'' Springer Publishing. ISBN 0-387-24348-8 {{ref-en}}
* Raad Z. Homod, K. S. M. Sahari, H. A.F. Almurib, F. H. Nagi, ''Gradient auto-tuned Takagi-Sugeno fuzzy forward control of a HVAC system using predicted mean vote index'' [http://www.sciencedirect.com/science/article/pii/S0378778812000904 Energy and Buildings, 49 (6) (2012) 254—267] {{Webarchive|url=https://web.archive.org/web/20181211152405/https://www.sciencedirect.com/science/article/pii/S0378778812000904 |date=11 грудня 2018 }} {{ref-en}}
* {{cite book|last1=Cauchy|first1=Augustin|authorlink1=Огюстен Коші|title=Méthode générale pour la résolution des systèmes d'équations simultanées|url=http://gallica.bnf.fr/ark:/12148/bpt6k2982c.image.f540.pagination.langEN|year=1847|pages=536–538|accessdate=31 липня 2016|archive-date=13 жовтня 2016|archive-url=https://web.archive.org/web/20161013220158/http://gallica.bnf.fr/ark:/12148/bpt6k2982c.image.f540.pagination.langEN}} {{ref-fr}}
* {{ЕК}}, [[Поляк Р. А.]], [[Примак М. Е.]], т. '''2''', ст. 64.

== Посилання ==

* [http://codingplayground.blogspot.it/2013/05/learning-linear-regression-with.html Застосування градієнтного спуску в C++, Boost, Ublas для лінійної регресії] {{Webarchive|url=https://web.archive.org/web/20130722153140/http://codingplayground.blogspot.it/2013/05/learning-linear-regression-with.html |date=22 липня 2013 }}

{{Диференційовні обчислення}}
{{Методи оптимізації}}
[[Категорія:Методи першого порядку]]
[[Категорія:Методи оптимізації]]
[[Категорія:Алгоритми оптимізації]]
[[Категорія:Градієнтні методи]]
[[Категорія:Статті з прикладами коду мовою Python]]
[[Категорія:Статті з прикладами коду мовою Matlab]]