Загальна схема.
Всі методи спуску рішення задачі безумовної мінімізації розрізняються або вибором напрямку спуска, або способом руху вздовж напрямку спуску. Це дозволяє написати загальну схему методів спуска.
Вирішується завдання мінімізації функції j (X) на всьому просторі En. Методи спуску складаються в наступній процедурі побудови послідовності {xk}. Г‚ якості початкового наближення вибирається будь-яка точка x0ГЋ En. Послідовні наближення x1, x2, ... будуються за наступною схемою:
в точці xk вибирають напрям спуску - Sk;
знаходять (k +1)-е наближення за формулою xk +1 = xk-pkSk.
Напрям Sk вибирають таким чином, щоб забезпечити нерівність j (Xk +1)
Число pk визначає відстань від точки xk до точки хk +1. Це число називається довжиною кроку або просто кроком. Основне завдання при виборі величини b k - це забезпечити виконання нерівності j (Xk +1) спосіб подвоєння кроку.
Вибирають b k = b k-1. Якщо при цьому j (Xk +1)
Метод градієнтного спуску.
Одним з найпоширеніших методів мінімізації, пов'язаних з обчисленням градієнта, є метод спуску по напрямку антіградіента минимизируемой функції. На користь такого вибору напрямку спуска можна навести такі міркування. Оскільки антіградіента, тобто j '(Xk) в точці xk вказує напрямок найшвидшого убування функції, то природним представляється зміститися з точки xk за цим напрямком.
Метод спуску, в якому Sk = j '(Xk), називається методом градієнтного спуску.
Величина b k в методі градієнтного спуску традиційно обчислюється шляхом застосування одного з методів одновимірної мінімізації функції y (B ) = J (Xk-b j '(Xk)), що не виключає застосування й інших способів відшукання b k.
Якщо в якості b k вибирають точку одновимірного мінімуму функції y (B ) = J (Xk-b Sk) релаксаційний процес називається методом найшвидшого спуску: xk +1 = xk-b kj '(Xk), b k = arg min {y (B ) = J (Xk-b Sk) | b Ві 0}.
Метод покоординатного спуску.
Одним з найбільш простих способів визначення напрямку спуску є вибір в якості Sk одного з координатних векторів В± e1, В± e2, ..., В± en, внаслідок чого у xk на кожній ітерації змінюється лише одна з компонент.
Існують численні варіанти покоординатного спуску. Але в будь-якому з цих методів вибирають як-Sk то з двох напрямків, + ej,-ej, якому відповідає нерівність
[j '(Xk), Sk]> 0.
У випадку, якщо = 0, вважають xk +1 = xk і переходять до наступної ітерації.
Опишемо перший цикл методу, що складається з n ітерацій. У довільній точці x0 вибирають S0 = В± e, і визначає величину b 0 способом подвоєння так, щоб було j (X1) = j (X0-b 0S0)
Практичне завдання
На практиці нам потрібно було знайти мінімум функції z (x) = x2 + y2-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. Видно, що кількість ітерацій, потребовавшееся першій програмі більше, ніж кількість ітерацій, необхідних другій програмі. Це випливає з того, що антіградіента вказує напрямок найшвидшого убування функції.
Нижче також представлений графік збіжності вищеописаного процесу для моєї функції і моїх початкових умов.
Необхідно також додати кілька важливих моментів. По-перше, з того, що кількість ітерацій, потребовавшееся для знаходження мінімуму в першій завданню більше, ніж у другій не слід той факт, що друга програма працює швидше, ніж перша, оскільки для другої задачі необхідно обчислювати не тільки значення функції в якій- або точці, але і її похідної в цій точці, яка може бути більш громіздка, ніж сама функція. Нарешті, другий метод поганий ще й тому, що для довільної функції похідну обчислити неможливо; доведеться спочатку апроксимувати її, а потім шукати мінімум (за рахунок апроксимації значно виростає час і похибку вимірювань).
