Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: , отже продовжуємо процедуру.
Перевіряємо умову зупинки: . Отже за точку локального мінімуму можна взяти середину відрізку . При цьому мінімальне значення вихідної функції буде рівним:
.
Метод дихотомії побудований таким чином, що кожний наступний інтервал невизначеності менше попереднього. Як бачимо, в порівнянні з методом золотого перерізу цей метод сходиться значно швидше (тобто через меншу кількість кроків отримуємо інтервал невизначеності заданої довжини, що містить (в методі дихотомії ми зробили 11 ітерацій, а в методі золотого перерізу - 16). Крім того, метод дихотомії потребує вдвічі менше обчислень, ніж метод золотого перерізу. Однак мінімальне значення функції знайдене обома методами співпадає, тому можемо зробити висновок, що доцільніше використовувати метод дихотомії для зменшення затрат часу на розв’язання задачі.
метод Фібоначчі
Спочатку згенеруємо послідовність чисел Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, … . Початкові обрахунки проводяться в точках: , де - число Фібоначчі, яке обирається з умови , тобто в нашому випадку це 18-те число Фібоначчі: . Ці точки розташовані симетрично відносно середини відрізку . На кожному кроці точка наступного обрахунку обирається симетрично відносно середини відрізка локалізації до точки уже проведеного обрахунку, що лежить на цьому відрізку. В силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена і дорівнює N=18. Отже можемо знайти початкові точки ділення:
. Далі обчислюємо значення функції в цих точках:
Оскільки , то покладаємо, що 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 ,