Методы прямого поиска.( Квадратичная аппроксимация (или квадратичное приращение) Метод координатного спуска)

Задачи безусловной гладкой оптимизации

Необходимое и достаточное условие оптимальности.

Методы прямого поиска.(Квадратичная аппроксимация (или квадратичное приращение) Метод координатного спуска).

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

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

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

Пример:

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

Методы:

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

 

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

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

 

Недостатки:

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

 

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

 

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