в точці,.
В
Рис 5. Графічне пояснення методу Коші
Метод Ньютона
Опис алгоритму
Цей метод використовує інформацію про других похідних цільової функції. Ця інформація з'являється при квадратичної апроксимації цільової функції, коли при її розкладанні в ряд Тейлора враховуються члени ряду до другого порядку включно. Алгоритм методу виглядає наступним чином:
, де:
- гессіан (матриця Гессе)
У разі, коли гессіан позитивно визначений, напрямок за методом Ньютона виявляється напрямком узвозу.
Знаходження мінімуму цільової функції методом Ньютона.
Вихідні дані:
В
- початкова точка;
В В В В В В
;
В В
Таким чином, точка мінімуму, значення функції в якій знайдена за одну ітерацію.
В
Рис 6. Графічне пояснення методу Ньютона
Метод сполучених градієнтів
Опис алгоритму
Даний метод має позитивні властивості методів Коші і Ньютона. Крім того, цей метод використовує інформацію тільки про перші похідних досліджуваної функції. Метод сполучених градієнтів дозволяє отримати рішення за кроків у-вимірному просторі і володіє квадратичної збіжністю. В основі методу лежить організація пошуку уздовж сполучених напрямків, причому для отримання сполучених напрямків використовується квадратична апроксимація цільової функції і значення компонент градієнта. p> Операції аргументу проводяться за формулою:
В
Напрямок пошуку на кожній ітерації визначається за допомогою формули:
В
У цьому випадку напрямок буде-пов'язане з усіма раніше побудованими напрямками пошуку.
Якщо функція квадратична, то для знаходження точки екстремуму потрібно визначити таких напрямків і провести пошуки уздовж кожної прямої. Якщо не є квадратичної, то кількість пошуків зросте. p> Використовувані в методі формули:
В
Зміна градієнта при переході від точки до точки:
В В
Зміни аргументу:
В
Напрямок пошуку:
,,.
(рекуррентная формула Флетчера-Рівса).
Знаходження мінімуму цільової функції методом сполучених градієнтів.
Вихідні дані:
В
- початкова точка;
В В
Крок 1.
В В В
Крок 2.
Пошук уздовж прямої:
В В
Крок 3.
Визначимо напрямок:
// х1 в похідну
В В
Крок 4.
Пошук уздовж прямої:
В В
Таким чином, рішення (точка мінімуму), значення функції в якій, отримано в результаті двох одновимірних пошуків, оскільки цільова функція квадратична.
В
Рис 7. Графічне пояснення методу сполучених градієнтів
Квазіньютоновскій метод
Опис алгоритму
Даний метод володіє позитивними рисами методу Ньютона, проте, використовує інформацію тільки про пер...
