Метод Покоординатного Спуску: Від Теорії До Практичного Прикладу

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

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

Метод Покоординатного Спуску: Де Його Застосовують і в Чому Полягає Суть

Нехай задано функцію багатьох змінних

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

де \( \bar{x} \) — вектор змінних. Потрібно знайти точку мінімуму цієї функції або наближення до точки локального мінімуму. Саме для таких задач і застосовують метод покоординатного спуску.

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

Починають із деякого початкового наближення
\[
\bar{x}^{(0)}=\bigl(x_1^{(0)},x_2^{(0)},\dots,x_n^{(0)}\bigr).
\]

Після цього за кожною координатою по черзі виконують пошук мінімуму. Спочатку змінюють \( x_1 \), потім \( x_2 \), далі \( x_3 \), і так продовжують до \( x_n \).

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

Водночас тут слід відразу зробити важливе уточнення. У загальному випадку цей метод приводить до наближення саме до локального мінімуму, а не обов’язково до глобального. Отже, отриманий результат може залежати від вибору початкового наближення.

Мінімізація по Координатах: Як Виглядає Один Повний Цикл

Після вибору початкового наближення можна перейти до опису самого обчислювального процесу. Нехай маємо точку

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

На першому кроці фіксуємо всі координати, крім \( x_1 \), і розглядаємо функцію однієї змінної

\[
\varphi_1(x_1)=f(x_1,x_2^{(0)},\dots,x_n^{(0)}).
\]

Далі знаходимо таке значення \( x_1 \), при якому ця функція набуває мінімуму. Нехай це значення дорівнює \( x_1^{(1)} \). Тоді після першого кроку отримуємо нове проміжне наближення \( \bigl(x_1^{(1)},x_2^{(0)},\dots,x_n^{(0)}\bigr) \).

Після цього переходимо до другої координати. Тепер фіксуємо вже оновлене значення \( x_1^{(1)} \), а також усі інші координати, крім \( x_2 \), і розглядаємо функцію

\[
\varphi_2(x_2)=f(x_1^{(1)},x_2,\dots,x_n^{(0)}).
\]

Знайшовши її мінімум, отримуємо нове проміжне наближення \( \bigl(x_1^{(1)},x_2^{(1)},\dots,x_n^{(0)}\bigr) \).

Аналогічно процес продовжують для всіх інших координат до \( x_n \). Після того як усі змінні пройдено по одному разу, отримуємо нову точку

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

Саме цей перехід від \( \bar{x}^{(0)} \) до \( \bar{x}^{(1)} \) і називають одним повним циклом методу.

Тут важливо не плутати два поняття.

• Крок методу — це мінімізація за однією координатою.
• Повний цикл — це послідовне виконання таких кроків для всіх координат.

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

\[
f\bigl(\bar{x}^{(1)}\bigr)\leq f\bigl(\bar{x}^{(0)}\bigr).
\]

Якщо далі виконати ще один цикл, то отримаємо точку \( \bar{x}^{(2)} \), і тоді матимемо

\[
f\bigl(\bar{x}^{(2)}\bigr)\leq f\bigl(\bar{x}^{(1)}\bigr)\leq f\bigl(\bar{x}^{(0)}\bigr).
\]

Отже, утворюється послідовність наближень

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

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

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

Метод Покоординатного Спуску: Коли Доцільно Зупиняти Обчислення

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

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

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

Саме тому логічно порівнювати наближення \( \bar{x}^{(k)} \) і \( \bar{x}^{(k+1)} \), отримані після двох сусідніх повних циклів.

Один із найуживаніших критеріїв зупинки пов’язаний зі зміною самої точки:

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

де \( \varepsilon>0 \) — задана точність. Тут норма показує, наскільки нове наближення відрізняється від попереднього в цілому за всіма координатами. Якщо ця різниця вже дуже мала, то процес можна завершити.

Ще один поширений критерій пов’язаний зі зміною значення функції:

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

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

Крім того, іноді задають обмеження на максимальну кількість повних циклів:

\[
k\geq k_{\max}.
\]

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

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

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

Практична Частина: Як Метод Покоординатного Спуску Працює на Прикладі

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

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

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

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

Умову зупинки перевірятимемо після кожного повного циклу за правилом

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

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

Починаємо перший повний цикл. Спочатку фіксуємо \( x_2=0 \) і мінімізуємо функцію за змінною \( x_1 \). Тоді маємо

\[
\varphi_1(x_1)=f(x_1,0)=x_1^2-6\cdot x_1.
\]

Обчислимо похідну:

\[
\varphi_1′(x_1)=2\cdot x_1-6.
\]

Далі прирівняємо її до нуля:

\[
2\cdot x_1-6=0.
\]

Із цього отримуємо

\[
x_1^{(1)}=3.
\]

Отже, після першого кроку маємо проміжне наближення \( (3,0) \).

Тепер фіксуємо \( x_1=3 \) і мінімізуємо функцію за змінною \( x_2 \):

\[
\varphi_2(x_2)=f(3,x_2)=3^2+3\cdot x_2+x_2^2-6\cdot 3-4\cdot x_2.
\]

Після спрощення дістаємо

\[
\varphi_2(x_2)=x_2^2-x_2-9.
\]

Тоді

\[
\varphi_2′(x_2)=2\cdot x_2-1.
\]

Прирівнюємо її до нуля:

\[
2\cdot x_2-1=0.
\]

Отже,

\[
x_2^{(1)}=0.5.
\]

Після завершення першого повного циклу маємо точку

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

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

\[
f\bigl(\bar{x}^{(1)}\bigr)=f(3,0.500)=-9.250.
\]

Тепер перевіримо, чи виконується умова точності:

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

Оскільки

\[
3.041>0.05,
\]

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

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

Переходимо до другого повного циклу. Фіксуємо \( x_2=0.5 \) і розглядаємо функцію

\[
\varphi_1(x_1)=f(x_1,0.5)=x_1^2+0.5\cdot x_1+0.25-6\cdot x_1-2.
\]

Після спрощення маємо

\[
\varphi_1(x_1)=x_1^2-5.5\cdot x_1-1.75.
\]

Тоді

\[
\varphi_1′(x_1)=2\cdot x_1-5.5.
\]

Прирівнюємо її до нуля:

\[
2\cdot x_1-5.5=0.
\]

Звідси

\[
x_1=2.75.
\]

Після цього маємо проміжне наближення \( (2.75,0.5) \).

Тепер фіксуємо \( x_1=2.75 \) і мінімізуємо за \( x_2 \):

\[
\varphi_2(x_2)=f(2.75,x_2)=2.75^2+2.75\cdot x_2+x_2^2-6\cdot 2.75-4\cdot x_2.
\]

Після спрощення отримуємо

\[
\varphi_2(x_2)=x_2^2-1.25\cdot x_2-8.938.
\]

Знайдемо похідну:

\[
\varphi_2′(x_2)=2\cdot x_2-1.25.
\]

Прирівнюємо її до нуля:

\[
2\cdot x_2-1.25=0.
\]

Отже,

\[
x_2=0.625.
\]

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

\[
\bar{x}^{(2)}=(2.75,0.625).
\]

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

\[
f\bigl(\bar{x}^{(2)}\bigr)=f(2.75,0.625)\approx -9.328.
\]

Знову перевіримо, чи виконується умова точності:

\[
\|\bar{x}^{(2)}-\bar{x}^{(1)}\|
=\sqrt{(2.75-3)^2+(0.625-0.5)^2}
\approx 0.28.
\]

Оскільки

\[
0.28>0.05,
\]

переходимо до наступного циклу.

Розглянемо третій повний цикл. Спочатку фіксуємо \( x_2=0.625 \). Тоді

\[
\varphi_1(x_1)=f(x_1,0.625)=x_1^2+0.625\cdot x_1+0.391-6\cdot x_1-2.5.
\]

Після спрощення маємо

\[
\varphi_1(x_1)=x_1^2-5.375\cdot x_1-2.109.
\]

Її похідна дорівнює

\[
\varphi_1′(x_1)=2\cdot x_1-5.375.
\]

Прирівнюємо до нуля:

\[
2\cdot x_1-5.375=0.
\]

Тому

\[
x_1=2.688.
\]

Далі фіксуємо \( x_1=2.688 \) і мінімізуємо функцію за \( x_2 \):

\[
\varphi_2(x_2)=f(2.688,x_2)=2.688^2+2.688\cdot x_2+x_2^2-6\cdot 2.688-4\cdot x_2.
\]

Після спрощення отримуємо

\[
\varphi_2(x_2)=x_2^2-1.312\cdot x_2-8.903.
\]

Тоді

\[
\varphi_2′(x_2)=2\cdot x_2-1.312.
\]

Прирівнюємо до нуля:

\[
2\cdot x_2-1.312=0.
\]

Звідси

\[
x_2=0.656.
\]

Отже, після третього повного циклу маємо точку

\[
\bar{x}^{(3)}=(2.688,0.656).
\]

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

\[
f\bigl(\bar{x}^{(3)}\bigr)=f(2.688,0.656)\approx -9.333.
\]

Перевіряємо, чи виконується умова точності:

\[
\|\bar{x}^{(3)}-\bar{x}^{(2)}\|
=\sqrt{(2.688-2.75)^2+(0.656-0.625)^2}
\approx 0.069.
\]

Оскільки

\[
0.069>0.05,
\]

виконуємо ще один цикл.

На четвертому повному циклі спочатку фіксуємо \( x_2=0.656 \). Тоді розглядаємо функцію

\[
\varphi_1(x_1)=f(x_1,0.656)=x_1^2+0.656\cdot x_1+0.43-6\cdot x_1-2.624.
\]

Після спрощення маємо

\[
\varphi_1(x_1)=x_1^2-5.344\cdot x_1-2.194.
\]

Її похідна дорівнює

\[
\varphi_1′(x_1)=2\cdot x_1-5.344.
\]

Прирівнюємо до нуля:

\[
2\cdot x_1-5.344=0.
\]

Звідси

\[
x_1=2.672.
\]

Після цього фіксуємо \( x_1=2.672 \) і розглядаємо функцію за змінною \( x_2 \):

\[
\varphi_2(x_2)=f(2.672,x_2)=2.672^2+2.672\cdot x_2+x_2^2-6\cdot 2.672-4\cdot x_2.
\]

Після спрощення дістаємо

\[
\varphi_2(x_2)=x_2^2-1.328\cdot x_2-8.892.
\]

Тоді

\[
\varphi_2′(x_2)=2\cdot x_2-1.328.
\]

Прирівнюємо її до нуля:

\[
2\cdot x_2-1.328=0.
\]

Отже,

\[
x_2=0.664.
\]

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

\[
\bar{x}^{(4)}=(2.672,0.664).
\]

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

\[
\|\bar{x}^{(4)}-\bar{x}^{(3)}\|
=\sqrt{(2.672-2.688)^2+(0.664-0.656)^2}
\approx 0.018.
\]

Оскільки

\[
0.018<0.05,
\]

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

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

\[
f\bigl(\bar{x}^{(4)}\bigr)=f(2.672,0.664)\approx -9.333.
\]

Отже, наближене значення точки мінімуму дорівнює

\[
\bar{x}^{*}\approx (2.672,0.664),
\]

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

\[
f_{\min}\approx -9.333.
\]

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

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

\[
\frac{\partial f}{\partial x_1}=2\cdot x_1+x_2-6=0,
\qquad
\frac{\partial f}{\partial x_2}=x_1+2\cdot x_2-4=0.
\]

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

\[
x_1=\frac{8}{3}\approx 2.667,
\qquad
x_2=\frac{2}{3}\approx 0.667.
\]

Відповідне точне мінімальне значення дорівнює

\[
f\left(\frac{8}{3},\frac{2}{3}\right)
=-\frac{28}{3}\approx -9.333.
\]

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

\[
H=
\begin{pmatrix}
2 & 1\\
1 & 2
\end{pmatrix}.
\]

Її головні мінори задовольняють умови

\[
2>0,
\qquad
\det(H)=4-1=3>0.
\]

Отже, матриця \( H \) є додатно визначеною, а функція є строго опуклою. Саме тому точка

\[
\left(\frac{8}{3},\frac{2}{3}\right)
\]

є єдиною точкою глобального мінімуму.

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

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

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

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

Метод Покоординатного Спуску в Програмуванні: Спробуйте Реалізувати Алгоритм Самостійно

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