Поиск по правильному симплексу

Поиск минимума целевой функции 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).