Поиск по правильному симплексу
Поиск минимума целевой функции f(x) по данному методу основан на выборе в качестве пробных точек вершин правильного симплекса. Напомним, что правильным симплексом в En называется множество из n+1 равноудаленных друг от друга точек - вершин симплекса. Так, в E2 правильным симплексом является равносторонний треугольник, в E3 – тетраэдр.
Из аналитической геометрии известно, что если X0– одна из вершин правильного симплекса в En, то координаты остальных вершин X1,…, Xn находятся по формулам
(2.4) где d1= 
, d2= 
, t - длина ребра.
По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины симметрично относительно центра тяжести Xс остальных вершин симплекса. Новая и старая вершины 
k и Xk связаны соотношением
= 
, = 
. (2.5)
В результате получается новый правильный симплекс с тем же ребром и вершинами
k=2 Xс - Xk, Xj , j=0,…,n, j¹k.
На рис.1 представлена иллюстрация описанной операции отражения в пространстве E2.
Рис. 1. Построение нового симплекса в Е2 отражением точки X2:
а - начальный симплекс X0, X1, X2; б - новый симплекс X0, X1, 
;
центр отражения - точка Xс=( X0+X1)/2.
На каждой итерации поиска сравниваются значения функции f(x) в вершинах симплекса и выполняется описанная процедура отражения для той вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Иначе выполняют ещё одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра и строят новый симплекс с этим ребром. При этом в качестве базовой выбирают ту вершину X0 старого симплекса, в которой функция принимает наименьшее значение. Поиск точки минимума X* заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг 0. Задать параметр точности e, выбрать базовую точку X0 и длину ребра t, построить по формулам (2.4) начальный симплекс и вычислить f(X0).
Шаг 1. Вычислить значения функции f(X) в вершинах симплекса X1,…, Xn.
Шаг 2. Упорядочить вершины симплекса X0,…,Хn так,чтобыf(X0)£…£f(Xn).
Шаг 3. Проверить условие достижения точности
Если оно выполняется, то перейти к шагу 7, иначе – к шагу 4.
Шаг 4. Найти по формуле (4) центр тяжести Xc вершин X0,X1,…,Xn-1и выполнить отражение вершины Xn: 
n=2Xc - Xn.Если f( n) < f(Xn), то положить Xn= n и перейти к шагу 2, иначе – к шагу 5.
Шаг 5. Найти центр тяжести Xc вершин X0,X1,…,Xn-1,Xn и выполнить отражение вершины Xn-1: n-1 =2Xc - Xn-1.Если f( n-1)<f(Xn-1), то положить Xn-1= n-1 и перейти к шагу 2, иначе – к шагу 6
Шаг 6. Построить новый правильный симплекс с вдвое меньшим ребром, считая базовой вершину X0, а остальные n вершин находя по формуле Xj=(Xj+ X0)/2, j=1,…,n и перейти к шагу 1.
Шаг 7. Завершить вычисления, положив X*= X0, f *= f(X0).