Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Тобто функція
- Теорема про локальний екстремум
| Нелінійна безумовна оптимізація.
Метод найшвидшого спуску Визначення. Розглядаємо задачу безумовної оптимізації f(x)=у → min (1) де f, такий фунціонал, що вектор точку х Rm (переводить) → у число у R Точка x* що належить Rm є рішенням задачі (1) або є точкою глобального безумовного мінімуму/максимуму функції f, якщо / (2) при всіх x Rm Якщо нерівність (2) виконано лише для x, що лежать в деякій околиці Vx* точки x*, то точку x* називають локальним рішенням задачі (1), або точкою локального безумовного мінімуму функції f. Якщо нерівність (2) сувора при всіх x ≠ x *, то говорять про суворий глобальний і, відповідно, суворий локальний мінімум / максимум Необхідна умова локального екстремуму: Теорема Ферма: Якщо f - функція, що диференціюється і x* - її локальний екстремум, то f '(x *) = 0. Таким чином, екстремум функції може досягатися тільки в тих точках, де f '(x *) = 0, тоді вони можуть бути знайдені коли вирішимо систему (*) Таким чином визначаємо точки "підозрілі на єкстремум". Точки, що задовольняють рівняння (*), називають стаціонарними точками функції f. Стаціонарна точка x* функції f може бути або точкою локального мінімуму, або точкою локального максимуму, або перегину рис. 1 або сідловою точкою (рис.2) Точка (x*, y*) називається сідловою функції f , якщо при всіх (x, y) виконані нерівності f(x*, y) ≤ f(x*, y*) ≤ f(x, y*) Тобто функція f(x*, y*), в цій точці (x*, y*) по у завжди іі більше f(x*, y) ≤ f(x*, y*) - її мах по у а по х - завжди менше f(x*, y*) ≤ f(x, y*) - її мін по х рис.2 Далі необхідно з множини "підозрілих" вийти на тільки на ті, що нас цікавлять - тільки екстремальні точки: Теорема про локальний екстремум (необхідні і достатні умови другого порядку). Нехай x* - стаціонарна точка функції f, що двічі диференціюється. Для того, щоб точка x* була точкою (локального) мінімуму / максимуму функції f необхідно, щоб оператор гесіан в точці x *: А = f '' (x *) був ненегативно / непозитивно визначеним і достатьно, щоб він був позитивно / негативно визначеним. Нагадаємо, що гесіан має вигляд та позитивна визначенність матриці потребує щоб: 1. Визначники усіх кутових мінорів були >0 чи 2. Всі характеристичні числа були >0 чи ...... І так у підсумку, нам відомо, що для визначення "підозрілих" на екстремум точок необхідно вирішувати систему (*), а для визначення з них, які точки екстремальні - - скористатися теоремою про локальний екстремум. Однак загальних підходів, щоб аналітично вирішувати системи нелінійних рівнянь не існує, тому, як правило, вдаються до їх чисельного вирішення, що за фактом є деякою ітераційною процедурою руху точки рішення до безумовного мінімуму (чи максимуму). Нижче розглянемо один з найбільш часто вживаних методів такого численного вирішення - методу найшвидшого спуску. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|