Введение. 
Метод Хука-Дживса

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

В этой работе пойдет речь об одном из методов, так называемого, прямого поиска. Это — метод Хука-Дживса. Он применяется для определения минимума функций и переменных. Этот метод, созданный в середине двадцатого столетия применяется и сейчас, так как очень хорошо себя зарекомендовал.

Целю данной работы, является освещения концепций метода Хука-Дживса.

Основными задачами, подлежащими рассмотрению в связи с поставленной целью являются:

• — объяснить в чем состоит суть метода Хука-Дживса;
• — показать его отличие от других методов данного типа;
• — рассмотреть алгоритм работы метода;
• — пояснить этапы выполнения метода;
• — уточнить в чем состоит модификация данного метода;
• — наглядно продемонстрировать работу метода с помощью блок-схем.

Актуальность данной работы заключается в конкретизации и резюмированию знаний об этом методе.

хук дживс функция минимизирование.

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

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

Минимум лежит в точке (x₁^*, x₂^*). Простейшим методом поиска является метод покоординатного спуска. Из точки, А мы производим поиск минимума вдоль направления оси и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси. Затем, производя поиск из точки В направлении оси, получаем точку С, производя поиск параллельно оси, получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идею можно применить для функций n-переменных.

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

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

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

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

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

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

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

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

P₁=b₁+2(b₂-b₁).

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

P_i=b_i+2(b_i+1-b_i).

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

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