Вопрос №48.

Алгоритм оптимизации методом Нелдера-Мида.(+следующий билет)

Последовательность работы метода Нелдера-Мида:

1) Задается исходный симплекс (x_k, k=1,…,n+1), к – номер вершины симплекса;

2) Вершины симплекса упорядочиваются по убыванию целевой функции .

3) Определяются координаты геометрического центра фигуры, состоящей из n лучших вершин (не включая ).

4) Найденный центр отражается. Координаты точки рассчитываются по формуле: , .

В точке рассчитываем значение целевой функции .

5) Значение целевой функции сравнивается с ее значением в вершинах исходного симплекса. В результате сравнения возможны следующие варианты:

I. Если , т.е. - не лучшая, но и не худшая точка по сравнению с исходным симплексом. Тогда вершина с координатой заменяется на вершину с координатой и выполняется следующий шаг поиска, начиная с п.2.

II. Если , то направление считается удачным и делается попытка растяжения симплекса в этом направлении.

Рассчитывается координата новой точки:

- коэффициент растяжения, ( ).

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

Если же , то вершина меняем на и возвращаемся к п.2.

III. Если , то симплекс признается слишком большим и выполняется его сжатие.

- коэффициент сжатия, , .

В этой точке рассчитывается целевая функция и если , то сжатие считается удачным и вершина меняется на и возвращаемся к п.2.

Если , то выполняется текущего симплекса новым

После этого пересчета делается проверка останова задачи:

- погрешность решения.