Мінімізація функції багатьох змінних. Наближені чисельні методи. Метод Монте-Карло
1. Мінімізація функції багатьох змінних. Аналітичні методи.
Теорема Вейєрштрасса: нехай - безліч функцій неперервних на замкненому обмеженій множині. Якщо, тоді досягає своїх найбільшого і найменшого значень.
Визначення: точки максимуму і мінімуму називаються точками екстремуму функції. Теорема Ферма: (Необхідна умова існування екстремуму). Нехай функція - визначена в околиці точки. Якщо - є точкою екстремуму функції, та в цій точці існують приватні похідні, тоді
(1)
Узагальнення: якщо - точка екстремуму, то в цій точці або виконується формула (1), або похідна не визначена. Визначення: точки, в яких виконується умова (1), називаються точками екстремуму функції . Зараз викладемо достатні умови існування екстремумів функції багатьох змінних. Для цього пригадаємо деякі відомості з теорії квадратичних форм.
Визначення: квадратична форма
(2)
(3)
називається позитивно (Негативно) певної, якщо (відповідно ) Для будь-якого, за умови, та звертається в нуль, тільки при.
Приклад:
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)
