повторів обчислення функції) методу.
Показано, що значення a можна визначати за деякими характеристиками функції f (x). Наприклад, якщо існує така константа R, що для будь-яких точок
Якщо відома оцінка М зверху максимального власного числа матриці, то рекомендується прийняти.
Однак, значення R і M зазвичай заздалегідь невідомі.
Розроблено різні методи, які відносяться до групи градієнтного спуску. Серед них: з постійним кроком, з дробовим кроком і найшвидшого спуску.
Основним недоліком градиентного методу є необхідність частого обчислення похідних. Цього недоліку позбавлений метод найшвидшого спуску.
Особливість методу найшвидшого спуску в тому, що в напрямку антіградіента шукається точка, що доставляє мінімум функції. Пошук цього мінімуму може здійснюватися будь-яким з відомих методів одновимірної мінімізації.
У цьому методі направлення з стосується лінії в
Далеко від оптимуму ефективність методу найшвидшого спуску підвищується в порівнянні з градієнтними методами, а в околиці знижується через часту зміну напрямків.
Всі градієнтні методи погано працюють в яружних функціях.
Умови закінчення ітераційного пошуку в градієнтних методах пов'язують зазвичай з величиною градієнта (критерій з номером 3).
Градієнтні методи відносяться до групи методів 1 порядку, т.к. спираються на обчислення першої похідної. Більш ефективними можуть бути методи другого порядку, які в тому числі використовують другі похідні. Однак, тут можуть виникнути труднощі з обчисленням і дослідженням матриці других похідних (матриці Гессе).
Метод сполучених градієнтів є спробою об'єднати гідності методів першого і другого порядків з виключенням їх недоліків.
На початкових метод сполучених градієнтів поводиться, як метод першого порядку, а в околиці оптимуму наближається до методів другого порядку.
Перший крок аналогічний першому кроці методу найшвидшого спуску, а кожен наступний - у напрямку, утвореному у вигляді лінійної комбінації векторів градієнта в даній точці і попереднього спрямування.
Для квадратичної функції (дуже ефективний) значення оптимуму цим методом можна отримати за n кроків, де n - розмірність задачі.
Метод важкого кульки
Метод базується на аналогії з рухом важкого матеріального кульки по похилій поверхні.
Швидкість кульки при русі вниз зростатиме, і він буде прагнути зайняти нижнє положення, тобто точку мінімуму.
Xi +1=Xi - a (Xi - Xi - 1) - h grad F (X i )
При a=0 - метод перетворюється на звичайний градієнтний. При 0 < a < 1 можна отримувати різну ефективність методу, яка буде залежати і від h. Далеко від оптимуму пошук буде прискорюватися, а поблизу можливі коливання біля мінімуму.
a - визначає пам'ять алгоритму, т. е враховує вплив попередньої точки, тому збільшення цього параметра поблизу мінімуму може привести до більш швидкого загасання, якщо градієнт функції малий. Кращий, коли глобальний мінімум яскраво виражений і локальні крейда.
Метод Ньютона
Метод Ньютона відноситься до методів другого порядку. Особливість його в тому, що для вибору напрямку пошуку використовується не сама функція, а її апроксимація квадратичною функцією. Збіжність методу доведена тільки для класу опуклих функції.
Метод випадкового п...
