Поиск оптимального значения функции с помощью метода Нелдера-Мида

Метод Нелдера и Мида относится к методам прямого поиска, в которых используются только значения функции (не требуются значения производных целевой функции). Этот метод является развитием симплексного метода Спендли, Хекста и Химсворта. Симплексом называется регулярный многогранник, т.е. множество -й равноудаленной точки в ( -мерном пространстве). В двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве – правильный тетраэдр. Идея метода состоит в сравнении значений целевой функции в вершинах симплекса и в перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. Эта особенность послужил причиной появления второго названия метода – поиск по деформируемому многограннику. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если .

Кратко метод Нелдера и Мида может быть описан следующим образом: минимизируется функция независимых переменных с использованием вершин деформируемого многогранника в . Каждая вершина может быть идентифицирована вектором , ( ), где i – номер вершины многогранника, k – номер очередного этапа поиска. Вершина многогранника, в которой значение максимально, проектируется через центр тяжести оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением на более хорошие точки с использованием операций отражения, растяжения, сжатия и редукции многогранника, пока не будет найден минимум , т.е. пока не будет выполнено условие, соответствующее критерию останова алгоритма.

Введем необходимые обозначения и перейдем к подробному описанию метода.

Пусть , ( ) является, как было сказано выше, i -й вершиной многогранника на k -м шаге поиска, и пусть значение целевой функции в равно . Кроме того, отметим те вершины многогранника (векторы x), в которых целевая функция принимает максимальное и миниимальное значения:

- вершина многогранника, в которой ;

- вершина многогранника, в которой .

Поскольку многогранник в состоит из вершин , пусть будет центром тяжести всех вершин, исключая , тогда

. (3.3.1)

Критерием останова алгоритма является выполнение следующего условия:

, (3.3.2)

где - произвольное малое число, а - значение целевой функции в центре тяжести .

Начальный многогранник выбирается в виде регулярного симплекса, построенного относительно произвольной точки, или, что проще, нерегулярного (например, симплекс, у i -й вершины которого i -я координата равна 1, а остальные координаты равны 0, n+1–я точка – начало координат). Процедура отыскания вершины в , в которой имеет лучшее значение (наименьшее), состоит из следующих операций:

A. Инициализация значений: . Определяем вершины начального симплекса.

B. Проверка критерия останова алгоритма. Если неравенство (3.3.2) выполняется, то переход к операции I (все значения функции уже лежат вблизи точки минимума функции ).

C. Подготовительный этап: определяем значения целевой функции в вершинах многогранника, находим наименьшее значение функции и соответствующую ему вершину , наибольшее значение функции и соответствующую ему вершину , вычисляем координаты центра тяжести .

D. Отражение – проецирование через центр тяжести (см. рис.3.3.1) в соответствии с соотношением

, (3.3.3)

где является коэффициентом отражения; - центр тяжести, вычисляемый по формуле (3.3.1); - вершина, в которой функция цели принимает наибольшее из ее значений на k-м этапе.

Рисунок 3.3.1. Отражение. Рисунок 3.3.2. Растяжение.

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

, (3.3.4)

где представляет собой коэффициент растяжения (см. Рис. 3.3.2).

Если , то на место записывается , в противном случае на место записывается . Затем процедура продолжается с операции H.

F. Если , то
Сжатие: вычисляем

, (3.3.5)

где представляет собой коэффициент сжатия.
Затем на место записывается . Затем процедура продолжается с операции H.

Рисунок 3.3.3. Сжатие.

G. Если , то
Редукция: все векторы , уменьшаются с коэффициентом () с отсчетом от в соответствии с формулой

, . (3.3.6)

Затем процедура продолжается с операции H.

H. . Переход к операции В.

I. Конец.

Коэффициенты в вышеописанном алгоритме, как уже было сказано, называются коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать и . Рекомендация основана на результатах экспериментов с различными комбинациями значений. Хотя другие исследователи рекомендуют следующие диапазоны для этих параметров: , .