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

Определение 3.7. Правильным симплексом в пространстве E _n на­зывается множество из п + 1 равноудаленных друг от друга точек (вер­шин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.

В пространстве E ₂ правильным симплексом является совокупность вершин равностороннего треугольника, в E ₃ — правильного тетраэдра.

Если х⁰ — одна из вершин правильного симплекса в E _n то координаты остальных п вершин х¹,..,х ⁿ можно найти, например, по формулам:

(3.37)

где d ₁ , d ₂ , a— длина ребра. Вершину х⁰ симплекса, построенного по формулам (3.37), бу­дем называть бaзовой.

В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой-либо вершины, например, х ^k симметрично относительно центра тяжести х ^c остальных вершин симплекса. Новая и старая вершины и х ^k связаны соотношением: , где x ^c . В результате получается новый правильный симплекс с тем же ребром и верши­нами = 2x ^c - х ^k, х ⁱ, i = 0,.., n, i¹ k. Таким образом, происходит перемещение симплекса в пространстве Е _n. На рис. 3.3 представле­на иллюстрация этого свойства симплекса в пространстве Е ₂.

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

Шаг 0. Выбрать параметр точности e, базовую точку х⁰, ребро a и построить начальный симплекс по формулам (3.37). Вычислить f (х⁰).

Шаг 1. Вычислить значения f(х) в вершинах симплекса х¹,.., x ⁿ.

Шаг 2. Упорядочить вершины симплекса х⁰,.., х ⁿ так, что бы f (х⁰) £ …£ £ f (х¹) £ f (х ^{n -1}) £ f (х ⁿ).

Шаг 3. Проверить условие

(3.38)

Если оно выполнено, то вычисления прекратить, полагая х^*» х⁰, f^*» f(x⁰).

В противном случае перейти к шагу 4.

Шаг 4. Найти и выполнить отражение вершины х ⁿ:

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

Шаг 5. Найти и выполнить отражение вершины х ^{n- 1}: = 2x ^c - х ^{n- 1}. Если f() < f(х ^{n- 1}), то положить х ^{n- 1} = и перейти к шагу 2. Иначе — перейти к шагу 6.

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

Геометрическая иллюстрация работы алгоритма в пространстве показана на рис. 3.4, где точки х ⁰, х ¹, х ² — вершины начального симплекса, а пунктиром указаны процедуры отражения.

Замечания:

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

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