Методы безусловной многомерной оптимизации. Шипилов С.А. - 8 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

Составители: 

Рубрика: 

8
В общем случае координаты вершин симплекса определяются матрицей:
)1(2
1
+⋅
=
ii
R
i
;
)1(2 +
=
i
i
V
i
.
В первом и во втором случаях формулы получены для симплекса, длина
ребра которого равна единице. Для произвольной длины каждую формулу
нужно умножить на длину ребра. Если поиск осуществляется не из начала
координат, а из начальной точки
x
(0)
, то к координатам вершин симплекса
необходимо добавить координаты начальной точки- x
1
(0)
и x
2
(0)
.
В вершинах исходного симплекса рассчитывается значение целевой
функции f(
x
(1)
), f(x
(2)
), f(x
(3)
). Из этих трех значений выбирается "наихудшая"
точка (при поиске минимума это та точка, в которой функция принимает мак-
симальное значение). Допустим, что это точка
x
(1)
. Через центр тяжести проти-
волежащей грани
x
ц.т.
=(x
(2)
+ x
(3)
)/2 строится новая вершина симплекса x
(4)
, сим-
метричная "наихудшей" вершине
x
(1)
(рис.1). Координаты новой вершины x
(4)
рассчитываются по формуле:
x
(4)
= x
ц.т.
+ (x
ц.т.
- x
(1)
)= x
(2)
+ x
(3)
- x
(1)
В результате получается новый симплекс
x
(2)
- x
(3)
- x
(4)
, причем значение
целевой функции в двух точках
x
(2)
и x
(3)
уже известно. Поэтому вычисляется
значение функции в точке
x
(4)
и среди всех вершин ищется вершина с "наихуд-
шим" значением. Эта вершина вновь отображается через середину противоле-
жащей грани и вся процедура повторяется. Признаком окончания поиска явля-
ется так называемая процедура зацикливания, когда вновь отображенная вер-
шина оказывается "наихудшей". В этом случае, если заданная точность не дос-
тигается, (точность определяется
длиной ребра симплекса) необходимо умень-
шить размеры симплекса. Процедура повторяется до тех пор, пока длина ребра
симплекса не станет меньше заданной точности.
В общем n – мерном случае, если обозначить отображаемую вершину
симплекса за
x
(1)
, остальные вершины - x
(2)
, x
(3)
, x
(n+1)
, отображенную вершину
за
x
(n+2)
, координаты центра тяжести грани, относительно которой производится
отображение, определяются по формуле:
()
∑
+
=
=
1
2
1
n
i
i
n
xx
ц.т.
, а отображаемой вершины
()
(
)
)1(
ц.т.ц.т.
2
xxxx −+=
+
α
n
. (4.1)
Здесь множитель
α
> 0 . При
α
=1 получаем зеркальное отображение x
(1)
и если
исходный симплекс был правильным, то при зеркальном отображении и новый
симплекс окажется правильным.
№ вершины x
1
x
2
x
3
…
x
n
1 -R
1
-R
2
-R
3
… -R
n
2 V
1
-R
2
-R
3
… -R
n
3 0
V
2
-R
3
… -R
n
4 0 0 V
3
-R
n
… … … … … …
n+1 0 0 0 …
V
n
                                                        8
      В общем случае координаты вершин симплекса определяются матрицей:
    № вершины         x1       x2      x3    …      xn                   1
         1           -R1      -R2     -R3    …     -Rn        Ri =                ;
         2            V1      -R2     -R3    …     -Rn              2 ⋅ i (i + 1)
         3            0        V2     -R3    …     -Rn                  i
                                                             Vi =                   .
         4            0         0      V3          -Rn             2(i + 1)
         …           …         …      …      …     …
        n+1           0         0      0     …      Vn
      В первом и во втором случаях формулы получены для симплекса, длина
ребра которого равна единице. Для произвольной длины каждую формулу
нужно умножить на длину ребра. Если поиск осуществляется не из начала
координат, а из начальной точки x(0), то к координатам вершин симплекса
необходимо добавить координаты начальной точки- x1(0) и x2(0).
      В вершинах исходного симплекса рассчитывается значение целевой
функции f(x(1)), f(x(2)), f(x(3)). Из этих трех значений выбирается "наихудшая"
точка (при поиске минимума это та точка, в которой функция принимает мак-
симальное значение). Допустим, что это точка x(1). Через центр тяжести проти-
волежащей грани xц.т.=(x(2) + x(3))/2 строится новая вершина симплекса x(4), сим-
метричная "наихудшей" вершине x(1) (рис.1). Координаты новой вершины x(4)
рассчитываются по формуле:
                              x(4)= xц.т.+ (xц.т.- x(1))= x(2) + x(3) - x(1)
       В результате получается новый симплекс x(2) - x(3) - x(4), причем значение
целевой функции в двух точках x(2) и x(3) уже известно. Поэтому вычисляется
значение функции в точке x(4) и среди всех вершин ищется вершина с "наихуд-
шим" значением. Эта вершина вновь отображается через середину противоле-
жащей грани и вся процедура повторяется. Признаком окончания поиска явля-
ется так называемая процедура зацикливания, когда вновь отображенная вер-
шина оказывается "наихудшей". В этом случае, если заданная точность не дос-
тигается, (точность определяется длиной ребра симплекса) необходимо умень-
шить размеры симплекса. Процедура повторяется до тех пор, пока длина ребра
симплекса не станет меньше заданной точности.
       В общем n – мерном случае, если обозначить отображаемую вершину
симплекса за x(1), остальные вершины - x(2) , x(3) , x(n+1), отображенную вершину
за x(n+2) , координаты центра тяжести грани, относительно которой производится
отображение, определяются по формуле:
                        1 n+1
                x ц.т. = ∑ x (i ) , а отображаемой вершины
                        n i =2
                                    (             )
              x (n+ 2 ) = x ц.т. + α x ц.т. − x (1) .                         (4.1)
Здесь множитель α > 0 . При α =1 получаем зеркальное отображение x(1) и если
исходный симплекс был правильным, то при зеркальном отображении и новый
симплекс окажется правильным.

Страницы