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

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b₁ и шаг длиной h_j для каждой переменной x_j, j = 1, 2,..., n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f(x) в базисной точке b₁ с целью получения сведений о локальном поведении функции f(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b₁ находится следующим образом:

1. Вычисляется значение функции f(b₁) в базисной точке b₁.

2. Каждая переменная по очереди изменяется прибавлением длины шага.

Таким образом, мы вычисляем значение функции f(b₁ + h₁e₁), где e₁ - единичный вектор в направлении оси х₁. Если это приводит к уменьшению значения функции, то b₁ заменяется на b₁ + h₁e₁. В противном случае вычисляется значение функции f(b₁ – h₁e₁), и если ее значение уменьшилось, то b₁ заменяем на b₁-h₁e₁. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b₁ остается неизменной и рассматриваются изменения в направлении оси х₂, т.е. находится значение функции f(b₁ + h₂e₂) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b₂.

3. Если b₂ = b₁, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b₁, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если , то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

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

(5)

В общем случае

(6)

2. Затем исследование следует продолжать вокруг точки P₁ (P_j).

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b₂ (в общем случае b_j+1), то получают новую базисную точку b₃ (b_j+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b₂ (b_j+1) а продолжить исследования в точке b₂ (b_j+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Ниже приведена блок-схема данного метода.

Рис. 2.

Рис. 3.