Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування (стр. 4 из 9)
Оскільки
, то покладаємо, що N=N-1=18-1=17. Нові межі відрізка тепер будуть рівними 
. Знаходимо нові точки ділення: 
. Значення функції в цих точках: 
Оскільки
N=16, нові межі відрізка - 
. 
Оскільки
N=15, нові межі відрізка - 
. 
Оскільки
N=14, нові межі відрізка - 
. 
Оскільки
N=13, нові межі відрізка - 
. 
Оскільки
N=12, нові межі відрізка - 
. 
Оскільки
N=11, нові межі відрізка - 
. 
Оскільки
N=10, нові межі відрізка - 
. 
Оскільки
N=9, нові межі відрізка - 
. 
Оскільки
N=8, нові межі відрізка - 
. 
Оскільки
N=7, нові межі відрізка - 
. 
Оскільки
N=6, нові межі відрізка - 
. 
Оскільки
N=5, нові межі відрізка - 
. 
Оскільки
N=4, нові межі відрізка - 
. 
Оскільки
N=3, нові межі відрізка - 
. 
Оскільки
, то локальний мінімум досягається в точці 
. При цьому мінімальне значення вихідної функції буде рівним: 
. Отже мінімальне значення функції, знайдене методом дихотомії, методом золотого перерізу і методом Фібоначчі співпадають. Однак найбільше ітерацій було зроблено при розв’занні задачі методом Фібоначчі.3. Розв’язання задачі мінімізації за допомогою методу Ньютона і методу найшвидшого спуску
Розв’яжемо задачу мінімізації для функції
, використовуючи метод Ньютона. Це метод другого порядку, який використовує похідну першого і другого порядку від цільової функції.Перш ніж розв’язувати дану задачу, з’ясуємо чи має вона точку локального мінімуму. Для цього побудуємо матрицю Гессе.
Знайдемо частинні похідні першого і другого порядку від функції
: 
Отже матриця Гессе матиме вигляд:
. А оскільки головні мінори додатні: 
, то матриця Гессе додатно визначена. Тобто достатні умови існування локального мінімуму виконані.Так як цільова функція є опуклою, тобто це задача опуклого програмування, а функція
є неперервно диференційованою в Rn , то якщо точка 
є точкою локального екстремуму, то вона буде і точкою глобального екстремуму для цієї задачі.Отже можемо застосувати метод Ньютона. Послідовність точок, яка прямує до точки мінімуму функції
згідно цього методу знаходиться за формулою: 
, де 
- обернена матриця Гессе. 
.Обиремо в допустимій області задачі довільну точку – початкове наближення. Нехай це буде точка
.Знайдемо градієнт цільової функції:
і обчислимо його в точці 
: 
.Знайдемо наступне наближення до оптимального розв’язку вихідної задачі:
і обчислимо градієнт цільової функції в цій точці: 
. Рівність градієнта цільової функції нулю є необхідною умовою існування екстремуму функції багатьох змінних. Тобто оптимальний розв’язок задачі 
, причому 
.Тепер розв’яжемо задачу мінімізації для функції
, використовуючи метод найшвидшого спуску. Цей метод відноситься до градієнтних методів.За даним методом будується послідовність точок
, яка прямує до оптимального розв’язку задачі - . Від точки 
до точки 
рухаються в напрямі градієнта цільової функції, обчисленого в точці .Широке застосування цього методу обумовлено тим, що в напряму антиградієнту —
похідна функції за напрямом досягає найменшого значення.Алгоритм методу найшвидшого спуску:
1. Обираємо довільну початкову точку
, яка називається початковим наближенням розв’язку задачі 
, і покладаємо, що 
При цьому функція 
вважається опуклою і неперервно диференційованою в 
. Також обираємо точність обчислень 
.