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

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

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) получаем итерационную

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать