Курсовая работа: Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування

Отже можемо тепер знайти координати точки : Обчислимо значення цільової функції в цій точці: .

Перевіряємо умову зупинки:

отже шукаємо наступне наближення:

Отже можемо тепер знайти координати точки : .

Обчислимо значення цільової функції в цій точці: Перевіряємо умову зупинки:

отже шукаємо наступне наближення:

Отже можемо тепер знайти координати точки : .

Обчислимо значення цільової функції в цій точці: Перевіряємо умову зупинки:

, тобто умову зупинки виконано. Отже .

Як бачимо, розв’язки задачі, знайдені обома методами майже однакові, але при цьому метод Ньютона дав результат вже на першому кроці ( на відміну від методу найшвидшого спуску, де довелося робити 4 ітерації). Це пов’язано з тим, що цільова функція є квадратичною, а отже напрям спуску завжди співпадає з напрямом в точку мінімуму . Тобто основна перевага методу Ньютона - швидка збіжність, однак при цьому суттєвим недоліком є залежність збіжності від початкового наближення . Крім того у випадку не квадратичної цільової функції трудомісткість ітерації методом Ньютона може виявитись дуже великою за рахунок необхідності обчислення матриці других похідних мінімізуємої функції, що потребує затрат великої кількості часу.

Розв’язання задачі умовної оптимізації за допомогою методу Франка-Вулфа і методу штрафних функції

4. Розв’яжемо задачу умовної оптимізації

a. методом Франка-Вулфа

Функція являється вгнутою так як представляє собою суму лінійної функції (її можна розглядати як вгнуту) і квадратичної форми, яка являється від’ємно визначеною і тому також являється вгнутою. Перевіримо завдяки матриці Гессе від’ємну визначеність функції . Для цього спочатку знайдемо частинні похідні першого і другого порядку від функції :

Отже матриця Гессе матиме вигляд:

Головні мінори :оскільки в ряді знаки чергуються, то дана матриця є від’ємно визначеною, я отже функція - вгнута.

Система обмежень задачі включає тільки лінійні нерівності, які утворюють опуклу множину, отже дана задача є задачею опуклого програмування.

Задачу такого типу можна розв’язувати методом Франка-Вулфа. Цей метод відноситься до групи градієнтних методів.

Розглянемо задачу: