Метод Нелдера-Мида. Метод не позволяет учесть ограничения, которые могут быть наложены на оптимизируемые параметры

Метод не позволяет учесть ограничения, которые могут быть наложены на оптимизируемые параметры. Математическая постановка задачи такова.

Требуется найти безусловный минимум функции многих переменных, т.е. найти такую точку

x*Î Rn, что , (5.1)

где - вектор параметров оптимизации,

n – число параметров оптимизации, f – скалярная нелинейная функция.

Описание алгоритма.

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

Операция отражения. Первоначально задаются три вершины треугольника A, B и C. В них вычисляются значение функции. Точки упорядочиваются по возрастанию функций. Пусть A наихудшая вершина, а B и C, соответственно, наилучшая и хорошая. Определяется средняя точка лучшей стороны . Проводится прямая через худшую вершину A и среднюю точку M до точки R. При этом AM=MR. См. рис. 5.5.

Операция растяжения. Если функция в точке M меньше, чем в точке A, то прямая продолжается до точки E. Если функция в точке E меньше, чем в точке R, то найдена лучшая вершина.

Операция сжатия. Если функции в точках R и A совпадают, то необходимо обследовать две точки D₁ и D₂. Они располагаются на серединах отрезков AM и MR. Симплекс всегда должен состоять из трех точек и поэтому новая точка не может занять место точки M. Из точек D₁ и D₂ выбирается лучшая и обозначается D. Получим новый треугольник BCD.

Операция сокращения. Если функция в точке D не меньше, чем значение функции в точке A, то производим сокращение треугольника ABС до треугольника SBM. Стороны сокращаются вдвое. На каждом шаге вычислений определяется лишь одна вершина.

На рис. 5.5 описанные операции проиллюстрированы графически. Точки А, В и С являются точками исходного симплекса. Значения функций в этих точках обозначены f(А), f(В), f(С). В зависимости от соотношений между функциями происходит выполнение соответствующей операции.

Алгоритм выполнения операций показан в таблице № 5.1.

Таблица № 5.1

Если f(R)< f(B), то выполняется случай (i) (либо отражение, либо растяжение)

Иначе выполняется случай (ii) (либо сжатие, либо сокращение).

На рис.5.5 смысл описанных операций пояснен графически.

Рис. 5.5

Опишем алгоритм метода более подробно применительно к функции двух переменных.

(A) Определим значения функции:

в вершинах симплекса.

(Б).Найдем наибольшее значение функции и обозначим его f_h,, следующее за ним по величине значение функции обозначим f_g и наименьшее значение функции обозначим f_l. Соответствующие им точки вершин обозначим .

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

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

(Г) Удобнее всего начать перемещение от точки x_h. Отразив точку х _h отно­сительно точки х ₀, получим точку х_г и найдем f(x_r) = f_r.

Операция отражения иллюстрируется рис. 5.6. Если α > 0 — коэффициент отражения, то положение точки определяется следующим образом:

(5.3)

Замечание, α =

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

1. Если f_r < f_l, то мы получили наименьшее значение функции. Направле­ние из точки в точку х_r наиболее удобно для перемещения. Таким об­разом, мы производим растяжение в этом направлении и находим точку х_е и значение функции f_e = f(x_e). Рисунок 5.7 иллюстрирует операцию растяжения симплекса. Коэффициент растяжения γ > 1 можно найти из следующих соотношений:

Рис. 5.6 Рис. 5.7

х_е – х ₀ = γ (х_r-х₀),

т. е.

х_е=γ х_r + (1-γ) х_о. (5.4)

Замечание, γ = | х_e —х₀| / |х_r -х₀ |.

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

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

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

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

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

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

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

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

Если f_r > f_h, то сразу переходим к шагу сжатия и находим точку х_с из соотношения

x_c-x₀=β (x_h - х₀),

где β (0 < β < 1) — коэффициент сжатия. Тогда

x_c= β x_h + (l - β) x _o. (5.5)

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

х_с -x_о = β (х_r - x _о),

т. е.

х_с= β х_r + (1- β)х₀ (см. рис. 5.9). (5.6)

Рис. 5.8 Рис. 5.9

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

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

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

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

Таким образом, точка x_i заменяется на точку x_i + ½ (x_i – х_l), т. е. заменя­ем точку x_l- точкой

½ (х_i+x_l). (5.7)

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

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

(5.8)

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

Эта процедура представлена далее в виде программы №1 на языке Турбо Паскаль.

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

Начальный симплекс выбирается так:

х₂ = + kе₁ , (5.9)

х₃ = + kе _2,

х_n+1 = + kе_n ,

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

Метод эффективен до n 6. Для функций, имеющих “овраги”, может происходить вырождение симплекса и тогда продолжать расчеты невозможно. Это чаще всего происходит при числе переменных больше двух.