Метод Градієнтного Спуску: Як Крок за Кроком Зменшувати Значення Функції

Метод градієнтного спуску — це один із базових чисельних підходів для знаходження мінімуму функції кількох змінних. Його часто використовують тоді, коли потрібно поступово наближатися до точки, у якій значення функції стає меншим. У цій статті розглянемо основну ідею методу, запишемо ітераційну формулу, пояснимо роль довжини кроку та покажемо, як можна обчислювати градієнт, якщо частинні похідні не задані явно.

Метод Градієнтного Спуску: Основна Ідея Мінімізації

Розглянемо функцію кількох змінних

\[
f(\bar{x})=f(x_1,x_2,\dots,x_n),
\]

де \( \bar{x} \) — це вектор змінних.

Мінімізувати таку функцію означає знайти таку точку \( \bar{x} \), у якій значення \( f(\bar{x}) \) буде найменшим або хоча б локально найменшим у певній області. Саме слово «локально» тут важливе. Адже метод градієнтного спуску в загальному випадку не завжди знаходить глобальний мінімум. Він зазвичай призводить до локального мінімуму, який залежить від початкової точки та властивостей функції.

Щоб зрозуміти, куди рухатися, використовують градієнт функції. Для функції кількох змінних він має вигляд

\[
\nabla f(\bar{x})=
\left(
\frac{\partial f}{\partial x_1},
\frac{\partial f}{\partial x_2},
\dots,
\frac{\partial f}{\partial x_n}
\right).
\]

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

Градієнт указує напрям найшвидшого зростання функції. А нам потрібно зменшувати значення функції, чи не так? Тому рухатися треба у протилежному напрямку: \( -\nabla f(\bar{x}) \). Цей напрям називають антиградієнтним. Саме він показує, у який бік потрібно зробити крок, щоб значення функції зменшувалося найшвидше поблизу поточної точки.

Отже, на першому етапі важливо запам’ятати просту ідею: метод починає роботу з певної точки, знаходить у ній градієнт і рухається в напрямку, протилежному до нього.

Початкове Наближення: Як Будується Ітераційний Процес

Тепер перейдемо від ідеї до алгоритму. Спочатку потрібно вибрати початкове наближення:

\[
\bar{x}^{(0)}=
\left(
x_1^{(0)},
x_2^{(0)},
\dots,
x_n^{(0)}
\right).
\]

Це стартова точка, з якої починаються обчислення. Вибір цієї точки має значення. Якщо функція складна й має кілька локальних мінімумів, то різні початкові точки можуть привести до різних результатів.

Після вибору (\bar{x}^{(0)}) обчислюють градієнт у цій точці: \( \nabla f(\bar{x}^{(0)}) \). Далі виконують перший крок у напрямку антиградієнта:

\[
\bar{x}^{(1)}
=
\bar{x}^{(0)}-\alpha\cdot \nabla f(\bar{x}^{(0)}),
\qquad \alpha>0.
\]

Тут \( \alpha \) — поточна довжина кроку. Вона показує, наскільки далеко ми переходимо від початкової точки в напрямку спадання функції.

Після цього отримуємо нову точку

\[
\bar{x}^{(1)}=
\left(
x_1^{(1)},
x_2^{(1)},
\dots,
x_n^{(1)}
\right).
\]

На наступній ітерації вже працюємо не з початковою точкою, а з новим наближенням. Тому знову обчислюємо градієнт, але вже в точці \( \bar{x}^{(1)} \), і переходимо до точки \( \bar{x}^{(2)} \):

\[
\bar{x}^{(2)}
=
\bar{x}^{(1)}-\alpha\cdot \nabla f(\bar{x}^{(1)}),
\qquad \alpha>0.
\]

Таким чином, крок за кроком будується послідовність наближень. У загальному вигляді її можна записати так:

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}-\alpha\cdot \nabla f(\bar{x}^{(k)}),
\qquad k=0,1,2,\dots
\]

