1.5 Модифікований метод Ньютона.

При оптимізації неквадратичних функцій метод Ньютона не відрізняється високою надійністю. Якщо початкова точка перебуває на значній відстані від екстремуму, то крок по методу Ньютона може бути надмірно великим, що може привести до відсутності збіжності. Модифікація методу дозволяє істотно підвищити його ефективність:

,

Методи Ньютона використовуються, якщо обчислення точних значень перших і других похідних не зв”зане істотними труднощами.

1.8 Методи змінної метрики.

Ідея методу полягає у використанні інформації про градієнт критерію оптимальності для наближеного обчислення зворотної матриці других похідних. Пошук ведеться по формулі:

,

де ^(k) - приблизно зворотна матриця Гессе; К-параметр кроку.

Головна перевага методу змінної метрики перед методом Ньютона - відмова від обчислення матриці Гессе на кожній ітерації. Методи змінної метрики відрізняються, в основному, способом обчислення матриці ^(k). У методі Девідона-Флетчера-Пауелла (ДФП) матриця ^(k) обчислюється по формулі:

Ж;

де .

Матриця ^(k) зветься метрикою. Вона змінюється на кожній ітерації. Тому методи називаються методами змінної метрики. Таким чином, алгоритм ДФП має вигляд:

;

;

;

;

;

;

.

Критерій зупинки:

ПРИКЛАД. Розрахунок чотирьох кроків пошуку методом змінної метрики.

Задана функція.

.

Алгоритм змінної метрики має вигляд

.

Вибираємо початкову точку і початкове значення матриці .

.

Крок 1. Розраховуємо градієнт в нульовій точці

.

Крок 2. Виконуємо пошук уздовж прямої. Спочатку розрахуємо координати точки як функції скалярного множника .

;

Підставим в оптимізуєму функцію знайдені величини.

.

Виконуємо оптимізацію по одержаного виразу.

Для знаходження екстремуму можна застосувати будь-який метод одномірної оптимізації.

Знайдемо першу похідну від виразу для

.

Звідси вирахуємо початкове значення оптимального параметру кроку

.

Розрахуємо координати точки

.

Крок 3. Вирахуємо градієнт в точці , а також значення

;

;

;

Знайдемо матрицю

.

Обчислюємо координати точки

.

Крок 4.Пошук уздовж прямої в результаті якого визначаємо , тобто вертаємося на крок 2.

Недоліки і переваги методу ДФП.

1.Схильність до нагромадження похибок обчислень при перерахуванні матриці . Тому матрицю треба під час розрахунків періодично поновлювати, тобто штучно робити одиничною.

2.Висока чутливість до точності визначення перших похідних.

При тестових випробуваннях алгоритмів метод ДФП виявив себе як найбільш ефективний за кількістю необхідних кроків пошуку.

Завдання на лабораторну роботу.

Завдання 1. Вивчення методів оптимізації.

1. Вивчити найпростіший градієнтний метод оптимізації, метод крутого спуску, метод найшвидшого спуску, методи Ньютона, метод ДФП.

2. Виконати вправи, наведені в Додатку 1 відповідно до свого варіанту.

Завдання 2. Формулювання задачі оптимізації.

1. Сформулювати задачу оптимізації, змістовна постановка якої наведена в Додатку 2. (Завдання вибрати за узгодженням з викладачем.)

2. Звести задачу умовної оптимізації до задачі безумовної оптимізації, підготувати вихідні дані для рішення її на ЕОМ.

Завдання 3. Розробити структурну схему алгоритму оптимізації.

№ варіанта	1	2	3	4	5
Метод	Ньютона	Флетчера-ДФП	Ньютона. модифікований	Найшвидшого спуску	Градієнтний з адаптивним кроком

Завдання 4. Розробка програми оптимізації.

1. Для зазначеного викладачем методу розробити структурну схему алгоритму й програму на одній з мов програмування (додаток 5).

2. Вибрати контрольний приклад і виконати один ітераційний цикл при підготовці до лабораторної роботи.

Завдання 5. Налагодження програми.

Виконати налагодження розробленої програми оптимізації.

Завдання 6. Виконати дослідження роботи алгоритму з використанням розробленої програми.

1. Для дослідження взяти функцію

Параметр дорівнює номеру варіанта. Величини , вибирати за узгодженням з викладачем. Коефіцієнти необхідно змінювати в процесі досліджування, з метою їх впливу на пошук екстремуму.

2. Визначити вплив параметрів алгоритму, а також величин початкових умов на процес пошуку екстремуму. Визначити найкраще значення параметрів алгоритму.

Завдання 7.Рішення задачі свого варіанту оптимізації сформульованої в додатку 2 згідно свого варіанту.

Завдання 8.

Вибрати метод оптимізації й вирішити задачу, наведену в Додатку 4 (відповідно до свого варіанту).

Зміст звіту.

1. Ціль роботи.

2. Короткі відомості про досліджувані методи і алгоритми.

3. Результати виконання завдань 1,2,3.

4. Текст програми. Розрахунок по контрольному прикладі.

5. Результати рішень завдань і досліджень алгоритму.

6. Висновки.