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

Пример

Симплекс планирование

Всегда привлекательно воспользоваться безградиентными методами. Они связаны с простыми вычислениями, устойчивы к локальным экстремумам. При последовательном симплекс планировании (ПСП) для каждого шага к оптимуму требуется один опыт. План эксперимента располагается в вершинах симплекса. Симплексом называется правильный выпуклый многогранник, имеющий k+1 вершину в k – мерном факторном пространстве. Для k=2 правильным симплексом будет равносторонний треугольник с вершинами (1, 2, 3). При k=3 – тетраедр.

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

Рис. Поиск экстремального значения. Траектория при ПСП.

Начнём с постановки опытов 1, 2, 3 в вершинах начального симплекса. Начальный симплекс располагают в факторном пространстве на основе априорной информации об объекте исследования. Результаты опытов ранжируют по величине отклика. Выбирают наихудший результат. В данном случае это точка 1. На грани 2 – 3, противолежащей точке 1 строят новый правильный симплекс 2, 3, 4. Причём построение этого симплекса состоит в расчёте координат одной точки 4. Ранжируют, выбирают наихудший результат и рассчитывают вершину следующего симплекса – точку 5. Координаты каждой новой вершины симплексов . Рассчитывают по формуле

Здесь: k - число факторов; u - номер опыта (т.е вершины симплекса); - координата i -го фактора в наихудшем опыте.

Если на протяжении k+1 шага в эксперименте одна вершина симплекса сохраняет своё положение, то такая ситуация называется зацикливанием. В этом случае рекомендуется повторить поиск оптимума из другой точки факторного пространства и с симплексом другого размера. Окончание поиска в тойже области свидетельствует о нахождении оптимума.

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

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

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

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

В. Найдем центр тяжести всех точек, за исключением точки x_h. Пусть центром тяжести будет и вычислим f(x₀)=f₀.

Г. Перемещение начнём от точки x_h. Отразив точку x_h относительно точки x₀, получим точку x_r и найдем f(x_r) = f_r. Операция отражения иллюстрируется рис. Если α > 0 - коэффициент отражения, то положение точки x_r определяется следующим образом: x_r-x₀= α(x₀-x_h), т.е. x_r=(1+ α)x₀ - α x_h.

Замечание. α = |x_r-x₀|/|x₀ -x_h|.

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

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

Рис. Операции отражения и растяжения

Замечание. g= |x_e-x₀|/|x_r-x₀|.

а) Если 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б, описанный выше.

3.Если f_r>f_l и f_r>f_gто перейдем на шаг Е.

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

1. Если 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) с помощью шага сжатия, показанного на рис.

Если f_r > f_h, то сразу переходим к шагу сжатия и находим точку x_c из соотношения x_c-x₀=b(x₀-x_h),

где (0<b<1)- коэффициент сжатия. Тогда x_c=(1+b)x₀-bx_h.

Если f_r<f_h, то сначала заменим точку x_h на точку x_r, а затем произведем сжатие. Тогда точку x_c найдем из соотношения x_c-x₀=b (x_r-x₀), т.е. x_c=bx_r+(1-b)x₀. (рис. ).

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

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

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

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

Рис. Шаги сжатия для f_r > f_h и для f_r < f_h

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

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

Если , то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции x_l. Коэффициенты α, b, g в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать α =1, b=0.5 и g=2. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.