Использование метода оврагов для поиска экстремумов функции

Овражная ситуация создается потому, что в практике встречается большое количество задач, в которых независимые переменные по-разному существенно влияют на поведение функции цели и потому имеет смысл по-разному строить поиск вдоль этих переменных.

Разобьем переменные функции на две группы. К первой группе отнесем переменные, незначительное варьирование которыми приводит к значительным изменениям функции цели. Частные производные для этой группы переменных велики по модулю. Будем считать, что они удовлетворяют условию

Переменные этой группы будем называть несущественными, подразумевая под этим простоту организации поиска вдоль этих переменных. К существенным переменным отнесем те, для которых

при . Организовать поиск вдоль этих переменных существенно сложно. Функцию цели (здесь ), оптимизируемые переменныe которой хорошо разбиваются на такие группы, называют хорошо организованной функцией. В противном случае функцию следует считать плохо организованной.

Например, функцию следует считать хорошо организованной, так как ее переменные четко подразделяются на две группы: несущественные и существенные переменные. В противоположность этому функция - плохо организована, потому что ее переменные не допускают четкого деления на сущесвтенные и несущественные. Как правило, хорошо организованная функция имеет «овраги». Однако, в общем случае, плохо организованная функция тоже может иметь «овраги».

При минимизации функции по методу оврагов поступаем следующим образом.

Выбираем случайным образом точки и ) (считаем, что точки находятся на склоне «оврага»);

Находим точку , расположенную близко к дну «оврага». Для этого, например, можно, взяв стартовую точку , применить одну итерацию алгоритма, описанного в лабораторной работе №1.

Аналогично, взяв стартовую точку , находим точку , также расположенную на дне «оврага».

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

Вычисляем

Точка находится на склоне «оврага»,

.

К величине «овражного» шага предъявляются следующие требования:

a) чем круче поворот, тем меньше шаг;

b) чем прямолинейнее дно, тем больше должен быть шаг;

c) в любом случае следует придерживаться дна «оврага».

Таким образом, формула нахождения следующей точки на склоне «оврага» выглядит следующим образом:

,

где согласно стратегии Гельфанда-Цетлина: , С >1, - угол между векторами и , С – параметр чувствительности к кривизне дна «оврага»;

,

где- скалярное произведение векторов и ;

- произведение по модулю векторов и .

В формуле для h_k+1 распишем h_k через h_k-1 (по той же формуле), h_k-1 через h_k-2, и т.д _.:

.

Пусть. Таким образом, .

выбирают произвольно. Например, =.

Если в процессе поиска возникнет ситуация , то следует начать поиск из точки с меньшим шагом.

Останов в овражной ситуации выполняется при .