Метод Хука — Дживса ( англ. Hooke — Jeeves, Pattern search ), также известный как метод конфигураций — как и алгоритм Нелдера — Мида , служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две фазы: исследующий поиск и поиск по образцу.

На начальном этапе задаётся стартовая точка (обозначим её 1) и шаги h _i по координатам. Затем замораживаем значения всех координат кроме 1-й, вычисляем значения функции в точках x ₀ +h ₀ и x ₀ -h ₀ (где x ₀ — первая координата точки, а h ₀ — соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x ₁ +h ₁ и x ₁ -h ₁ , переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам h _i станут меньше соответствующих значений e _i , алгоритм завершается, и точка 1 признаётся точкой минимума.

Иллюстрация первого этапа для двух координат:

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

На этапе поиска по образцу откладывается точка 3 в направлении от 1 к 2 на том же расстоянии. Её координаты получаются по формуле ${\displaystyle {\overline {x}}_{3}={\overline {x}}_{1}+\lambda ({\overline {x}}_{2}-{\overline {x}}_{1})}$ , где x _i — точка с номером i, λ — параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе в результате исследующего поиска удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма — исследующий поиск.

Иллюстрация второго этапа для двух координат:

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

Литература

1. Р. Хук , Т. А. Дживс «Прямой поиск решения для числовых и статических проблем», 212—219 с., 1961.
2. C. T. Kelley. Iterative methods for optimization, 180 p

Ссылки

• в Интуит.ру .
• А.В. Аттетков, С.В. Галкин, В.С. Зарубин. Метод Хука - Дживса // . — М. : Изд-во МГТУ им. Н.Э. Баумана, 2003. — С. 285. — 440 с. — (Математика в техническом университете; Вып. XIV). (недоступная ссылка)

Для улучшения этой статьи по математике желательно : Оформить статью по правилам . Исправить статью согласно стилистическим правилам Википедии . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.