ВУЗ:
Составители:
73
алгебраических уравнений (4.5) с затратой примерно 6
/
3
n
арифметических операций. При больших n это неприемлемый объем
работы на одну итерацию.
К настоящему времени разработаны модификации метода Ньютона,
сохраняющие высокую скорость сходимости, но не требующие вычисле-
ний и обращений матрицы Гессе. Эта группа методов носит название
квазиньютоновских. Широко известен относящийся к указанной группе
метод Дэвидона–Флетчера–Пауэла. В нем, в отличие от алгоритма (4.7),
спуск на каждой итерации проводится в направлении )(
(k)
k
f xB ∇− , где
k
B –
положительно определенная симметричная матрица, которая обновляется
на каждом шаге и в пределе стремится к обратной матрице Гессе.
4.5. Симплексный метод Нелдера–Мида
Симплексом называется n-мерная геометрическая фигура, ребрами
которой являются прямые линии, пересекающиеся в n+1 вершине. В
двумерном пространстве симплексом является треугольник, в трехмерном
– тетраэдр. Прямые методы поиска, получившие свое название от этого
геометрического объекта, основаны на исследовании значений целевой
функции в вершинах симплекса и построении последовательности
симплексов с центрами, систематически смещающимися в направлении
точки минимума.
Из группы симплексных методов наиболее известен метод Нелдера–
Мида. Он считается одним из самых эффективных методов минимизации
функций при числе переменных 6≤n .
В методе Нелдера–Мида симплекс деформируется и перемещается в
пространстве с помощью трех операций: отражения, растяжения и
сжатия. Смысл этих операций поясним при рассмотрении шагов
алгоритма.
1. Находим значения целевой функции в вершинах симплекса:
)(...,),(),(
112211 ++
===
nn
ffffff xxx .
2. Среди вершин симплекса находим точку
L
X с наименьшим
значением функции
L
f , точку
G
X со значением
G
f , следующим за
наименьшим, и точку
H
X с наибольшим значением функции.
H
f . Точку
L
X назовем наилучшей, точку
G
X – хорошей, а точку
H
X – наихудшей
(см. рис. 4.5 а).
3. Определяем центр тяжести всех вершин симплекса, за исключением
наихудшей:
∑
≠
=
Hi
iM
n
xx
1
(4.8)
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
