47732 (Нелинейное программирование), страница 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

Успех.

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

Успех.

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

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

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

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

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

Итерации поиска по методу Хука-Дживса на примере