Основные шаги метода переменного многогранника Нелдера-Мида.

 

1) «Подготовка». Вначале выбирается  точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции:

2) «Сортировка». Из вершин симплекса выбираем три точкиx h {\displaystyle x_{h}} :  c наибольшим (из выбранных) значением функции f h {\displaystyle f_{h}} ,  x g {\displaystyle x_{g}} со следующим по величине значением f g {\displaystyle f_{g}}  и  x l {\displaystyle x_{l}} с наименьшим значением функции f l {\displaystyle f_{l}} . Целью дальнейших манипуляций будет уменьшение по крайней мере f h {\displaystyle f_{h}} .

3) Нахождение центра тяжести всех точек, за исключением :

 

(2.1)

Вычислять  не обязательно.

4) «Отражение». Отразим точку  относительно  с коэффициентом α (при α=1 это будет центральная симметрия, в общем случае – гомотетия), получим точку  и вычислим в ней функцию: . Координаты новой точки вычисляются по формуле:

 

(2.2)

 

5) Далее смотрим, насколько нам удалось уменьшить функцию, ищем место f r {\displaystyle f_{r}} в ряду f h, f g, f l {\displaystyle f_{h},f_{g},f_{l}} , .

· Если , то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка

 

(2.3)

и значение функции .

o Если , то можно расширить симплекс до этой точки: присваиваем точке  значение  и заканчиваем итерацию (переход к шагу 9).

o Если , то переместились слишком далеко: присваиваем точке  значение  и заканчиваем итерацию (переход к шагу 9).

· Если , то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке  значение  и переходим на шаг 9.

· Если , то меняем местами значения . Также нужно поменять местами значения .Переход к шагу 6.

· Если , то переход к шагу 6.

6) «Сжатие». Строим точку

 

(2.4)

и вычисляем в ней значение .

7) Если , то присваиваем точке  значение  и переходим к шагу 9.

8) Если , то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса – гомотетию к точке с наименьшим значением .

9) Последний шаг – проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.

 

Блок – схема метода переменного многогранника Нелдера-Мида.

 

Блок-схема вышеописанного алгоритма метода Нелдера-Мида выглядит следующим образом:

 

Рисунок 3 – Блок-схема алгоритма метода Нелдера-Мида.

 

Тестовая функция.

 

       В качестве тестовой функции для метода Нелдера-Мида, была использована функция Розенброка. Это невыпуклая функция, используемая для оценки производительности алгоритмов оптимизации, предложенная Ховардом Розенброком в 1960 году. Считается, что поиск глобального минимума для данной функции является нетривиальной задачей. Является примером тестовой функции для локальных методов оптимизации.

    Функция Розенброка для двух переменных определяется как:

 

(2.5)

 

Она имеет глобальный минимум в точке , где .

Рисунок 4 - Значение функции Розенброка для двух переменных в окрестности точки (x,y) = (0,0).