Метод деформируемого многогранника (Нелдера-Мида)

Содержание

Слайд 2

Задача

Найти минимум критерия оптимальности ,определенного в n-мерном евклидовом пространстве

Метод использует следующие операции над

Задача Найти минимум критерия оптимальности ,определенного в n-мерном евклидовом пространстве Метод использует
симплексами:
отражение;
редукция;
сжатие;
растяжение.

Слайд 3

Отражение вершин симплекса

Производится относительно центра тяжести остальных вершин.
Отражение k-й вершины с координатами:

Вектор

Отражение вершин симплекса Производится относительно центра тяжести остальных вершин. Отражение k-й вершины
координат центра тяжести остальных вершин симплекса:

Новый симплекс с координатами вершин:

Слайд 4

Редукция симплекса

Уменьшение длин всех ребер симплекса в одно и то же количество

Редукция симплекса Уменьшение длин всех ребер симплекса в одно и то же
раз.
Редукция вершин симплекса к вершине

Коэффициенты редукции равны:

Новый симплекс с координатами вершин:

Слайд 5

Сжатие симплекса

Сжатие симплекса в направлении

Новый симплекс с координатами вершин:

Коэффициенты сжатия:

Сжатие симплекса Сжатие симплекса в направлении Новый симплекс с координатами вершин: Коэффициенты сжатия:

Слайд 6

Растяжение симплекса

Сжатие симплекса в направлении

Новый симплекс с координатами вершин:

Коэффициенты растяжения:

Растяжение симплекса Сжатие симплекса в направлении Новый симплекс с координатами вершин: Коэффициенты растяжения:

Слайд 7

Схема метода Нелдера-Мида

обозначим за ; зададим начальную точку

Находим координаты и вычисляем значение

Схема метода Нелдера-Мида обозначим за ; зададим начальную точку Находим координаты и
функции во всех вершинах симплекса

Среди вершин симплекса найдем те, что принимают наименьшее, наибольшее и следующее за максимальным значение
Вычислим значение функции в них:

max

min

Слайд 8

Схема метода Нелдера-Мида

Выполняем отражение вершины симплекса , вычисляем , получили новый симплекс

Если

Схема метода Нелдера-Мида Выполняем отражение вершины симплекса , вычисляем , получили новый
и

Если но

Если

Растяжение симплекса в направлении
Получаем новую вершину
Если возвращаемся к вычислению 3х вершин симплекса и отражению.
Иначе - данные не используем.

Возвращаемся к вычислению 3х вершин симплекса и отражению.

Сжатие симплекса в направлении
Получаем новую вершину . Если
, , то возвращаемся к вычислению 3х вершин симплекса и отражению.
Иначе – выполняем редукцию к вершине

Слайд 9

Условие окончания итераций

- требуемая точность решения

Можно завершать итерации, когда длина максимального из

Условие окончания итераций - требуемая точность решения Можно завершать итерации, когда длина
ребер текущего симплекс станет меньше или равна требуемой точности решения  

Также можно завершить алгоритм, если выполнено необходимое количество итераций

Слайд 10

Успешное растяжение

Успешное отражение

Успешное сжатие

Использование редукции после неудачного сжатия

Успешное растяжение Успешное отражение Успешное сжатие Использование редукции после неудачного сжатия

Слайд 11

Пример

Найти экстремум следующей функции: F(x,y)=x2+xy+y2−6x−9y
Возьмем точки: V1(0, 0); F(V1) = 0 = b

Пример Найти экстремум следующей функции: F(x,y)=x2+xy+y2−6x−9y Возьмем точки: V1(0, 0); F(V1) =
;
V2(1, 0); F(V2) = -5 = g;
V3(0, 1); F(V3) = -8 = w.
Находим центр тяжести Xc (середина отрезка bg) = (b+g)/2 = (½, ½)
Отражение вершины: X1= 2Xc – w = (1,1)
Вычисляем значение в точке X1
F(X1)= -12 ; F(X1)Растяжение вершины: X2 = Xc + α(X1 – Xc)
Возьмем α = 2 X2 = (1.5, 1.5)
Вычисляем значение в точке X2
F(X2) = -15.75 получаем новые вершины
V1(1.5, 1.5); F(V1) = -15.75
V2(1, 0); F(V2) = -5
V3(0, 1); F(V3) = -8
Начинаем алгоритм сначала!

Слайд 12

Пример

Результат для 10 итераций

Таблица значений для 10 итераций

Ответ:
После 10

Пример Результат для 10 итераций Таблица значений для 10 итераций Ответ: После
итераций мы получаем достаточно точное приближение:
F(0.990, 4.002) = -20.9951
Аналитический экстремум функции достигается в F(1,4) = -21

Слайд 13

Визуальный пример работы

Визуальный пример работы
Имя файла: Метод-деформируемого-многогранника-(Нелдера-Мида).pptx
Количество просмотров: 49
Количество скачиваний: 0