Алгоритм метода поиска точки минимума функции по деформируемому симплексу

Начальный этап. Выбрать параметр точности eps, параметры a, b и g, базовую точку x0, параметр a и построить начальный симплекс. Вычислить значение функции f(x0).

Основной этап.

Шаг 1. Вычислить значения функции в вершинах симплекса x1,..., xn.

Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)< =f(x1)< =...< =f(x[n-1])< =f(xn).

Шаг 3. Проверить условие (1/n)Sum[f(xi)-f(x0)]^2 < e^2, i=[1, n].

Это одно из возможных условий останова. При его выполнении " дисперсия" значений f(x) в вершинах симплекса становится меньше e2, что, как правило, соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.

Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.

Шаг 4. Найти xс и пробные точки zk, k=1,..., 4 по формулам (2). Найти f(z*)=minf(zk). Если f(z*)< f(xn), то положить xn = z* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая xi=(xi+ x0)/2, i=1,..., n перейти к шагу 1.

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

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

1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2. Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.