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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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