Реферат Класичні методи безумовної оптимізації

-->> (8)

Легко довести, що для точки локального максимуму необхідні умови будуть точно такими ж, як і для точки локального мінімуму, тобто умовами (8).

Зрозуміло, що підсумком докази буде нерівність виду: - умова непозитивно приросту функції в околиці локального максимуму.

Отримані необхідні умови не дають відповідь на питання: чи є стаціонарна точка точкою мінімуму або точкою максимуму.

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

2. Достатні умови для точки локального мінімуму (максимуму)

Уявімо розкладання функції в околі точки в ряд Тейлора з точністю до квадратичних по доданків.

(1)

Розкладання (1) можна представити більш стисло, використовуючи поняття: "скалярний добуток векторів" і "Векторно-матричне твір".

(1 ')

- матриця двох похідних від цільової функції по відповідним змінним.

,

Прирощення функції на підставі (1 ') можна записати у вигляді:

(3)

Враховуючи необхідні умови:

, (4)

Підставимо (3) у вигляді:

(4 ')

(5)

Квадратична форма називається диференціальної квадратичною формою (ДКФ).

Якщо ДКФ позитивно визначена, то і стаціонарна точка є точкою локального мінімуму.

Якщо ж ДКФ і матриця, її представляє, негативно визначені, то і стаціонарна точка є точкою локального максимуму.

Отже, необхідне і достатня умова для точки локального мінімуму мають вигляд

(ці ж необхідні умови можна записати так:

,, )

- достатня умова.

Відповідно, необхідна і достатня умова локального максимуму має вигляд:

, (),.

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

3. Критерій Сильвестра

Дозволяє відповісти на питання: чи є квадратична форма і матриця, її представляє, позитивно певної, або негативно визначеною.

Далі виклад буде щодо ДКФ і матриці її визначальною, тобто ДКФ виду

.

, - називається матрицею Гессе.

Головний визначник матриці Гессе

і ДКФ, яку вона представляє, будуть позитивно певними, якщо всі головні визначники матриці Гессе () позитивні (тобто має місце наступна схема знаків:

)

Якщо ж має місце інша схема знаків для головних визначників матриці Гессе, наприклад,, то матриця і ДКФ негативно визначені.

4. Метод Ейлера - класичний метод вирішення завдань безумовної оптимізації

Цей метод заснований на необхідних і достатніх умов, вивчених в 1.1 - 1.3; застосуємо знаходженню локальних екстремумів тільки безперервних диференційовних функцій.

Алгоритм цього методу досить простий:

використовуючи необхідні умови формуємо систему в загальному випадку нелінійних рівнянь. Відзначимо, що вирішити аналітично цю систему в загальному випадку неможливо; слід застосувати чисельні методи рішення систем нелінійних рівнянь (НУ) (див. "ЧС"). З цієї причини метод Ейлера буде аналітично-чисельним методом. Вирішуючи зазначену систему рівнянь знаходимо координати стаціонарної точки.;

досліджуємо ДКФ і матрицю Гессе, яка її представляє. За допомогою критерію Сильвестра визначаємо, чи є стаціонарна точка точкою мінімуму або точкою максимуму;

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

Методом Ейлера вирішити наступну задачу безумовної оптимізації: знайти 4 стаціонарні точки функції виду:

З'ясувати характер цих точок, чи є вони точками мінімуму, або сідлових (див. [3]). Побудувати графічне відображення цієї функції у просторі і на площині (за допомогою ліній рівня).

Далі цю функцію будемо іменувати типовий функцією, досліджуючи її екстремальні властивості всіма вивченими методами.

5. Класична задача умовної оптимізації та методи її вирішення: Метод виключення і Метод множників Лагранжа (ММЛ)

Як відомо, класична задача умовної оптимізації має вигляд:

(1)

(2)

Графік, що пояснює постановку задачі (1), (2) в просторі.

(1 ')

(2 ')

,

- рівняння ліній рівня

Отже, ОДР в розглянутій задачі являє собою деяку криву, представлену рівнянням (2 ').

Як видно з малюнка, точка є точкою безумовного глобального максимуму; точка - точкою умовного (відносного) локального мінімуму; точка - точка умовного (відносного) локального максимуму.

Завдання (1 '), (2') можна вирішити методом виключення (підстановки), вирішивши рівняння (2 ') щодо змінної, і підставляючи знайдене рішення (1 ').

Вихідна задача (1 '), (2 ') таким чином перетворена в задачу безумовної оптимізації функції, яку легко вирішити методом Ейлера.

Метод виключення (Підстановки).

Нехай цільова функція залежить від змінних:

називаються залежними змінними (або змінними стану); відповідно можна ввести вектор

Решту змінних називаються незалежними змінними рішення.

Відповідно можна говорити про вектор-стовпці:

і вектора.

У класичній задачі умовної оптимізації:

(1)

(2)

Система (2) в Відповідно до методу виключення (підстановки) повинна бути дозволена щодо залежних змінних (змінних стану), тобто повинні бути отримані наступні вирази для залежних змінних:

(3)

Чи завжди система рівнянь (2) розв'язана відносно залежних змінних - не завжди, це можливо лише у випадку, коли визначник, званий якобіаном, елементи якого мають вигляд:

,

не дорівнює нулю (див. відповідну теорему в курсі МА)

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

Підставляємо з (3) в цільову функцію (1), маємо:

(5)

Досліджувана функція на екстремум можна провести методом Ейлера - методом безумовної оптимізації безперервно диференціюється функції.

Отже, метод виключення (Підстановки) дозволяє використовувати завдання класичної умовно...