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

 (1)

Регулярный симплекс и некоторые операции над ним.
Регулярным симплексом в пространстве называется правильный многогранник, образованный -ой равноотстоящими друг от друга вершинами. Для случая – это равносторонний треугольник, для случая – тетраэдр.
Если в пространстве необходимо построить регулярный симплекс, одна из вершин которого находится в точке , то координаты вершин такого симплекса удобно задавать с помощью матрицы

 (2)

Здесь -й столбец представляет собой координаты -й вершины симплекса, ;

 (3)

-длина ребра симплекса.
Например, регулярный симплекс в двумерном пространстве с одной из вершин в начале координат (когда определяется матрицей


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

 (4)

Здесь

 (5)

вектор координат центра тяжести остальных вершин симплекса (за исключением отраженной вершины )
Таким образом, после отражения -й вершины симплекса с координатами вершин , получаем новый симплекс с координатами вершин

 (6)

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

 (7)

Схема простейшего варианта симплекс-метода.
Суть симплекс-метода раскрывает его простейший вариант.
  1. Задаем начальную точку , длину ребра симплекса и полагаем =0.
  2. По формулам (2), (3) находим координаты всех вершин симплекса.
  3. Вычисляем значения минимизируемой функции во всех вершинах симплекса.
  4. Находим максимальное из значений функции в вершинах симплекса

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

 (8)

где - требуемая точность решения по , - номер произвольной вершины симплекса. Отметим, что выражение в левой части неравенства (8) есть максимальная разность значений функции () в двух вершинах симплекса .
Простейший вариант симплекс-метода иллюстрирует рис. 4, на котором показаны линии уровня функции Химмельблау (=2).
Рис. 4.  Траектория поиска минимума функции Химмельблау простейшим симплекс-методом.
Модифицированный симплекс-метод.
Рассмотренный простейший симплекс-метод склонен к зацикливанию и медленно сходится, если длина ребра симплекса выбрана малой (выбор же большой длины ребра симплекса обеспечивает высокую скорость сходимости, но дает малую точность решения). Поэтому в вычислительной практике используются различные модификации простейшего метода, направленные на преодоление его указанных недостатков.
Основной идей модифицированного симплекс-метода является изменение по некоторому правилу размера симплекса в процессе поиска. При этом наряду с условием (8) в качестве условия окончания итераций можно использовать условие

 (9)

где - текущая длина ребра симплекса, - требуемая точность решения по .
Обычно размер симплекса изменяется при выполнении следующих условий:

«Накрытие» симплексом дна оврага или точки минимума. Пусть - вершина, которая получилась на -ой итерации в результате отражения вершины . Так что координаты вершин нового симплекса равны .
Ситуация интерпретируется как «накрытие» этим симплексом дна оврага или точки минимума и простейший симплекс-метод модифицируется следующим образом (см. рис. 5):
  1. Полагаем =+1 (если =+2, то полагаем =1);
  2. Выполняем отражение -ой вершины симплекса ;
  3. Если ()>() и не все вершины перебраны, то переходим к п.1.
  4. Иначе - продолжаем итерации по схеме простейшего симплекс-метода
Рис. 5.  Траектория поиска минимума функции Розенброка модифицированным симплекс-методом при «накрытии» дна оврага. Пунктиром показаны отвергнутые симплексы.

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

  2. По формуле (7) выполняем редукцию симплекса к вершине .
  3. Продолжаем итерации по схеме простейшего симплекс-метода
Здесь количество итераций рекомендуется находить из условия где * - символ ближайшего целого большего.