Метод Нелдера – Мида

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

В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.

A. Найдем значения функции f₁=f(x₁), f₂=f(x₂)... f_n+1=f(х_n+1) в вершинах симплекса.

Б. Найдем наибольшее значение функции f_h, следующее за наибольшим значением функции f_g наименьшее значение функции f_l и соответствующие им точки x_h, x_g, x_l.

B. Найдем центр тяжести всех точек, за исключением точки х_h. Пусть центром тяжести будет

(7)

и вычислим f(x₀)=f₀.

Г. Удобнее всего начать перемещение от точки x_h. Отразив точку x_h относительно точки х₀, получим точку х_r и найдем f(x_r) = f_r. Операция отражения иллюстрируется (Рис 4.). Если а > 0 - коэффициент отражения, то положение точки х_r определяется следующим образом:

т.е.

(8)

Замечание:

Д. Сравним значения функций f_r и f_l.

1. Если f_r < f_l, то мы получили наименьшее значение функции. Направление из точки x₀ в точку x_r наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку x_e и значение функции f_e = f(x_e). (рис. 5) иллюстрирует операцию растяжения симплекса.

Рис. 4.

Рис. 5.

Коэффициент растяжения можно найти из следующих соотношений:

т.е.

(9)

Замечание:

а) Если f_e < f_l, то заменяем точку x_h на точку x_e и проверяем (n + 1)-ую точку симплекса на сходимость к минимуму (см. шаг Б). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг Б.

б) Если f_e > f_l, то отбрасываем точку x_e. Очевидно, мы переместились слишком далеко от точки x₀ к точке x_r. Поэтому следует заменить точку x_h на точку x_r, в которой было получено улучшение (шаг Д, 1), проверить сходимость и, если она не достигнута, вернуться на шаг Б.

2. Если f_r > f_l, но f_r < f_g, то x_r является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку x_h на точку x_r и, если сходимость не достигнута, возвращаемся на шаг Б, т.е. выполняем пункт 1, 6, описанный выше.

3. Если f_r > f_e и f_r > f_g, перейдем на шаг Е.

Е. Сравним значения функций f_r и f_h.

1. Если f_r > f_h, то переходим непосредственно к шагу сжатия Е, 2.

Если f_r < f_h, то заменяем точку x_h на точку x_r и значение функции f_h на значение функции f_r. Запоминаем значение f_r > f_g из шага Д, 2, приведенного выше. Затем переходим на шаг Е, 2.

2. В этом случае f_r > f_h, поэтому ясно, что мы переместились слишком далеко от точки x_h к точке x₀. Попытаемся исправить это, найдя точку x_c (а затем f_c) с помощью шага сжатия, показанного на (Рис. 6) Если f_r > f_h, то сразу переходим к шагу сжатия и находим точку x_c из соотношения

где - коэффициент сжатия. Тогда

(10)

Если f_r < f_h, то сначала заменим точку x_h на точку x_r, а затем произведем сжатие. Тогда точку x_c найдем из соотношения

т.е.

(11)

(рис. 7).

Рис. 6.

Рис. 7.

Ж. Сравним значения функций f_c и f_h.

1. Если f_c < f_h, то заменяем точку x_h на точку x_c и если сходимость не достигнута, то возвращаемся на шаг Б.

2. Если f_c > f_h, то очевидно, что все наши попытки найти значение меньшее f_h закончились неудачей, поэтому мы переходим на шаг 3.

3. На этом шаге мы уменьшаем размерность симплекса делением пополам расстояния от каждой точки симплекса до x₁ - точки, определяющей наименьшее значение функции.

Таким образом, точка x_j заменяется на точку , т.е. заменяем точку x_i точкой

(12)

Затем вычисляем f_i для i = 1, 2,..., (n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг В.

И. Проверка сходимости основана на том, чтобы стандартное отклонение (n + 1)-го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется

(13)

где .

Если , то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции x_l. Исходя из этого, такой критерий сходимости является разумным, хотя Бокс, Дэвис и Свенн предлагают то, что они считают более " безопасной" проверкой.

Шаги этой процедуры представлены в виде блок-схемы на рис. 8.

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

Начальный симплекс выбирается на наше усмотрение. В данном случае точка x₁ является начальной точкой, затем формируются точки

(14)

где k - произвольная длина шага, a e_j - единичный вектор.

Рис. 8.

Метод полного перебора (метод сеток)

Многомерные задачи, естественно, являются более сложными и трудоемкими, чем одномерные, причем обычно трудности при их решении возрастают при увеличении размерности. Для того чтобы вы лучше почувствовали это, возьмем самый простой по своей идее приближенный метод поиска наименьшего значения функции. Покроем рассматриваемую область сеткой G с шагом h (Рис. 9) и определим значения функции в ее узлах. Сравнивая полученные числа между собой, найдем среди них наименьшее и примем его приближенно за наименьшее значение функции для всей области.

Рис. 9.

Как мы уже говорили выше, данный метод используется для решения одномерных задач. Иногда он применяется также для решения двумерных, реже трехмерных задач. Однако для задач большей размерности он практически непригоден из-за слишком большого времени, необходимого для проведения расчетов. Действительно, предположим, что целевая функция зависит от пяти переменных, а область определения G является пятимерным кубом, каждую сторону которого при построении сетки мы делим на 40 частей. Тогда общее число узлов сетки будет равно . Пусть вычисление значения функции в одной точке требует 1000 арифметических операций (это немного для функции пяти переменных). В таком случае общее число операций составит 10¹¹. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 10₅ секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.