> 0, приймається рішення про закінчення процедури. В іншому випадку відбувається перехід на пункт 1).
Недоліки методу:
В· Метод має низьку ефективність (багаторазове повторення ітерацій).
В· Метод погано працює при яскраво вираженою В«яружноВ» функції => виникає В«заїданняВ» (зациклення) див. рис. 3.
Переваги методу:
В· Відносна простота програмування та тестування при налагодженні програми.
Блок-схема алгоритму методу покоординатного спуску
Метод сполучених градієнтів
Метод заснований на деяких властивостях квадратичних цільових функцій, апроксимація яких інших цільових функцій дозволяє істотно підвищити ефективність градієнтних методів.
Припустимо, що цільовою функцією є квадратична функція
.
Можна показати, що інформація про матрицю Н може бути отримана при певному програмуванні мінімуму функції. Для цього кожне наступне наближення будується згідно з наступною схемою
,
де - це напрямок пошуку, - крок пошук. Щоб забезпечити пошук мінімуму функції в напрямку враховує не тільки градієнт, але і вигин функції. визначається наступним чином
,
де коефіцієнт повинен задовольняти умовам сполучення
.
При цьому обидва вектори і називаються сполученими і в окремому випадку при умова сполучення стає умовою ортогональності векторів.
Виходячи з двох останніх умов, можна отримати вирази (співвідношення) для коефіцієнтів, а саме
.
Що хитається кроку, він вибирається з умови мінімізації функції в напрямку.
В
Величина цього кроку може бути отримана аналітично, якщо розглядається квадратична функція
В
Зауваження: можна показати, що пошук мінімуму квадратичної функції типу повинен бути завершений за k кроків (це випливає з умови взаємної ортогональності всіх градієнтів пошуку мінімуму).
Після тотожних перетворень отримані співвідношення можуть бути перетворені і незалежні від матриці Н і коефіцієнтів.
В
Якщо отримане співвідношення доповнити заміною аналітичного пошуку кроку процедурою одновимірного пошуку функції в напрямку з точки, то можна сформувати алгоритм пошуку мінімуму функції першого порядку незалежно від знання матриці Н.
Алгоритм Флетчера - Рівса
. Вибрати початкову точку пошуку;
. Визначити напрямок початкового пошуку;
. Здійснити одновимірний пошук точки
;
. Визначити новий напрямок пошуку,
де.
. У загальному випадку після точки обчислюється градієнт ф...
