Минимизация функции многих переменных Приближённые численные методы Метод Монте-Карло

Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло

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)