Функции нескольких переменных

Поиск по образцу.

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

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

-   текущая базовая точка,

- предыдущая базовая  точка,

-  точка, построенная при движении по образцу,

- следующая (новая)  базовая точка.

Приведенная последовательность характеризует логическую структуру поиска по методу Хука — Дживса.

Структура метода поиска Хука — Дживса

Шаг  1 . Определить:

начальную точку  ,

приращения

коэффициент уменьшения шага ,

параметр окончания  поиска .

Ш а г 2.  ровести исследующий поиск.

Ш а г 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением  

целевой функции)?

Да: перейти к шагу 5.

Нет: продолжать.

Ш а г 4. Проверка на окончание поиска.

Выполняется ли неравенство ?

Да: прекратить поиск; текущая точка аппроксимирует точку  оптимума.

Нет: уменьшить приращения по формуле

Перейти к шагу 2.

Ш а г 5. Провести поиск по образцу:

Шаг 6. Провести исследующий  поиск, используя  в качестве базовой точки;

пусть  полученная в результате точка.

Ш а г 7. Выполняется  ли  неравенство ?

Да: положить  Перейти к шагу 5.

Нет: перейти к  шагу 4. 

Пример 6  Поиск по методу Хука — Дживса

Найти точку минимума функции   используя начальную точку .

Решение.

Для того чтобы применить  метод прямого поиска .Хука — Дживса,  необходимо задать следующие величины:  

векторная величина приращения = , 

 коэффициент уменьшения  шага = 2, 

параметр окончания  поиска = 10^-4.

Итерации начинаются с исследующего поиска вокруг точки , которой соответствует значение функции Фиксируя, дадим приращение переменной :

Успех.

Следовательно, необходимо зафиксировать  и дать приращение переменной :  

Успех.

Таким образом, в  результате исследующего поиска найдена  точка

Поскольку исследующий  поиск был удачным, переходим  к поиску по образцу:

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

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

 Из примера  следует, что метод Хука — Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования метода поиска по симплексу.