Мінімізація функції багатьох змінних. Наближені чисельні методи. Метод Монте-Карло
1. Мінімізація функції багатьох змінних. Аналітичні методи.
Теорема Вейєрштрасса: нехай - Безліч функцій неперервних на замкненому обмеженому безлічі . Якщо , Тоді досягає своїх найбільшого і найменшого значень.
Визначення: точки максимуму і мінімуму називаються точками екстремуму функції. Теорема Ферма: (необхідна умова існування екстремуму). Нехай функція - Визначена в околиці точки . Якщо - Є точкою екстремуму функції , І в цій точці існують частинні похідні, тоді
(1)
Узагальнення: якщо - Точка екстремуму, то в цій точці або виконується формула (1), або похідна не визначена. Визначення: точки, в яких виконується умова (1), називаються точками екстремуму функції . Зараз викладемо достатні умови існування екстремумів функції багатьох змінних. Для цього пригадаємо деякі відомості з теорії квадратичних форм.
Визначення: квадратична форма
(2)
(3)
називається позитивно (негативно) певної, якщо (Відповідно ) Для будь-якого , За умови , І звертається в нуль, тільки при .
Приклад:
- Позитивно-визначена форма.
- Не є позитивно-певної, хоча , Тому що .
- Негативно-визначена форма.
Визначення: квадратичну форму, яка приймає як позитивні, так і негативні значення називають невизначеною формою.
Приклад:
4) - Невизначена квадратична форма.
Тепер, ми вже можемо сформулювати достатні умови існування екстремумів для функції багатьох змінних.
Теорема: нехай , І нехай є критичною точкою функції . Якщо квадратична форма
(4)
(Тобто другий диференціал функції в точці ) Є позитивно-певної (негативно-визначеній) квадратичною формою, то точка - Є точкою мінімуму (відповідно максимуму). Якщо ж квадратична форма (4) є невизначеною, то в точці - Екстремуму немає.
На запитання: коли квадратична форма є позитивно (або негативно) певної, відповідає критерій Сильвестра:
Для того, щоб квадратичні форми (2), (3) були позитивно-визначеними, необхідно і достатньо, щоб
(5)
Для того, щоб квадратична форма (2), (3) була негативно-визначеної, необхідно і достатньо, щоб
(6)
(7)
Як бачимо, для знаходження точок екстремуму нам потрібно вирішувати систему, загалом, нелінійних рівнянь (1), а для з'ясування характеру точки екстремуму потрібно на основі критерію Сильвестра перевіряти умови (5), (6) і (7) для диференціальної квадратичної форми ( 4) у точці екстремуму. Проілюструємо цей метод на прикладі 5: Функція двох змінних:
(8)
Рішення: знайдемо критичні точки:
(9)
звідки отримуємо критичні точки: А (0, 0); В (3, 2). Досліджуємо ці точки. Для цього нам потрібно з'ясувати, в кожній з цих точок, до якого виду належить квадратична форма:
(10)
(11)
(12)
(13)
У точці A (0, 0) маємо:
,
так що , І умови критерію
Сильвестра не дають відповіді на питання про наявність екстремуму в цій точці.
Для вирішення цього питання треба залучити старші похідні і форми більш високого порядку, для яких відповідної загальної теорії поки немає, тому потрібно звертатися до чисельних досліджень.
У точці B (3, 2) маємо:
,
отримуємо матрицю квадратичної форми:
.
тобто за критерієм Сильвестра B (3, 2) є точкою максимуму:
2. Метод градієнтного спуску.
Як ми бачили з останнього чисельного прикладу, строгий аналітичний метод не завжди приводить до мети (випадок, коли у критичній точці). У подібних, і в складніших випадках застосовують різні наближені аналітичні методи, які в математичному сенсі іноді менш строго обгрунтовані, але, тим не менш часом призводять до бажаного результату. До таких методів відносяться і градієнтні методи найшвидшого спуску.
Нехай, нам потрібно знайти . Розглянемо деяку точку і обчислимо в цій точці градієнт функції :
(14)
де - Ортонормованій базис в просторі . Якщо , То вважаємо:
(15)
де , А вибирається з умови збіжності ітераційного процесу:
(16)
де , А вибираються з умови збіжності. Формулу (16) можна розписати у вигляді:
перше наближення; (17)
друге наближення; (18)
... ... ... ... ... ... ... ... ... ..
m-те наближення; (19)
Тут m - число ітерацій. Процес ітерації зупиняється, коли досягається необхідна гранична похибка, тобто коли виконані умови зупинки ітерації:
(20)
Приклад 6: Знайти мінімум функції
Рішення: візьмемо початкову точку . З (14) маємо:
(21)
(22)
Складаємо итерационную формулу (16):
(23)
Маємо:
(24)
(25)
(26)
Ясно, що якщо h вибрати так, щоб , Тобто , То ітерація (26) сходиться і (27)
Інакше кажучи:
(28)
Приклад 7: Знайти точку мінімуму функції .
Рішення: візьмемо початкове наближення , Ясно, що . Тому, з (16) отримуємо итерационную формулу:
(29)
Зрозуміло, що
(30)
тому:
(31)
(32)
Далі, якщо , Отримуємо, що , Тобто:
(33)
Приклад 8: Знайти точки мінімуму функції .
Рішення: вибираємо початкову точку (1,1). Складаємо итерационную формулу:
(34)
Розпишемо детальніше:
(35)
(36)
Якщо перейти до межі в (36), при і :
(37)
то отримаємо точку мінімуму (1, -2).
(38)
3. Метод Монте-Карло.
Для мінімізації функції багатьох змінних розроблено безліч чисельних методів, але більшість з них пов'язана з підрахунком градієнта функції, що зі свого боку може дати ефективні алгоритми обчислення лише, якщо вдається аналітично підрахувати приватні похідні. Між тим, більш універсальним методом мінімізації функції багатьох змінних є метод перебору, при якому довільним чином розбивається область визначення функцій на симплекс і в кожному вузлі симплекса обчислюється значення функції, причому відбувається порівняння - перебір значень і на друк виводиться точка мінімуму та значення функції в цій точці.
У методі Монте-Карло задамо функцію . Вибираємо область пошуку рішення задачі:
(39)
а) Виконуємо випадкові кидки, тобто вибираємо значення , Для кожної змінної за формулою:
, Де (40)
б) Порівнюємо значення функції:
(41)
якщо ця нерівність виконується, то
(42)
якщо (41) не виконується, то
(43)
в) Процес випадкових кидків триває до досягнення заданої точності ; Число випадкових кидків m задовольняє умові:
(44)
Де
(45)
(46)