Мінімізація функції багатьох змінних. Наближені чисельні методи. Метод Монте-Карло
1. Мінімізація функції багатьох змінних. Аналітичні методи. br/>
Теорема Вейєрштрасса: нехай - безліч функцій неперервних на замкненому обмеженій множині. Якщо, тоді досягає своїх найбільшого та найменшого значень.
Визначення: точки максимуму і мінімуму називаються точками екстремуму функції. Теорема Ферма: (Необхідна умова існування екстремуму). Нехай функція - визначена в околиці точки. Якщо - є точкою екстремуму функції, і в цій точці існують приватні похідні, тоді
(1)
Узагальнення: якщо - точка екстремуму, то в цій точці або виконується формула (1), або похідна не визначена. Визначення: точки, в яких виконується умова (1), називаються точками екстремуму функції. Зараз викладемо достатні умови існування екстремумів функції багатьох змінних. Для цього згадаємо деякі відомості з теорії квадратичних форм.
Визначення: квадратична форма
(2)
(3)
називається позитивно (Негативно) певної, якщо (відповідно) для будь-якого, при умови, і звертається в нуль, тільки при.
Приклад:
1) - Позитивно-визначена форма. p> 2) - Не є позитивно-певної, хоча, тому що . p> 3) - Негативно-визначена форма. br/>
Визначення: квадратичну форму, яка приймає як позитивні, так і негативні значення називають невизначеною формою.
Приклад:
4) - невизначена квадратична форма.
Тепер, ми вже можемо сформулювати достатні умови існування екстремумів для функції багатьох змінних.
Теорема: нехай, і нехай є критичною точкою функції. Якщо квадратична форма
(4)
(тобто другий диференціал функції в точці) є позитивно-певної (негативно-визначеній) квадратичною формою, то точка - є точкою мінімуму (відповідно максимуму). Якщо ж квадратична форма (4) є невизначеною, то в точці - екстремуму немає. p> На питання: коли квадратична форма є позитивно (або негативно) певної, відповідає критерій Сильвестра:
Для того, щоб квадратичні форми (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) маємо:
, br/>
так що, і умови критерію
Сильвестра не дають відповіді на питання про наявність екстремуму в цій точці. p> Для вирішення цього питання треба залучити старші похідні і форми більш високого порядку, для яких відповідної загальної теорії поки немає, тому потрібно звертатися до чисельних дослідженням. p> У точці B (3, 2) маємо:
, br/>
отримуємо матрицю квадратичної форми:
. <В
тобто за умовою Сильвестра B (3, 2) є точкою максимуму:
2. Метод градієнтного спуску. br/>
Як ми бачили з останнього чисельного прикладу, строгий аналітичний метод не завжди призводить до мети (випадок, коли в критичній точці). У подібних, і в більш складних випадках застосовують різні наближені аналітичні методи, які в математичному сенсі іноді менш строго обгрунтовані, але, тим щонайменше часом призводять до бажаного результату. До таких методів належать і градієнтні методи найшвидшого спуску.
Нехай, нам потрібно знайти. Розглянемо деяку точку і обчислимо в цій точці градієнт функції:
(14)
де - ортонормованій базис в просторі. Якщо, то вважаємо:
(15)
де, а вибирається з умови збіжності ітераційного процесу:
(16)
де, а вибираються з умови збіжності. Формулу (16) можна розписати у вигляді:
перший наближення; (17)
другий наближення; (18)
.............................
m-те наближення; (19)
Тут m - число ітерацій. Процес ітерації зупиняється, коли досягається необхідна гранична похибка, тобто коли виконані умови зупинки ітерації:
(20)
Приклад 6: Знайти мінімум функції
Рішення: візьмемо початкову точку. З (14) маємо:
(21)
...
