Правильный симплекс в пространстве En называется
множество из n+1 равноудаленных друг от друга точек (вершин симплекса). В
пространстве Е2 правильным симплексом является совокупность вершин
равностороннего треугольника, Е3 – правильного тетраэдра.
Поиск точки минимума функции f(x) с помощью правильных
симплексов производят следующим образом. На каждой итерации сравниваются значения
f(x) в вершинах симплекса. Затем проводят описанную выше процедуру отражения
для этой вершины, в которой f(x) принимает наибольшее значение. Если в
отраженной вершине получается меньшее значение функции, то переходят к новому симплексу.
В противном случае выполняют еще одну попытку отражения для вершины со
следующим по величине значением f(x). Если и она не приводит к уменьшению
функции, то сокращают длину ребра симплекса и строят новый симплекс с новым
ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, которой
функция принимает наименьшее значение. Поиск минимума f(x) заканчивают, когда
либо ребро симплекса, либо разность между значениями функции в вершинах
симплекса становятся достаточно малыми.
Начальный этап. Выбрать параметр точности eps, базовую
точку x0, ребро a и построить начальный симплекс. Вычислить f(x0).
Основной этап.
Шаг 1. Вычислить значения f(x) в вершинах симплекса
x1,..., xn.
Шаг 2. Упорядочить вершины симплекса x0,..., xn так,
чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).
Шаг 3. Проверим на окончание поиска
,
где
Это одно из возможных условий останова. Его выполнении
соответствует либо малому ребру a симплекса, либо попаданию точки минимума x*
внутрь симплекса, либо тому и другому одновременно.
Если это условие выполнено, то вычисления прекратить,
полагая x*= x0. В противном случае перейти к шагу 4.
Шаг 4. Найти xс и выполнить отражение вершины xn :
y=2*xс- xn. Если f(y)<f(xn), то положить xn=y и перейти к шагу 2. Иначе -
перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвое
меньшим ребром, считая базовой вершиной x0. Остальные n вершин симплекса найти
по формуле xi=( xi+ x0)/2, i=1,...,n. Перейти к шагу 1.
Для решения поставленной задачи выбрано приближение
ε=0,01, α=0,3
Таблица 5 - Метод симплекса
№ шага
Z(x0,y0)
Z(x1,y1)
Z(x2,y2)
α
1
5,2755004
7,4172004
5,62549807735416
0,3
2
5,2755004
5,62549807735416
3,76366398915256
0,3
3
3,76366398915256
5,2755004
3,5838004
0,3
4
3,5838004
3,76366398915256
2,35182990095096
0,3
5
2,35182990095096
3,5838004
2,3421004
0,3
6
2,3421004
2,35182990095096
1,38999581274936
0,3
7
1,38999581274936
2,3421004
1,5504004
0,3
8
1,38999581274936
1,5504004
0,878161724547756
0,3
9
0,878161724547756
1,38999581274936
0,657100646520204
0,3
10
0,657100646520204
0,878161724547756
0,425132470117002
0,3
11
0,425132470117002
0,657100646520204
0,143414901312537
0,3
12
0,143414901312537
0,425132470117002
0,191312636707734
0,3
13
0,143414901312537
0,191312636707734
-0,15106142287364
0,3
14
-0,15106142287364
0,143414901312537
-0,0288250700672363
0,3
15
-0,15106142287364
-0,0288250700672363
-0,383957885030324
0,3
16
-0,383957885030324
-0,15106142287364
-0,226328326038328
0,3
17
-0,383957885030324
-0,226328326038328
-0,519881278971922
0,3
18
-0,519881278971922
-0,383957885030324
-0,507376749762318
0,3
19
-0,519881278971922
-0,507376749762318
-0,703956634480828
0,3
20
-0,703956634480828
-0,521318017069623
-0,507376749762318
0,3
21
-0,703956634480828
-0,521318017069623
-0,778554392565042
0,3
22
-0,778554392565042
-0,703956634480828
-0,681327098177849
0,3
23
-0,778554392565042
-0,816581347038974
-0,681327098177849
0,3
24
-0,816581347038974
-0,778554392565042
-0,743674553224567
0,3
25
-0,816581347038974
-0,842357998475409
-0,743674553224567
0,3
26
-0,845848412956476
-0,846177360374865
-0,838238020383463
0,075
27
-0,846177360374865
-0,845848412956476
-0,843154372435278
0,075
28
-0,846616455690446
-0,845848412956476
-0,843154372435278
0,075
29
-0,848017017695877
-0,847087728053341
-0,846597987664592
0,0375
30
-0,848017017695877
-0,847980516275042
-0,847811621576176
0,01875
31
-0,848017017695877
-0,848085062414109
-0,847811621576176
0,01875
Т.к дальнейшее уменьшение α невозможно(α/2<
ε) и в ε окрестности полученной на 31 шаге точке мы не получаем
улучшения (уменьшения значения) функции, то примем x=0,248249999999998 и
y=0,408289729858682 Z(x,y)= -0,847811621576176.
2.4 Метод деформированного симплекса
Алгоритм минимизации по правильному симплексу можно
модифицировать, добавив к процедуре отражения при построении нового симплекса
процедуры сжатия и растяжения. А именно, положение новой вершины y вместо
вершины xn , соответствующей наибольшему значению функции, находится сравнением
и выбором наименьшего среди значений целевой функции в точках:
z1= xc - a( xc - xn), 0<a<1;
z2 = xc +
a( xc - xn),
0<a<1;
z3 = xc + b( xc - xn), b приближенно равно 1;
z4 = xc + g( xc - xn), g<1.
Геометрическая иллюстрация этих процедур для двумерного
пространства приведена на рисунке 7.
Новые симплексы полученные в результате процедуры сжатия
(a,b); отражения (c); растяжения (d)
Так как величина a принадлежит интервалу (0;1), то выбор
точек z1 и z2 соответствует сжатию симплекса; b приближенно равно 1, поэтому
выбор точки z3 соответствует отражению, а g>1 и выбор точки z4 приводит к растяжению
симплекса.
Отметим, что при деформациях утрачивается свойство
правильности исходного симплекса.
Алгоритм метода поиска точки минимума функции по
деформируемому симплексу
Начальный этап. Выбрать параметр точности eps, параметры
a, b и g, базовую точку x0 , параметр a и построить начальный симплекс.
Вычислить значение функции f(x0).
Основной этап. Шаг 1. Вычислить значения функции в
вершинах симплекса x1,..., xn.
Шаг 2. Упорядочить вершины симплекса x0,..., xn так,
чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).
Это одно из возможных условий останова. При его
выполнении "дисперсия" значений f(x) в вершинах симплекса становится
меньше e2, что, как правило, соответствует либо малому ребру a симплекса, либо
попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.Если
это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном
случае перейти к шагу 4.
Шаг 4. Найти xс и пробные точки zk , k=1,...,4 по
формулам (2). Найти f(z*)=minf(zk). Если f(z*)<f(xn),
то положить xn = z* и перейти к шагу 2. Иначе - перейти к шагу 5.
Шаг 5. Уменьшить симплекс, полагая xi=( xi+ x0)/2,
i=1,...,n перейти к шагу 1.
На практике хорошо зарекомендовал себя следующий набор
параметров a=1/2, b=1, g=2, поэтому он и был использован в программе.