Алгоритм Хука-Дживса

Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенной для определения направления убывания f(x):

б) перемещение в направлении убывании (поиск по образцу).

Опишем алгоритм исследующего покоординатного поиска из заданной точки х с приращениями по каждой координате.

Шаг 1. Положить , j = 1.

Шаг 2. Сделать пробный шаг , где e^j — j-й базисный вектор. Если

, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Сделать пробный шаг . Если , то перейти к шагу 5,

иначе - к шагу 4.

Шаг 4. Положить

Шаг 5. Положить j = j+1. Если j n, то перейти к шагу 2. В противном случае исследующий поиск окончен - получена точка , для которой , если .

Замечание:

В результате исследующего поиска может оказаться, что . Тогда исследующий поиск считается неудачным. Если при этом норма приращения мала, т. е. , где - заданная точность, то полагают x* = x. Если заданная точность не достигнута, то полагают (постоянная >1 - коэффициент уменьшения шага) и повторяют исследующий поиск.

Приведем теперь полный алгоритм Хука-Дживса.

Шаг 0. Выбрать начальную точку x°, вектор приращений ,

коэффициент уменьшения шага > 1, параметр окончания поиска > 0.

Шаг 1. Провести исследующий покоординатный поиск из точки x0, т. е. найти точку

. Если , то перейти к шагу 3, иначе - к шагу 2.

Шаг 2. Проверка на окончание поиска. Если , то прекратить поиск и

положить x *= x⁰. Иначе - положить и перейти к шагу 1.

Шаг 3. Перемещение из точки в направлении убывания (): положить

.

Шаг 4. Провести исследующий поиск в точке х¹, т. е. найти следующую точку .

Если то положить x° = х¹, и перейти к шагу 3. Иначе -положить и перейти к шагу 1.