Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
Отже
можемо застосувати
метод Ньютона.
Послідовність
точок, яка прямує
до точки мінімуму
функції
згідно цього
методу знаходиться
за формулою:
,
де
- обернена матриця
Гессе.
.
Обиремо
в допустимій
області задачі
довільну точку
– початкове
наближення.
Нехай це буде
точка
.
Знайдемо
градієнт цільової
функції:
і
обчислимо його
в точці
:
.
Знайдемо
наступне наближення
до оптимального
розв’язку
вихідної задачі:
і обчислимо
градієнт цільової
функції в цій
точці:
.
Рівність градієнта
цільової функції
нулю є необхідною
умовою існування
екстремуму
функції багатьох
змінних. Тобто
оптимальний
розв’язок
задачі
,
причому
.
Тепер
розв’яжемо
задачу мінімізації
для функції
,
використовуючи
метод
найшвидшого
спуску.
Цей метод відноситься
до градієнтних
методів.
За
даним методом
будується
послідовність
точок
,
яка прямує до
оптимального
розв’язку
задачі -
.
Від точки
до точки
рухаються в
напрямі градієнта
цільової функції,
обчисленого
в точці
.
Широке
застосування
цього методу
обумовлено
тим, що в напряму
антиградієнту
—
похідна
функції за
напрямом досягає
найменшого
значення.
Алгоритм методу найшвидшого спуску:
Обираємо
довільну початкову
точку
,
яка називається
початковим
наближенням
розв’язку
задачі
,
і покладаємо,
що
При цьому функція
вважається
опуклою і неперервно
диференційованою
в
.
Також обираємо
точність обчислень
.
Обчислюємо
градієнт цільової
функції
.
Якщо
,
то покладаємо
і зупиняємо
обчислення,
інакше - переходимо
до кроку 3.
Шукаємо
наступне наближення
за формулою:
-
для задачі
мінімізації,
а для задачі
максимізації:
.
Число
- параметр, який
називається
довжиною кроку
в точці
.
Його обирають
довільно, однак
зазвичай, параметр
обирається
з умови, щоб в
точці
спостерігалося
максимальне
зменшення
(збільшення)
цільової функції
.
Перевіряємо
умову зупинки,
а саме:
.
Якщо умова
виконана, то
покладаємо
і зупиняємо
обчислення,
якщо ні, то
переходимо
до наступного
кроку.
Покладаємо,
що
і переходимо
до кроку 2.
Тепер перейдемо безпосередньо до нашого прикладу.
Оберемо
спочатку точність
обчислень
.
За початкове
наближення
як і в методі
Ньютона візьмемо
точку
.
З аналізу,
проведеного
в методі Ньютона,
маємо що цільова
функція є опуклою
і неперервно
диференційованою
в Rn,
отже даний
метод застосовувати
можна.
З
методу Ньютона
маємо, що градієнт
цільової функції
в точці
буде рівним
.
Оскільки
,
то шукаємо
наступне наближення
розв’язку
вихідної задачі:
.
Знайдемо
:
.
Оскільки
обирається
з умови, щоб в
точці
спостерігалося
максимальне
зменшення
,
знайдемо похідну
від цільової
функції в точці
і прирівняємо
її до нуля.

Отже
можемо тепер
знайти координати
точки
:
.
Обчислимо
значення цільової
функції в цій
точці:
.
Перевіряємо умову зупинки:
отже
шукаємо наступне
наближення
аналогічним
чином.
![]()



Отже
можемо тепер
знайти координати
точки
:
Обчислимо
значення цільової
функції в цій
точці:
.
Перевіряємо умову зупинки:
отже
шукаємо наступне
наближення:
![]()



Отже
можемо тепер
знайти координати
точки
:
.
Обчислимо
значення цільової
функції в цій
точці:
Перевіряємо
умову зупинки:
отже
шукаємо наступне
наближення:
![]()



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

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