Градієнтний спуск

Ця стаття про алгоритм оптимізації. Про метод наближення інтегралів у математичному аналізі див. Метод перевалу^[en]

Градіє́нтний спуск (англ. gradient descent) — це ітераційний алгоритм оптимізації першого порядку, в якому для знаходження локального мінімуму функції здійснюються кроки, пропорційні протилежному значенню градієнту (або наближеного градієнту) функції в поточній точці. Якщо натомість здійснюються кроки пропорційно самому значенню градієнту, то відбувається наближення до локального максимуму цієї функції; і ця процедура тоді відома як градіє́нтний підйо́м (англ. gradient ascent).

Градієнтний спуск відомий також як найшви́дший спуск (англ. steepest descent), або ме́тод найшви́дшого спу́ску (англ. method of steepest descent). Градієнтний спуск не слід плутати з методом перевалу^[en] для наближення інтегралів.

Опис

Градієнтний спуск ґрунтується на тому спостереженні, що якщо функція кількох змінних^[en] $F(\mathbf {x} )$ є визначеною^[en] та диференційовною в околі точки $\mathbf {a}$ , то $F(\mathbf {x} )$ зменшується найшвидше, якщо йти від $\mathbf {a}$ в напрямку, протилежному градієнтові $F$ в $\mathbf {a}$ , $-\nabla F(\mathbf {a} )$ . З цього випливає, що якщо

\mathbf {b} =\mathbf {a} -\gamma \nabla F(\mathbf {a} )

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

\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.

Ми маємо

F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,

і тому сподіваємося, що послідовність $(\mathbf {x} _{n})$ збігається до бажаного локального мінімуму. Зауважте, що значення розміру кроку (англ. step size) $\gamma$ дозволено змінювати на кожній ітерації. Для деяких припущень стосовно функції $F$ (наприклад, що $F$ є опуклою, а $\nabla F$ задовольняє умові Ліпшиця) і певних варіантах вибору $\gamma$ (наприклад, якщо його вибирають лінійним пошуком, який задовольняє умови Вольфе), збіжність до локального мінімуму може бути гарантовано. Якщо функція $F$ є опуклою, то всі локальні мінімуми є також і глобальними мінімумами, тому в такому випадку градієнтний спуск може збігатися до глобального розв'язку.

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

Приклади

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

f(x_{1},x_{2})=(1-x_{1})^{2}+100(x_{2}-x_{1}^{2})^{2}.\quad

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

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

Обмеження

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

Для недиференційовних функцій градієнтні методи є недостатньо визначеними. Для локально ліпшицевих задач, та особливо для задач опуклої оптимізації, цілком визначеними є в'язкові методи спуску. Також можуть застосовуватися не-спускові методи, такі як методи субградієнтної проєкції.^[1] Ці методи зазвичай є повільнішими за градієнтний спуск. Іншою альтернативою для недиференційовних функцій є «згладжування» цих функцій, або обмеження функції гладкою функцією. За цього підходу розв'язують згладжену задачу в надії, що відповідь для неї є близькою до відповіді на незгладжену задачу (іноді це може бути зроблено строгим).

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

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

A\mathbf {x} -\mathbf {b} =0

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

F(\mathbf {x} )=\|A\mathbf {x} -\mathbf {b} \|^{2}.

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

\nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).

В такому випадку мінімізація лінійним пошуком, яка знаходить на кожній ітерації локально оптимальний розмір кроку $\gamma$ , може виконуватися аналітично, і явні формули локально оптимального $\gamma$ є відомими.^[2]

Для розв'язання лінійних рівнянь градієнтний спуск застосовується рідко, а однією з найпопулярніших альтернатив є метод спряжених градієнтів. Швидкість збігання градієнтного спуску залежить від максимального та мінімального власних значень $A$ , тоді як швидкість збігання спряжених градієнтів має складнішу залежність від цих власних значень, і може отримувати користь від передобумовлювання^[en]. Градієнтний спуск також отримує користь від передобумовлювання, але це не роблять так поширено.

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

Градієнтний спуск може також застосовуватися і до розв'язання систем нелінійних рівнянь. Нижче наведено приклад, як застосовувати градієнтний спуск для розв'язання для трьох невідомих змінних, x₁, x₂ та x₃. Цей приклад показує одну ітерацію градієнтного спуску.

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

{\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}

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

G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}}

де

\mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}

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

F(\mathbf {x} )={\tfrac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )={\tfrac {1}{2}}\left(\left(3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\left(\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {1}{3}}(10\pi -3)\right)^{2}\right)

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

\mathbf {x} ^{(0)}={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}

Ми знаємо, що

\mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}-\gamma _{0}\nabla F(\mathbf {x} ^{(0)})

де

\nabla F(\mathbf {x} ^{(0)})=J_{G}(\mathbf {x} ^{(0)})^{\mathrm {T} }G(\mathbf {x} ^{(0)})

Матриця Якобі $J_{G}(\mathbf {x} ^{(0)})$

J_{G}={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}

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

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

Отже,

\mathbf {x} ^{(1)}=0-\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}}

та

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

Тепер мусить бути знайдено придатний $\gamma _{0}$ , такий що $F(\mathbf {x} ^{(1)})\leq F(\mathbf {x} ^{(0)})$ . Це можна зробити за допомогою будь-якого з безлічі алгоритмів лінійного пошуку. Можна також просто припустити $\gamma _{0}=0.001$ , що дає

\mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}

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

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

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

Коментарі

Градієнтний спуск працює в просторах з будь-яким числом вимірів, навіть у нескінченновимірних. В останньому випадку простір пошуку зазвичай є простором функцій, і для визначення напрямку спуску здійснюється обчислення похідної Гато функціоналу, який мінімізують.^[3]

Якщо кривина заданої функції дуже різниться в різних напрямках, то градієнтному спускові може знадобитися багато ітерацій для обчислення локального мінімуму з потрібною точністю. Для таких функцій повільне збігання лікується передобумовлюванням^[en], яке змінює геометрію простору так, щоби надати множинам рівнів функції форми концентричних кіл. Проте побудова та застосування передобумовлювання можуть бути обчислювально витратними.

Градієнтний спуск можна поєднувати з лінійним пошуком, який на кожній ітерації шукає локально оптимальний розмір кроку $\gamma$ . Виконання лінійного пошуку може бути витратним за часом. З іншого боку, застосування незмінного малого $\gamma$ може давати погану збіжність.

Кращими альтернативами можуть бути методи на основі методу Ньютона та обернення гессіану із застосуванням методик спряжених градієнтів.^[4]^[5] Загалом такі методи збігаються за меншу кількість ітерацій, але вартість кожної ітерації є вищою. Прикладом є Метод БФГШ, який складається з обчислення на кожному кроці матриці, на яку множиться вектор градієнту, щоби йти в «найкращому» напрямку, поєднаного зі складнішим алгоритмом лінійного пошуку для знаходження «найкращого» значення $\gamma$ . Для надзвичайно великих задач, у яких домінують питання комп'ютерної пам'яті, замість БФГШ або найшвидшого спуску повинні застосовуватися методи з обмеженою пам'яттю, такі як О-БФГШ^[en].

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

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

Python

Алгоритм градієнтного спуску застосовується для знаходження локального мінімуму функції f(x)=x⁴−3x³+2 з похідною f'(x)=4x³−9x². Ось реалізація мовою програмування 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)

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

MATLAB

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

{\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}

% Багатовимірна вектор-функція 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))

Розширення

Градієнтний спуск може бути розширено для підтримки обмежень шляхом включення проєкції на множину обмежень. Цей метод підходить лише тоді, коли ця проєкція є ефективно обчислюваною на комп'ютері. За зручних припущень цей метод збігається. Цей метод є окремим випадком послідовно-зворотного алгоритму для монотонних включень (який включає опукле програмування та варіаційні нерівності^[en]).^[6]

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

Інше розширення градієнтного спуску виникло завдяки Юрієві Нестерову^[en] 1983 року,^[7] і було згодом узагальнене. Він пропонує просту видозміну цього алгоритму, яка уможливлює швидке збігання для опуклих задач. А саме, якщо функція $F$ є опуклою, а $\nabla F$ є ліпшицевою, і немає припущення, що $F$ є сильно опуклою, то похибку цільового значення, породжувану методом градієнтного спуску на кожному кроці $k$ , буде обмежено ${\mathcal {O}}(1/k)$ . Із застосуванням методики прискорення Нестерова похибка знижується до ${\mathcal {O}}(1/k^{2})$ .^[8]

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

Ще одним розширенням, яке знижує ризик застрягнути в локальному мінімумі, а також істотно прискорює збіжність у випадках, коли інакше процес би сильно зиґзаґував, є метод імпульсу (англ. momentum method), який використовує член імпульсу по аналогії з «масою ньютонових частинок, які рухаються в'язким середовищем у консервативному силовому полі».^[9] Цей метод часто використовують як розширення алгоритмів зворотного поширення, що застосовуються для тренування штучних нейронних мереж.^[10]^[11]

Див. також

Примітки

