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

курсовая работа

3. Розвязання задачі мінімізації за допомогою методу Ньютона і методу найшвидшого спуску

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

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

Знайдемо частинні похідні першого і другого порядку від функції :

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

. А оскільки головні мінори додатні: , то матриця Гессе додатно визначена. Тобто достатні умови існування локального мінімуму виконані.

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

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

.

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

Знайдемо градієнт цільової функції:і обчислимо його в точці : .

Знайдемо наступне наближення до оптимального розвязку вихідної задачі: і обчислимо градієнт цільової функції в цій точці: . Рівність градієнта цільової функції нулю є необхідною умовою існування екстремуму функції багатьох змінних. Тобто оптимальний розвязок задачі , причому .

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

За даним методом будується послідовність точок , яка прямує до оптимального розвязку задачі - . Від точки до точки рухаються в напрямі градієнта цільової функції, обчисленого в точці .

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

Алгоритм методу найшвидшого спуску:

1. Обираємо довільну початкову точку , яка називається початковим наближенням розвязку задачі , і покладаємо, що При цьому функція вважається опуклою і неперервно диференційованою в . Також обираємо точність обчислень .

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

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

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

5. Покладаємо, що і переходимо до кроку 2.

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Делись добром ;)