де \( \alpha \) — поточна довжина кроку, яка використовується під час переходу від \( \bar{x}^{(k)} \) до \( \bar{x}^{(k+1)} \).

Ця формула є основою методу. Вона показує, як із поточної точки \( \bar{x}^{(k)} \) перейти до наступної точки \( \bar{x}^{(k+1)} \). При цьому кожен перехід виконується з урахуванням напряму спадання функції.

Довжина Кроку: Як Уникнути Невдалого Переходу

Після запису ітераційної формули виникає важливе практичне питання: як вибрати довжину кроку \( \alpha \)? Адже саме вона визначає, наскільки сильно ми змістимося в антиградієнтному напрямку.

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

\[
f(\bar{x}^{(k+1)})<f(\bar{x}^{(k)}).
\]

Якщо ця умова виконується, то нову точку можна прийняти. У такому разі поточне значення \( \alpha \) можна залишити для наступної ітерації.

Якщо ж значення функції не зменшилося або навіть збільшилося, тоді довжину кроку потрібно зменшити. Один із простих способів — поділити крок навпіл:

\[
\alpha \leftarrow \frac{\alpha}{2}.
\]

Після цього нову точку обчислюють ще раз, але вже з меншим кроком:

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}-\alpha\cdot \nabla f(\bar{x}^{(k)}).
\]

Така перевірка допомагає зробити метод надійнішим. Ми не просто механічно переходимо до нової точки, а контролюємо, чи справді рухаємося в бік зменшення функції.

Однак рано чи пізно зміни стають дуже малими. Тому потрібно мати умову зупинки. Наприклад, можна завершити обчислення, якщо норма градієнта стала меншою за задану точність:

\[
\|\nabla f(\bar{x}^{(k)})\|<\varepsilon.
\]

Також можна використовувати умову близькості двох сусідніх наближень:

\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<\varepsilon.
\]

Або умову малої зміни значення функції:

\[
|f(\bar{x}^{(k+1)})-f(\bar{x}^{(k)})|<\varepsilon.
\]

Тут \( \varepsilon \) — задана точність обчислень.

З теоретичної точки зору, якщо локальний мінімум досягається всередині області, то в цій точці виконується умова

\[
\nabla f(\bar{x})=0.
\]

Проте важливо пам’ятати: ця умова є необхідною, але не завжди достатньою. Точка з нульовим градієнтом може бути не лише точкою мінімуму, а й точкою максимуму або сідловою точкою. Тому результат потрібно оцінювати з урахуванням властивостей функції.

Обчислення Градієнта: Що Робити Без Явних Похідних

У простих навчальних прикладах частинні похідні часто знаходять аналітично. Тобто ми беремо задану функцію, диференціюємо її за кожною змінною й отримуємо готову формулу для градієнта.

Але що робити, якщо частинні похідні знайти складно? Або якщо функція задана так, що її значення можна обчислити, але явний вигляд похідних незручний? У такому разі елементи градієнта можна наближено обчислювати чисельно.

Для змінної \( x_i \) можна використати формулу односторонньої різниці:

\[
\frac{\partial f}{\partial x_i}\approx
\frac{
f(x_1,\dots,x_i+\Delta x_i,\dots,x_n)-
f(x_1,\dots,x_i,\dots,x_n)
}{
\Delta x_i
},
\qquad i=1,2,\dots,n.
\]

Тут \( \Delta x_i \) — малий приріст змінної \( x_i \). Ідея проста: ми трохи змінюємо одну змінну, залишаємо інші без змін і дивимося, як змінилося значення функції.

Для більшої точності іноді використовують центральну різницю:

\[
\frac{\partial f}{\partial x_i}\approx
\frac{
f(x_1,\dots,x_i+\Delta x_i,\dots,x_n)-
f(x_1,\dots,x_i-\Delta x_i,\dots,x_n)
}{
2\Delta x_i
}.
\]

