3.2 Метод деформируемого многогранника
В
основу метода деформируемого многогранника
(метода Нелдера-Мида [J.A.Nelder, R.Mead]) положено
построение последовательности систем
точек
,
которые являются вершинами выпуклого
многогранника. Точки системы
на
итерации совпадают с точками системы
,
кроме
,
где точка
-
наихудшая в системе
,
т.е.
.
Точка
заменяется другой точкой по специальным
правилам, описанным ниже. В результате
многогранники деформируются в
зависимости от структуры линий уровня
целевой функции, вытягиваясь вдоль
длинных наклонных плоскостей, изменяя
направление в изогнутых впадинах и
сжимаясь в окрестности минимума.
Построение последовательности
многогранников заканчивается, когда
значения функции в вершинах текущего
многогранника отличаются от значения
функции в центре тяжести системы
не более чем на
.
Алгоритм:
Шаг
1. Задать
координаты вершин многогранника
;
параметры отражения
,
сжатия
,
растяжения
;
число
для остановки алгоритма. Положить
.
Шаг
2. Среди
вершин найти “наилучшую”
и “наихудшую”
,
соответствующие минимальному и
максимальному значениям функции:
;
,
а
также точку
,
в которой достигается второе по величине
после максимального значение функции
.
Шаг 3. Найти “центр тяжести” всех вершин многогранника за исключением наихудшей :
Шаг 4. Проверить условие окончания:
если
,
процесс поиска можно завершить и в
качестве приближенного решения взять
наилучшую точку текущего многогранника
;если
,
продолжать процесс.
Шаг
5. Выполнить
операцию отражения
наихудшей вершины через центр тяжести
(рисунок 3.3):
Рисунок 3.3
Шаг 6. Проверить выполнение условий:
если
,
выполнить операцию растяжения
(рисунок 3.4):
Рисунок 3.4
Найти вершины нового многогранника:
если
,
то вершина
заменяется на
(при
многогранник будет содержать вершины
,
,
).
Затем следует положить
и перейти к шагу 2;если
,
то вершина
заменяется на
(при
многогранник будет содержать вершины
,
,
).
Далее следует положить
и перейти к шагу 2;
если
,
то выполнить операцию сжатия
(рисунок
3.5):
Рисунок 3.5
Следует
заменить вершину
на
,
положить
и перейти к шагу 2 (при
многогранник будет содержать вершины
,
,
);
если
,
то вершина
заменить на
.
При этом следует положить
и перейти к шагу 2;если
,
выполнить операцию редукции (рисунок
3.6). Формируется новый многогранник с
уменьшенными вдвое сторонами и вершиной
:
.
Рисунок 3.6
При этом следует положить и перейти к шагу 2.
Замечание:
Нелдер и Мид
рекомендуют использовать параметры
,
,
;
Павиани -
,
,
;
Паркинсон и Хатчинсон -
,
,
.
Пример: Найти локальный минимум функции методом деформируемого многогранника:
Решение:
1.
Зададим вершины начального многогранника
(треугольник, так как n
= 2 ):
,
,
,
.
20.
Т.к.
то
.
30.
Найдем центр тяжести вершин
и
:
.
40.
Т.к.
,
процесс продолжается.
50. Выполним отражение:
60.
Т.к.
то вершина
заменяется на
.
Положим k
= k
+ 1. Переходим
к шагу 2.
21.
Имеем вершины
.
Т.к.
то
.
31. Найдем центр тяжести вершин и :
.
41.
Т.к.
,
процесс продолжается.
51. Выполним отражение:
61.
Т.к.
то выполним сжатие:
Заменим
вершину
на
.
Положим k
= k
+ 1 = 2 и перейдем
к шагу 2.
22.
Имеем вершины
.
Т.к.
то
.
32. Найдем центр тяжести вершин и :
.
42.
Т.к.
,
процесс продолжается.
52. Выполним отражение:
62.
Т.к.
то выполним редукцию:
.
Положим k = 3 и перейдем к шагу 2.
23.
Т.к.
то
.
33. Найдем центр тяжести вершин и :
.
43.
Т.к.
,
процесс продолжается.
53. Выполним отражение:
.
63.
Т.к.
то заменим
на
,
положим k = 4 и перейдем к шагу 2.
24.
Имеем вершины
.
Т.к.
то
.
34. Найдем центр тяжести вершин и :
.
44.
Т.к.
,
процесс продолжается.
54. Выполним отражение:
.
64.
Т.к.
то выполним растяжение:
.
Т.к.
то заменим
на
,
положим k
= 5 и перейдем
к шагу 2.
25.
Имеем вершины
.
Т.к.
то
.
35. Найдем центр тяжести вершин и :
.
45.
Т.к.
,
процесс продолжается.
55. Выполним отражение:
.
65.
Т.к.
то заменим
на
,
положим k
= 6 и перейдем
к шагу 2.
26.
Имеем вершины
.
Т.к.
то
.
36. Найдем центр тяжести вершин и :
.
46.
Т.к.
,
процесс продолжается.
56. Выполним отражение:
.
66.
Т.к.
то выполним редукцию:
.
Положим k = 7 и перейдем к шагу 2.
27.
Имеем вершины
.
Т.к.
то
.
37. Найдем центр тяжести вершин и :
.
46.
Т.к.
,
процесс завершается.
В
качестве приближенного решения выбирается
наилучшая точка
.