Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування (стр. 5 из 9)

2. Обчислюємо градієнт цільової функції

. Якщо , то покладаємо і зупиняємо обчислення, інакше - переходимо до кроку 3.

3. Шукаємо наступне наближення за формулою:

- для задачі мінімізації, а для задачі максимізації: . Число - параметр, який називається довжиною кроку в точці . Його обирають довільно, однак зазвичай, параметр обирається з умови, щоб в точці спостерігалося максимальне зменшення (збільшення) цільової функції .

4. Перевіряємо умову зупинки, а саме:

. Якщо умова виконана, то покладаємо і зупиняємо обчислення, якщо ні, то переходимо до наступного кроку.

5. Покладаємо, що

і переходимо до кроку 2.

Тепер перейдемо безпосередньо до нашого прикладу.

Оберемо спочатку точність обчислень

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

З методу Ньютона маємо, що градієнт цільової функції в точці

буде рівним . Оскільки , то шукаємо наступне наближення розв’язку вихідної задачі:

.

Знайдемо

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

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

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

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

отже шукаємо наступне наближення аналогічним чином.

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

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

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

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

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

: .

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

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

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

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

: .

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

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

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

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

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

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

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

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

Функція

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

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

Головні мінори :

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

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

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

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

Алгоритм методу Франка-Вулфа:

1. Спочатку в допустимій області задачі обирають довільну точку

. Це можна зробити, наприклад, за допомогою методу штучного базису. Також обирають точність обчислень . Покладають