Ця формула зазвичай дає точніше наближення, але потребує більше обчислень значень функції. Тому на практиці вибір способу залежить від того, що важливіше: швидкість чи точність.

Отже, метод градієнтного спуску можна застосовувати не лише тоді, коли градієнт заданий явно. Його можна використовувати й у чисельному вигляді, якщо ми вміємо обчислювати значення самої функції.

Практична Частина: Метод Градієнтного Спуску Для Функції Двох Змінних

Тепер розглянемо, як метод градієнтного спуску працює на конкретній функції двох змінних. У такому прикладі вже потрібно не просто записати формулу, а послідовно обчислювати градієнт, нові наближення та перевіряти умову зупинки. Саме так добре видно, як теоретична схема перетворюється на реальний обчислювальний процес.

Приклад 1. Знайти мінімальне значення функції \( f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2 \) з точністю \( \varepsilon=0.05 \) методом градієнтного спуску

Розглянемо функцію:

\[
f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2.
\]

Це функція двох змінних \( x_1 \) та \( x_2 \). Вона має простий аналітичний вигляд, тому з її допомогою зручно показати, як крок за кроком застосовується метод градієнтного спуску.

Візьмемо початкове наближення

\[
\bar{x}^{(0)}=(3,2).
\]

Також виберемо поточну довжину кроку \( \alpha=0.25 \). Умову зупинки перевірятимемо за правилом

\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<0.05.
\]

Для методу градієнтного спуску використовуємо формулу

\[
\bar{x}^{(k+1)}
=
\bar{x}^{(k)}
-\alpha\cdot \nabla f(\bar{x}^{(k)}).
\]

Спочатку знайдемо градієнт заданої функції. Для цього обчислимо частинні похідні:

\[
\frac{\partial f}{\partial x_1}=2\cdot (x_1-1),
\qquad
\frac{\partial f}{\partial x_2}=2\cdot (x_2+2).
\]

Отже,

\[
\nabla f(x_1,x_2)=
\left(
2\cdot (x_1-1),
2\cdot (x_2+2)
\right).
\]

Починаємо першу ітерацію. У початковій точці \( \bar{x}^{(0)}=(3,2) \) градієнт дорівнює

\[
\nabla f(3,2)=
\left(
2\cdot (3-1),
2\cdot (2+2)
\right)
=
(4,8).
\]

Тоді нове наближення обчислюємо так:

\[
\bar{x}^{(1)}
=
(3,2)-0.25\cdot(4,8).
\]

Звідси

\[
\bar{x}^{(1)}
=
(3,2)-(1,2)=(2,0).
\]

Перевіримо, чи зменшилося значення функції. У початковій точці маємо

\[
f(3,2)=(3-1)^2+(2+2)^2=20.
\]

У новій точці отримуємо

\[
f(2,0)=(2-1)^2+(0+2)^2=5.
\]

Оскільки

\[
5<20,
\]

перехід виконано успішно. Отже, поточне значення \( \alpha=0.25 \) можна залишити для наступної ітерації.

Тепер перевіримо умову точності:

\[
\|\bar{x}^{(1)}-\bar{x}^{(0)}\|
=
\sqrt{(2-3)^2+(0-2)^2}.
\]

Тому

\[
\|\bar{x}^{(1)}-\bar{x}^{(0)}\|
=\sqrt{1+4}
=\sqrt{5}
\approx 2.236.
\]

Оскільки

\[
2.236>0.05,
\]

обчислення продовжуємо.

Переходимо до другої ітерації. Беремо точку

\[
\bar{x}^{(1)}=(2,0).
\]

Обчислюємо градієнт у цій точці:

\[
\nabla f(2,0)=
\left(
2\cdot (2-1),
2\cdot (0+2)
\right)
=
(2,4).
\]

Тоді

\[
\bar{x}^{(2)}
=
(2,0)-0.25\cdot(2,4).
\]

Отже,

\[
\bar{x}^{(2)}
=
(2,0)-(0.5,1)=(1.5,-1).
\]

Значення функції в цій точці дорівнює

\[
f(1.5,-1)=(1.5-1)^2+(-1+2)^2.
\]

Маємо

\[
f(1.5,-1)=0.5^2+1^2=1.25.
\]

Оскільки

\[
1.250<5,
\]

другий крок також є успішним. У цьому прикладі після кожного виконаного переходу значення функції зменшується, тому зменшувати крок \( \alpha \) не потрібно.

Перевіримо точність:

\[
\|\bar{x}^{(2)}-\bar{x}^{(1)}\|
=
\sqrt{(1.5-2)^2+(-1-0)^2}
\approx 1.118.
\]

Оскільки

\[
1.118>0.05,
\]

переходимо до наступної ітерації.

Продовження ітераційного процесу

Для третьої ітерації маємо

\[
\bar{x}^{(2)}=(1.5,-1).
\]

Обчислюємо градієнт:

\[
\nabla f(1.5,-1)=
\left(
2\cdot (1.5-1),
2\cdot (-1+2)
\right)
=
(1,2).
\]

Тоді

\[
\bar{x}^{(3)}
=
(1.5,-1)-0.25\cdot(1,2).
\]

Звідси

\[
\bar{x}^{(3)}
=
(1.5,-1)-(0.25,0.5)=(1.25,-1.5).
\]

Обчислимо значення функції:

\[
f(1.25,-1.5)=(1.25-1)^2+(-1.5+2)^2.
\]

Тому

\[
f(1.25,-1.5)=0.25^2+0.5^2=0.313.
\]

Маємо

\[
0.313<1.25.
\]

Отже, значення функції знову зменшилося.

Тепер перевіримо умову точності:

\[
\|\bar{x}^{(3)}-\bar{x}^{(2)}\|
=
\sqrt{(1.25-1.5)^2+(-1.5+1)^2}
\approx 0.559.
\]

Оскільки

\[
0.559>0.05,
\]

обчислення продовжуємо.

Для четвертої ітерації беремо

\[
\bar{x}^{(3)}=(1.25,-1.5).
\]

Знаходимо градієнт:

\[
\nabla f(1.25,-1.5)=
\left(
2\cdot (1.25-1),
2\cdot (-1.5+2)
\right)
=
(0.5,1).
\]

Тоді

\[
\bar{x}^{(4)}
=
(1.25,-1.5)-0.25\cdot(0.5,1).
\]

Отримуємо

\[
\bar{x}^{(4)}
=
(1.25,-1.5)-(0.125,0.25)=(1.125,-1.75).
\]

Значення функції дорівнює

\[
f(1.125,-1.75)=(1.125-1)^2+(-1.75+2)^2.
\]

Після обчислення маємо

\[
f(1.125,-1.75)=0.125^2+0.25^2=0.078.
\]

Оскільки

\[
0.078<0.313,
\]

перехід приймаємо.

Перевіряємо точність:

\[
\|\bar{x}^{(4)}-\bar{x}^{(3)}\|
=
\sqrt{(1.125-1.25)^2+(-1.75+1.5)^2}
\approx 0.280.
\]

Оскільки

\[
0.280>0.05,
\]

потрібно виконати ще одну ітерацію.

Для п’ятої ітерації маємо

\[
\bar{x}^{(4)}=(1.125,-1.75).
\]

Обчислюємо градієнт:

\[
\nabla f(1.125,-1.75)=
\left(
2\cdot (1.125-1),
2\cdot (-1.75+2)
\right)
=
(0.25,0.5).
\]

Тоді

\[
\bar{x}^{(5)}
=
(1.125,-1.75)-0.25\cdot(0.25,0.5).
\]

Звідси

\[
\bar{x}^{(5)}
=
(1.125,-1.75)-(0.063,0.125)=(1.063,-1.875).
\]

Значення функції в цій точці:

\[
f(1.063,-1.875)=(1.063-1)^2+(-1.875+2)^2.
\]

Отже,

\[
f(1.063,-1.875)
\approx 0.063^2+0.125^2
\approx 0.02.
\]

Маємо

\[
0.02<0.078,
\]

тому точку \( \bar{x}^{(5)} \) приймаємо.

Перевіряємо умову зупинки:

\[
\|\bar{x}^{(5)}-\bar{x}^{(4)}\|
=
\sqrt{(1.063-1.125)^2+(-1.875+1.75)^2}
\approx 0.14.
\]

Оскільки

\[
0.14>0.05,
\]

ітераційний процес поки що не завершуємо.

Далі виконаємо ще дві ітерації в тій самій послідовності: обчислюємо градієнт, робимо крок у напрямку антиградієнта, перевіряємо зменшення функції та умову точності.

Для шостої ітерації беремо

\[
\bar{x}^{(5)}=(1.063,-1.875).
\]

Градієнт у цій точці дорівнює

\[
\nabla f(1.063,-1.875)
\approx
\left(
2\cdot (1.063-1),
2\cdot (-1.875+2)
\right)
=
(0.125,0.25).
\]

Тоді

\[
\bar{x}^{(6)}
=
(1.063,-1.875)-0.25\cdot(0.125,0.25).
\]

Отримуємо

\[
\bar{x}^{(6)}
=
(1.063,-1.875)-(0.031,0.063)
=
(1.031,-1.938).
\]

Значення функції:

\[
f(1.031,-1.938)
=
(1.031-1)^2+(-1.938+2)^2
\approx 0.005.
\]

Знову бачимо зменшення значення функції:

\[
0.005<0.02.
\]

Тепер перевіримо точність:

\[
\|\bar{x}^{(6)}-\bar{x}^{(5)}\|
=
\sqrt{(1.031-1.063)^2+(-1.938+1.875)^2}
\approx 0.07.
\]

Оскільки

\[
0.07>0.05,
\]

виконуємо ще одну ітерацію.

Для сьомої ітерації маємо

\[
\bar{x}^{(6)}=(1.031,-1.938).
\]

Обчислюємо градієнт:

\[
\nabla f(1.031,-1.938)
\approx
\left(
2\cdot (1.031-1),
2\cdot (-1.938+2)
\right)
=
(0.063,0.125).
\]

Тоді

\[
\bar{x}^{(7)}
=
(1.031,-1.938)-0.25\cdot(0.063,0.125).
\]

Звідси

\[
\bar{x}^{(7)}
=
(1.031,-1.938)-(0.016,0.031)
=
(1.016,-1.969).
\]

Обчислимо значення функції:

\[
f(1.016,-1.969)
=
(1.016-1)^2+(-1.969+2)^2
\approx 0.001.
\]

Оскільки

\[
0.001<0.005,
\]

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

Тепер знову перевіряємо умову точності:

\[
\|\bar{x}^{(7)}-\bar{x}^{(6)}\|
=
\sqrt{(1.016-1.031)^2+(-1.969+1.938)^2}
\approx 0.035.
\]

Оскільки

\[
0.035<0.05,
\]

ітераційний процес можна завершити.

Останнім знайденим наближенням є

\[
\bar{x}^{(7)}=(1.016,-1.969).
\]

Тому наближено точку мінімуму можна записати так:

\[
\bar{x}^{*}\approx(1.016,-1.969).
\]

Тепер знайдемо наближене мінімальне значення функції:

\[
f_{\min}\approx f(1.016,-1.969).
\]

Підставляємо знайдене наближення:

\[
f(1.016,-1.969)
=
(1.016-1)^2+(-1.969+2)^2.
\]

Отже,

\[
f(1.016,-1.969)
=
0.016^2+0.031^2
\approx 0.001.
\]

Таким чином, методом градієнтного спуску отримуємо

\[
\bar{x}^{*}\approx(1.016,-1.969),
\qquad
f_{\min}\approx 0.001.
\]

