Методы прямого поиска

J

I

X

Y

X

2. Идет построение в плоскости х₁ и х₂. Берут точку – определяющую значение аргумента. Находят точку в которой функция имеет тоже самое значение, в результате получаем линию в которой функция имеет постоянное значение – изолиния (линия уровня).

х2 х2 х1 х1 - изолиния

z изолиния

Вектор grad составляет прямой угол с изолинией.

Вернемся к формуле:

Квадратичная аппроксимация.

(или квадратичное приращение)

Линейное отображение:

- линейное отображение, если:

1. свойство аддитивности - ;

2. свойство однородности -

Линейное отображение можно задать матрицей:

т

; ;

п - основная формула

1

отображение

2 задачи:

- решение системы уравнений

и обратное отображение – найти х

А^-1 – обратное отображение;

следовательно строки матрицы ортогональны столбцам

другой матрицы

- нахождение собственных значений

Используя матрицу можно найти более сложную функцию: - квадратичная форма.

- функция нескольких переменных .

Рассмотрим подробнее.

Есть матрица:

- квадратичная форма

А и А^/ определяют одну и ту же квадратичную форму следовательно значения этой формы не однозначно. Если по заданной квадратичной форме найдем симметрию, то она будет однозначная.

;

;

Без ограничения общности можно считать, что матрица определяющая квадратичную форму является симметричной.

Вернемся к квадратичной форме:

Рассмотрим функцию 2-го порядка:

Допустим, что , матрица диагональная.

1.
Эллипсы	Эллиптический парабалоид
2.
3.
Гиперболы	Седло

Допустим, что . Тогда вся картина просто повернется на некоторый угол по оси Z.

Рассмотрим п -мерный случай.

Квадратичная форма называется положительно определенной областью если она не отрицательная.

1. , причем обращается в ноль, в том случае если х = 0 (). Этот случай соответствует эллиптическому параболоиду.
2. , .
3. Знаконеопределенность.

соответствует п -мерному эллиптическому гиперболоиду (п -мерное седло)

Рассмотрим 2-мерное пространство:

Если квадратная матрица называется положительно определенной, то и матрица положительно определенной.

Рассмотрим разложение функции 2-х переменных в ряд Тейлора:

квадратичная матрица задается матрицей Н

матрица составленная из членов 2-го порядка

- матрица симметрична

Матрица Н – матрица Гесса.

- определение матрицы Гесса

Если матрица (матрица Гесса) в точке локального экстремума положительно определена, то это точка – локального минимума, если матрица отрицательно определена, то это точка – локального максимума, а если не определена – седловые точки.

Локальный max или min

Седловая точка

Минимизируем:

Найти частные производные:

1. (grad = 0);

2.

Эта система позволяет найти все точки экстремума:

те х1 и х2 которые удовлетворяют уравнениям и будет точками экстремума.

Допустим, что . Надо составить функцию второго порядка и подставить и посмотреть их.

Необходимые условия – помогают охарактеризовать искомую точку:

1. grad f = 0
2. 

Н ³ 0 – локальный минимум;

Н £ 0 – локальный максимум;

Н – не определена – седловая точка.

Для поиска используют численные методы.

Постановка:

Требуется , где х – вектор - т.к. нет ограничений задача безусловной оптимизации.

Есть черный ящик, который по заданным значениям х позволяет вычислить значение функции.

Должны задать начальное приближение точки х0; - некоторое приближение полученное после к – итераций; вычислить значение точки в окрестности точки ; Из данных точек выбрать точку в которой функция принимает наименьшее значение, выбираем ее и строим вокруг нее окрестность.

Выбираем точку где хуже. В окрестности существующей точки выбираем точку с меньшим значением, опять в ее окрестности есть точки с меньшим значением и т.д.

В таком виде этот метод не эффективен.

Пример:

Шаг по х1 берем больше, а по х2 – сохраняем. Поскольку мы свободны в выборе точек, то можно менять шаг и направление.

Методы:

1. Хука-Дживса;
2. Нелдера-Мида (используется п-1 угольник)

Преимущества метода прямого поиска:

1. простота;
2. не нужны производные.

Недостатки:

1. плохая сходимость;
2. применим для небольшого числа переменных.

п £ 10¸20
	2п точек: в случае 2-х переменных – 4 точки; в случае 3-х переменных – 6 точек.

Этот метод применим в простых случаях, когда эти недостатки себя не проявляют.