Всі методи спуска рішення завдання безумовної мінімізації розрізняються або вибором напрямку спуска, або способом руху уздовж напрямку спуска. Це дозволяє написати загальну схему методів спуска
Вирішується завдання мінімізації функції j (x) на всьому просторі E n . Методи спуска складаються в наступній процедурі побудови послідовності {x k }. ? якості початкового наближення вибирається будь-яка крапка x 0 ? E n . Послідовні наближення x 1 , x 2 , ... будуються за наступною схемою:
- у крапці x k вибирають напрямок спуска - S k ;
- знаходять (k+1)-е наближення по формулі x k+1 =x k -p k S k .
Напрямок S k вибирають таким чином, щоб забезпечити нерівність j (x k+1 )< j (x k ) принаймні для малих значень величини p k . На питання, якому зі способів вибору напрямку спуска варто віддати перевагу при рішенні конкретного завдання, однозначної відповіді немає
Число p k визначає відстань від крапки x k до крапки х k+1 . Це число називається довжиною кроку або просто кроком. Основне завдання при виборі величини b k - це забезпечити виконання нерівності j (x k+1 )< j (x k ). Одним з елементарних способів вибору кроку є спосіб подвоєння кроку
Вибирають b k = b k-1 . Якщо при цьому j (x k+1 )< j (x k ), то або переходять до наступній (k+2)-й ітерації, або вибирають b k =2 b k-1 . Якщо значення j (х) менше його попереднього значення, то процес подвоєння можна продовжувати доти, поки убування не припиниться. Якщо j (x k+1 ) ? j (x k ), те вибирають b k =0.5 b k-1 . Якщо j (x k -0.5 b k-1 S k )< j (x k ), то думають x k+1 =x k -0.5 b k-1 S k і переходять до наступній (k+2)-й ітерації. Якщо ж j (x k -0.5 b k-1 S k ) ? j (x k ), те вибирають b k =0.25 b k-1 і т.д
Метод градиентного спуска
Одним з найпоширеніших методів мінімізації, пов'язаних з обчисленням градієнта, є метод спуска по напрямку антиградієнта минимизируемой функції. На користь такого вибору напрямку спуска можна привести наступні міркування. Оскільки антиградієнт, тобто j '(x k ) у крапці x k указує напрямок найшвидшого убування функції, те природним представляється зміститися із крапки x k по цьому напрямку
Метод спуска, у якому S k = j '(x k ), називається методом градиентного спуска
Величина b k у методі градиентного спуска традиційно обчислюється шляхом застосування одного з методів одномірної мінімізації функції y ( b )= j (x k - b j '(x k )), що не виключає застосування й інші способи відшукання b k
Якщо в якості b k вибирають крапку одномірного мінімуму функції y ( b )= j (x k - b S k ) релаксационний процес називається методом найшвидшого спуска: x k+1 =x k - b k j '(x k ), b k =arg min { y ( b )= j (x k - b S k ) | b ? 0}
Метод покоординатного спуска
Одним з найбільш простих способів визначення напрямку спуска є вибір у якості S k одного з координатних векторів ± e 1 , ± e 2 , ..., ± e n , внаслідок чого в x k на кожній ітерації змінюється лише один з компонентів
Існують численні варіанти покоординатного спуска. Але в кожному із цих методів вибирають у якості -S k те із двох напрямків, +e j , -e j , якому відповідає нерівність
[ j '(x k ), S k ] > 0
У випадку, якщо =0, думають x k+1 =x k і переходять до наступної ітерації
Опишемо перший цикл методу, що складає з n ітерацій. У довільній крапці x 0 вибирають S 0 = ± e, і визначає величину b 0 способом подвоєння так, щоб було j (x 1 )= j (x 0 - b 0 S 0 )< j (x 0 ). Потім вибирають S 1 = ± e 2 і, думаючи b = b 0 , подвоєнням обчислюють b 1 і так далі. При цьому на кожній ітерації прагнуть визначення величини кроку методом подвоєння здійснювати з найменшим числом обчислень значень функції j (х). Цикл закінчується при k= n-1, після чого починають наступний цикл, думаючи S n = ± e 1 і т.д
Практичне завдання
На практиці нам потрібно було знайти мінімум функції z(x)=x 2 +y 2 - xy-3y c точністю e , використовуючи описані вище методи
Знаходження мінімуму моєї функції за допомогою методу покоординатного спуска
Для знаходження мінімуму моєї функції за допомогою методу покоординатного спуска я використовував програму, представлену нижче. Вхідними параметрами цієї програми є координати початкової крапки (я взяв х=10, y=10), початковий крок по х і по y (я взяв D х=0.5 і D y=0.5), а так само точність ( e =10 -5 ; більшу точність брати не має змісту, оскільки під час виконання програми накопичується помилка й спотворює дані такої точності). Отже, взявши як початкові умови ці значення я одержав координати крапки мінімуму:
х= 1,00000977
y= 1,99999931
z=-3,00000142
Для одержання результату програмою було виконано 24 ітерації
Знаходження мінімуму за допомогою методу градиентного спуска
Програма, використана мною для виконання цього завдання представлена нижче
Оскільки вхідні параметри цієї програми збігаються із вхідними параметрами завдання №1, то я взяв їх такі ж, що й для першого завдання, щоб, зрівнявши отримані результати й кількість ітерацій, необхідних для пошуку мінімуму, я зміг зробити які-небудь висновки про переваги й недоліки обох завдань із практики
Отже, взявши ті ж початкові умови я одержав наступні результати:
x= 1,00000234
y= 2,00000119
z=-3,00000094
Кількість ітерацій, що треба було для знаходження крапки мінімуму дорівнює 20. Видно, що кількість ітерацій, потребовавшееся першій програмі більше, ніж кількість ітерацій, необхідних другій програмі. Це треба з того, що антиградієнт указує напрямок найшвидшого убування функції
Нижче також представлений графік збіжності вищеописаного процесу для моєї функції й моїх початкових умов
Необхідно також додати кілька важливих моментів. По-перше, з того, що кількість ітерацій, потребовавшееся для знаходження мінімуму в першому завданні більше, ніж у другий не треба той факт, що друга програма працює швидше, ніж перша, оскільки для другого завдання необхідно обчислювати не тільки значення функції в якій-небудь крапці, але і її похідній у цій крапці, що може бути більше громіздка, чим сама функція. Нарешті, другий метод поганий ще й тому, що для довільної функції похідну обчислити неможливо; прийде спочатку апроксимувати її, а потім шукати мінімум (за рахунок апроксимації значно виростає час і погрішність вимірів)