Минимизация по правильному симплексу

Определение:

Правильным симплексом в пространстве Еn называется множество из n+1 равноудаленных друг от друга точек (вершин симплекса).

Отрезок соединяющих две вершины, называются ребром симплекса.

Например: в пространстве Еправильным симплексом является совокупность вершин равностороннего треугольника.

Если Х- одна из вершин правильного симплекса в Еn, то координаты остальных n вершин X,…,Xможно найти по формулам:

Х= (2)

где d=a(-1)/n, d=a(+n-1)/n, а-длина ребра

Определение:

Вершину Хсимплекса, построенного по формулам (1), будем называть базовой.

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

=x, где x=

В результате получается новый правильный симплекс с тем же ребром и вершинами

X^=2 x-x, x, i=0,…,n, i≠k

Таким образом происходит перемещение симплекса в пространстве Еn.

Изобразим на рисунке пример построения нового симплекса в Еотражением точки X:

а) начальный симплекс Х, Х, Х;

б) новый симплекс Х, Х, X^;

центр отражения – точка Х=(Х+Х)/2

Поиск точки min-ма функции f(x) с помощью правильных симплексов производится следующим образом.

На каждой итерации сравниваются значения f(x) в вершинах симплекса. Затем производится процедура отражения той вершины, в которой f(x) принимает max-ое значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину Хстарого симплекса, в которой функция принимает min-ое значение. Поиск точки min-ма f(x) заканчивают, когда, либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становится достаточно малыми.

Один из вариантов алгоритма этого метода:

ШАГ 0:

Выбрать параметр точности , базовую точку Х, ребро а и построить начальный симплекс по формулам (1). Вычислить f(Х).

ШАГ1:

Вычислить значение f(x) в вершинах симплекса X,…,X.

ШАГ2:

Упорядочить вершины симплекса X,…,Xтак, чтобы f(Х)f(X)…f(X)f(X)

ШАГ3:

Проверить условие

(2)

Если оно выполняется, то вычисления прекратить, полагая Х*≈Х, f*≈f(Х). В противном случае перейти к шагу 4.

ШАГ4:

Найти x=и выполнить отражение вершины х:

х^=2 x-х. Если f(х^)<f(х), то положить х= х^ и перейти к шагу2. Иначе перейти к шагу5.

ШАГ5:

Найти x=и выполнить отражение вершины х

х^=2 x-х. Если f(х^)<f(х), то положить х= х^ и перейти к шагу 2. Иначе перейти к шагу 6.

ШАГ6:

Перейти к новому правильному симплексу с вдвое меньшим ребром,считая базовой вершиной х. Остальные n-вершин симплекса найти по формуле х=(х+х)/2, i=1,…,n

Перейти к шагу 1.

Замечания:

1. Следует иметь в виду, что если функция f(x) многомодальна, то описательным методом может быть найдена точка локального, а не глобального min-ма f(x).

2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.

Дата добавления: 2014-01-07