Минимизацияфункции многих переменных. Приближённые численные методы. Метод Монте-Карло
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)