Овражный метод
1
Особые трудности при отыскании экстремума (min/max) функции возникают в случаях, когда характер функции «овражный» или «хребтовый».
Если использовать просто градиентный метод, то в этом случае точки будут находиться поочередно то с одной, то с другой стороны "оврага", а если «берега оврага» достаточно круты, то продвижение к точке экстремума будет очень медленным, в этом случае задача заключается в том, чтобы найти направление поиска вдоль «дна оврага».
2
Пусть и произвольные достаточно близкие точки на «склоне оврага». Из них спустимся на «дно оврага» методом наискорейшего спуска. Полученные точки и , лежащие в окрестности «дна оврага», определят направление
большого шага d («овражный шаг») вдоль «дна оврага». Например, при поиске минимума при «шагаем» в сторону точки
В результате получаем точку , в окрестности которой выберем точку и процедура повторяется.
3
Блок-схема овражного метода
1.Находим градиент заданной функции.
2.Выберем начальную точку и вычислим .
3.Используя метод наискорейшего спуска, получаем точку .
4.Выберем другую начальную точку и вычислим .
5.Используя метод наискорейшего спуска, получаем точку .
6.Вычисляем значение функции в полученных точках и . Пусть .
4
7. Делаем «овражный шаг» в |
сторону |
убывания функции: |
|
Если уменьшаем шаг d вдвое, если процесс продолжается.
Т.о. основная формула блок-схемы для нахождения минимума функции:
,
где
5
Задача 1
Найти минимум функции
Решение:
1.Найдем градиент:
2.Выберем начальную точку В этой точке
и
3.
Тогда
6
Решая уравнение , имеем:
29;
.
4. Выбираем за начальную точку .
и
и
7
Следовательно
Т.к. , то сделаем «овражный шаг» в сторону точки
.
8
Из условий экстремума функции
находим:
d = 1.019;
Так как и ), то процесс продолжаем.
9
6.Выбираем точку близкую к точке
иповторим п.3 для точек и:
10