↑ Kiwiel, Krzysztof C. (2001). Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical Programming (Series A). Т. 90, № 1. Berlin, Heidelberg: Springer. с. 1—25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. (англ.)
↑ Yuan, Ya-xiang (1999). Step-sizes for the gradient method (PDF). AMS/IP Studies in Advanced Mathematics. Providence, RI: American Mathematical Society. 42 (2): 785.{{cite journal}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання) (англ.)
↑ G. P. Akilov, L. V. Kantorovich, Functional Analysis, Pergamon Pr; 2 Sub edition, ISBN 0-08-023036-9, 1982 (англ.)
↑ W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd Ed., Cambridge University Press, New York, 1992 (англ.)
↑ 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. (англ.)
↑ P. L. Combettes and J.-C. Pesquet, «Proximal splitting methods in signal processing» [Архівовано 7 липня 2011 у Wayback Machine.], 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. (англ.)
↑ Yu. Nesterov, «Introductory Lectures on Convex Optimization. A Basic Course» (Springer, 2004, ISBN 1-4020-7553-7) (англ.)
↑ Fast Gradient Methods [Архівовано 24 грудня 2012 у Wayback Machine.], lecture notes by Prof. Lieven Vandenberghe for EE236C at UCLA (англ.)
↑ Qian, Ning (January 1999). On the momentum term in gradient descent learning algorithms (PDF). Neural Networks^[en]. 12 (1): 145—151. Архів оригіналу (PDF) за 8 травня 2014. Процитовано 17 жовтня 2014. (англ.)
↑ Momentum and Learning Rate Adaptation. Willamette University^[en]. Архів оригіналу за 21 жовтня 2014. Процитовано 17 жовтня 2014. (англ.)
↑ Geoffrey Hinton; Nitish Srivastava; Kevin Swersky. 6 — 3 — The momentum method. YouTube. Архів оригіналу за 10 травня 2015. Процитовано 18 жовтня 2014. Частина з серії лекцій для онлайн-курсу Coursera Neural Networks for Machine Learning [Архівовано 29 червня 2016 у Wayback Machine.]. (англ.)

Джерела

Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0. (англ.)
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 (англ.)
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 Energy and Buildings, 49 (6) (2012) 254—267 [Архівовано 11 грудня 2018 у Wayback Machine.] (англ.)
Cauchy, Augustin (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. с. 536—538. Архів оригіналу за 13 жовтня 2016. Процитовано 31 липня 2016. (фр.)
Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973., Поляк Р. А., Примак М. Е., т. 2, ст. 64.

Посилання

Застосування градієнтного спуску в C++, Boost, Ublas для лінійної регресії [Архівовано 22 липня 2013 у Wayback Machine.]

[1] Kiwiel, Krzysztof C. (2001). Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical Programming (Series A). Т. 90, № 1. Berlin, Heidelberg: Springer. с. 1—25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. (англ.)

[2] Yuan, Ya-xiang (1999). Step-sizes for the gradient method (PDF). AMS/IP Studies in Advanced Mathematics. Providence, RI: American Mathematical Society. 42 (2): 785.{{cite journal}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання) (англ.)

[3] G. P. Akilov, L. V. Kantorovich, Functional Analysis, Pergamon Pr; 2 Sub edition, ISBN 0-08-023036-9, 1982 (англ.)

[4] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd Ed., Cambridge University Press, New York, 1992 (англ.)

[5] 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. (англ.)

[6] P. L. Combettes and J.-C. Pesquet, «Proximal splitting methods in signal processing» [Архівовано 7 липня 2011 у Wayback Machine.], 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. (англ.)

[7] Yu. Nesterov, «Introductory Lectures on Convex Optimization. A Basic Course» (Springer, 2004, ISBN 1-4020-7553-7) (англ.)

[8] Fast Gradient Methods [Архівовано 24 грудня 2012 у Wayback Machine.], lecture notes by Prof. Lieven Vandenberghe for EE236C at UCLA (англ.)

[9] Qian, Ning (January 1999). On the momentum term in gradient descent learning algorithms (PDF). Neural Networks^[en]. 12 (1): 145—151. Архів оригіналу (PDF) за 8 травня 2014. Процитовано 17 жовтня 2014. (англ.)

[10] Momentum and Learning Rate Adaptation. Willamette University^[en]. Архів оригіналу за 21 жовтня 2014. Процитовано 17 жовтня 2014. (англ.)

[11] Geoffrey Hinton; Nitish Srivastava; Kevin Swersky. 6 — 3 — The momentum method. YouTube. Архів оригіналу за 10 травня 2015. Процитовано 18 жовтня 2014. Частина з серії лекцій для онлайн-курсу Coursera Neural Networks for Machine Learning [Архівовано 29 червня 2016 у Wayback Machine.]. (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

п о р Методи оптимізації
Одномірні	Метод золотого перетину Дихотомія Перебір по сітці Метод рівномірного блокового пошуку Метод Фібоначчі Тернарний пошук Метод Піявського Метод Стронгіна
Нульового порядку	Метод Гауса Метод Нелдера — Міда Метод Гука — Дживса Метод Розенброка Метод Пауелла
Першого порядку	Градієнтний спуск Метод Зойтендейка Покоординатний спуск Метод проксимального градієнта Метод спряженого градієнта Квазі-ньютонів метод Алгоритм Левенберга — Марквардта Ріманова оптимізація
Другого порядку	Метод Ньютона Метод Ньютона — Рафсона Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS)
Стохастичні	Метод Монте-Карло Імітація відпалу Квантовий відпал Еволюційний алгоритм Диференціальна еволюція Мурашиний алгоритм Метод рою часток Бджолиний алгоритм Метод випадкових блукань
Методи лінійного програмування	Симплекс-метод Алгоритм Гоморі Метод еліпсоїдів Метод потенціалів
Методи нелінійного програмування	Послідовне квадратичне програмування

Градієнтний спуск

Зміст