Метод поиска по симплексу

Метод основан на том, что экспериментальным образцом, содержащим наименьшее количество точек, является симплекс.

Регулярный симплекс в N-мерном пространстве – это многогранник, образованный N+1 равноотстоящими точками – вершинами симплекса.

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

Пример для двухмерного случая. (рисунок)

в точке x⁽¹⁾ наихудшее значение функции; в точке x_c центр тяжести.

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

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

· Если некоторая вершина симплекса не исключается более, чем на N итерациях, то уменьшить размеры симплекса с помощью некоторого коэффициента и построить новый симплекс, используя в качестве базовой точку с наименьшим значением функции. Количество итераций не исключения вершины: M=1,65ЧN+0,05ЧN².

· Поиск заканчивается, когда размеры симплекса и разности значений функции в вершинах станут достаточно малы.