Лекция: Алгоритм Хука-Дживса

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

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

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

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

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

Шаг 2. Сделать пробный шаг, где ej — 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 *= x0. Иначе — положить и перейти к шагу 1.

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

.

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

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