Рассмотрим следующую задачу локальной безусловной оптимизации: найти минимум критерия оптимальности (), определенного в -мерном евклидовом пространстве ,

 (1)

В случае если функция () является овражной функцией, эффективность симплекс-метода при решении задачи (1) значительно снижается в силу того, что регулярный симплекс нельзя «вытянуть» вдоль оврага. Метод Нелдера-Мида (метод деформируемого многогранника) является развитием симплекс-метода и использует в процессе поиска деформацию (изменение размеров и формы) текущего симплекса (не обязательно регулярного).
Метод использует следующие операции над симплексами:

Отражение вершины симплекса относительно центра тяжести остальных вершин (см. параграф 5, рис. 1). В результате отражения -й вершины симплекса с координатами вершин , получаем новый симплекс с координатами вершин

 (2)

где

 (3)

вектор координат центра тяжести остальных вершин симплекса (за исключением отраженной вершины ).
Рис. 1.  Отражение вершины X1 симплекса в пространстве R2 относительно центра тяжести Xc остальных вершин.
Редукции симплекса (см. параграф 5, рис. 2) - уменьшение длин всех ребер симплекса в одно и то же количество раз. В результате выполнения редукции вершин симплекса к вершине получаем новый симплекс с координатами вершин

 (4)

где - коэффициент редукции.
Рис. 2.  Редукция вершин симплекса в пространстве R2 к вершине X1.
Сжатие симплекса (см. рис. 3). В результате выполнения сжатия симплекса , [1,+1] в направлении получаем новый симплекс с координатами вершин

 (5)

где - коэффициент сжатия, - вектор координат центра тяжести остальных вершин симплекса (см. (3)).
Рис. 3.  Сжатие симплекса в пространстве R2 в направлении (X1-Xc).
Растяжение симплекса (см. рис. 4). В результате выполнения растяжения симплекса в направлении получаем новый симплекс с координатами вершин

 (6)

где - коэффициент растяжения, - вектор координат центра тяжести остальных вершин симплекса (см. (3)).
Рис. 4.  Растяжение симплекса в пространстве R2 в направлении (X1-Xc).
Схема метода Нелдера-Мида.
Симплекс с вершинами обозначим .
  1. Задаем начальную точку , длину ребра симплекса и полагаем =0.
  2. Находим координаты , [1,+1] всех вершин регулярного симплекса с длиной ребра . Вычисляем значения () минимизируемой функции во всех вершинах симплекса.
  3. Среди вершин симплекса находим вершины в которых функция () принимает, соответственно, наименьшее, наибольшее и следующее за максимальным значения, а также находим значения функции () в этих точках:



  4. По формулам (2), (3) выполняем отражение вершину симплекса относительно центра тяжести остальных вершин симплекса – получаем новый симплекс . Вычисляем значение () минимизируемой функции в новой вершине симплекса.
  5. Если условие окончания итераций (см. ниже) выполнено, то в качестве приближенного значения точки минимума функции () принимаем ту вершину симплекса , в которой () имеет минимальное значение, и заканчиваем вычисления.
  6. Если и , то переходим к п.7 (растяжению симплекса) - см. рис. 5. Если , но , то переходим к п.3 (отражению) – см. рис. 6. Если , то переходим к п.8 (сжатию симплекса) – см. рис. 7, рис. 8.
  7. Ситуация и . По формуле (6) выполняем растяжение симплекса в направлении - получаем новый симплекс . Вычисляем значение минимизируемой функции в новой вершине симплекса . Если , то полагаем и переходим к п.3 (отражению вершины симплекса). Иначе полагаем и переходим к п.3 (отражению вершины симплекса) с симплексом (т.е. не используем результаты растяжения).
  8. Ситуация . По формуле (5) выполняем сжатие симплекса в направлении - получаем новый симплекс . Вычисляем значение минимизируемой функции в новой вершине симплекса . Если , то полагаем =+2 и переходим к п.3 (отражению вершины симплекса). Иначе по формуле (4) выполняем редукцию симплекса к вершине - получаем новый симплекс . Вычисляем значение минимизируемой функции во всех новых вершинах симплекса . Полагаем =+1 и переходим к п.3 (отражению симплекса)
Рис. 5.  Ситуация, когда метод Нелдера-Мида использует успешное растяжение симплекса.
Рис. 6.  Ситуация, когда метод Нелдера-Мида использует успешное отражение симплекс.
Рис. 7.  Ситуация, когда метод Нелдера-Мида использует успешное сжатие симплекс.
Рис. 8.  Ситуация, когда метод Нелдера-Мида использует редукцию после неудачного сжатия симплекса. Пунктиром показаны отвергнутые (неудачные) итерации.
На рис. 5 - рис. 8 минимизируемой функцией () является функция Химмельблау.
В качестве условия окончания итераций в методе Нелдера-Мида можно использовать условие


где - требуемая точность решения по , [1,+1] - номер произвольной вершины симплекса. Можно также завершать итерации, когда длина максимального из ребер текущего симплекс станет меньше или равна - требуемой точности решения по .
Изложенная схема метода Нелдера–Мида имеет тот недостаток, что для сильно овражных функций может происходить вырождение («сплющивание») симплекса. Поэтому к рассмотренной схеме метода Нелдера-Мида добавляется этап периодического (через итераций) восстановления симплекса, который заключается в следующем: