Метод Хука–Дживса

Назначение сервиса. Онлайн-калькулятор предназначен для нахождения минимума функции методом Хука-Дживса (см. пример). Решение оформляется в формате Word.
f(x1,x2) =
Метод отыскания минимума функции
Начиная из точки ( ; ).
Приращение Δx = (; ).
Точность ξ = . Шаг α = .
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.

Метод Хука-Дживса относятся к категории эвристических методов (методам прямого поиска). Методы прямого поиска используют не менее n независимых направлений, где n-размерность вектора.
Элементарным примером метода, реализующего процедуру рекурсивного перебора на множестве направлений поиска, является метод циклического изменения переменных - каждый раз меняется только одна переменная. Затем вдоль каждого из координатных направлений последовательно проводится поиск точки экстремума на основе методов одномерной минимизации. Однако, если линии уровня ЦФ имеют овражный характер, то процедура поиска становится неэффективной и даже может привести к отсутствию сходимости к точке локального extr, если изменение координатных направлений поиска осуществляется в циклическом порядке (показано Пауэллом).

Модифицированный метод Хука-Дживса позволяет существенно ускорить сходимость за счет того обстоятельства, что поиск периодически проводится в направлении di=xi-xi-1.
По существу процедура Хука–Дживса представляет собой комбинацию двух поисков:
а) исследующий поиск (для выявления характера локального поведения ЦФ и определения направления движения вдоль "овра­гов") с циклическим изменением переменных;
б) ускоряющий поиск по образцу с использованием определен­ных эвристических правил.

Исследующий поиск. Выбирается некоторая исходная точка x0. Задается величина шага ∆i, которая может быть различной для разных координатных направлений и изменяться в процессе поиска.
Если значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, то шаг поиска успешный. В противном случае из исходной точки делается шаг в противоположном направлении. После перебора всех n координат исследующий поиск завершается. Полученная точка называется базовой.

Поиск по образцу. Осуществляется шаг из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей ба­зовой. Новая точка образца определяется по формуле:
xpk+1=xk+(xk-xk-1).
Как только движение по образцу не приводит к уменьшению ЦФ, точка xpk+1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением ЦФ, чем в точке xk, то она рассматривается как новая базовая точка xk+1. Но если исследующий поиск неудачен, то следует вернуться в точку xk и провести исследующий поиск с целью выявления нового направления минимизации. В конечном итоге возникает ситуация, когда такой поиск не приводит к успеху. В этом случае уменьшается шаг путем введения коэффициента α и возобновляется исследующий поиск.
Если исследуемая функция имеет овражный вид, то предпочтительнее использовать метод Хука-Дживса, а не метод Нелдера-Мида, так как в первом методе мы можем регулировать шаг в направлении убывания функции, в то время как во втором методе мы этого сделать не можем.

Схема алгоритма Хука–Дживса

Введем следующие обозначения: xk - текущая базовая точка; xk-1 - предыдущая базовая точка; xpk+1 - точка, построенная при движе­нии по образцу; xk+1 - следующая (новая) базовая точка.
Критерий останова: |∆x|≤ε.
Шаг 1. Определить начальную точку x0; приращения (шаги) ∆i; коэффициент уменьшения шага α>1; параметр оконча­ния поиска ε<1.
Шаг 2. Провести исследующий поиск.
Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением ЦФ)?
Да: переход на Шаг 5. Нет: продолжить, т.е. переход на Шаг 4.
Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство |Δx| ≤ ε? Да: окончание поиска, т.е. текущая точка аппроксимирует точку экстремума x*.
Нет: уменьшить приращение ∆i/α; i=1,2,..,n. Переход на Шаг2.
Шаг 5. Провести поиск по образцу: xpk+1=xk+(xk-xk-1).
Шаг 6. Провести исследующий поиск, используя точку xpk+1 в каче­стве временной базовой точки. Пусть в результате получена точка xk+1.
Шаг 7. Выполняется ли неравенство: f(xk+1) < f(xk)?
Да: положить xk-1= xk; xk= xk+1. Переход на Шаг 5.
Нет: переход на Шаг 4.

Пример.

загрузка...