Для зручності зведемо основні результати ітерацій в одну таблицю. Вона добре показує, як точка поступово наближається до мінімуму, а значення функції зменшується.

\( k \)	\( \bar{x}^{(k)} \)	\( f(\bar{x}^{(k)}) \)	\( \|\bar{x}^{(k)}-\bar{x}^{(k-1)}\| \)
\( 0 \)	\( (3,2) \)	\( 20 \)	—
\( 1 \)	\( (2,0) \)	\( 5 \)	\( 2.236 \)
\( 2 \)	\( (1.5,-1) \)	\( 1.25 \)	\( 1.118 \)
\( 3 \)	\( (1.25,-1.5) \)	\( 0.313 \)	\( 0.559 \)
\( 4 \)	\( (1.125,-1.75) \)	\( 0.078 \)	\( 0.28 \)
\( 5 \)	\( (1.063,-1.875) \)	\( 0.02 \)	\( 0.14 \)
\( 6 \)	\( (1.031,-1.938) \)	\( 0.005 \)	\( 0.07 \)
\( 7 \)	\( (1.016,-1.969) \)	\( 0.001 \)	\( 0.035 \)

Порівняння з точною відповіддю

Перевіримо, як знайдений результат узгоджується з точною відповіддю. Для цього повернемося до самої функції:

\[
f(x_1,x_2)=(x_1-1)^2+(x_2+2)^2.
\]

Квадрат будь-якого числа не може бути від’ємним. Тому значення функції буде найменшим тоді, коли обидва вирази в дужках дорівнюватимуть нулю:

\[
x_1-1=0,
\qquad
x_2+2=0.
\]

Звідси отримуємо

\[
x_1=1,
\qquad
x_2=-2.
\]

Отже, точна точка мінімуму має вигляд

\[
\bar{x}^{*}=(1,-2).
\]

Відповідне мінімальне значення функції дорівнює

\[
f_{\min}=f(1,-2).
\]

Підставляємо точні значення:

\[
f(1,-2)=(1-1)^2+(-2+2)^2=0.
\]

Отже,

\[
\bar{x}^{*}=(1,-2),
\qquad
f_{\min}=0.
\]

Отримане методом градієнтного спуску наближення

\[
\bar{x}^{*}\approx(1.016,-1.969)
\]

є близьким до точної точки \( (1,-2) \). Тому результат обчислень добре узгоджується з точною відповіддю. Метод почав роботу з точки \( (3,2) \), послідовно зменшував значення функції та завершив обчислення тоді, коли відстань між двома сусідніми наближеннями стала меншою за задану точність.

Що Розглянути Далі: Корисні Теми Для Продовження

Метод градієнтного спуску добре показує базову ідею руху до мінімуму за допомогою градієнта. Але в чисельній оптимізації є й інші підходи. Саме вони допомагають краще порівняти різні способи мінімізації функцій кількох змінних.

1. Метод покоординатного спуску: Мінімізація крок за кроком — У цій статті йтиметься про пошук мінімуму через послідовну зміну окремих координат функції кількох змінних.
2. Метод Ньютона: Мінімізація функції багатьох змінних — Матеріал покаже, як у мінімізації використовують не лише градієнт, а й інформацію про кривину функції.
3. Метод Ньютона з параметром: Керований рух до мінімуму — У статті буде розглянуто, як параметр кроку допомагає зробити метод Ньютона більш керованим під час мінімізації.

Метод Градієнтного Спуску в Коді: Від Схеми До Власної Програми

Після теорії та практичного прикладу варто зробити ще один корисний крок — спробувати реалізувати метод самостійно. Готова блок-схема з цього розділу допоможе перетворити математичну ідею на зрозумілий програмний алгоритм для пошуку мінімального значення функції кількох змінних методом градієнтного спуску. Ви можете взяти її за основу й написати невелику програму улюбленою мовою програмування. Так ви не лише перевірите результат обчислень, а й краще побачите, як вибір початкової точки, кроку та умови зупинки впливає на роботу методу.