Алгоритм Нелдера-Мида для отыскания экстремумов

Алгоритм Нелдера-Мида является широко известным и применяется в качестве алгоритма прямого поиска локального экстремума функций от 2 до 6 переменных. Особенностью алгоритма является продвижение к экстремуму целым облаком пробных точек, который условно назван симплексом. Общее число точек в симплексе равно увеличенному на единицу числу переменных поиска. Продвижение к экстремуму не по линии от одной точки к другой, а внутри какого-то множества пробных точек обеспечило не реагирование на мелкие дефекты целевой функции.

Вводимая информация:

n - число переменных минимизируемой функции;

X^о = (x₁^о,x₂^о,...,x_n^о) - точка первого начального приближения;

h - шаг регуляризации симплекса;

e_x - погрешность нахождения экстремума по параметрам.

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

1 x₁^o x₂^o x₃^o... x _n ^o Q₁

2 x₁^o+h x₂^o... x _n ^o Q₂

3 x₁^o x₂^o+h x₃^o ... x _n ^o Q₃

......

n+1 x₁^o x₂^o x₃^o... x _n ^o+h Q_n+1

Далее до выполнения условия окончания поиска осуществляются итерации (шаги) поиска.

Условием окончания поиска этого метода является неудаленность от лучшей точки симплекса остальных точек симплекса более, чем на e_x.

Каждая итерация начинается с нахождения номеров l и k, соответственно лучшей и худшей по значению функции точек симплекса. Далее осуществляется расчет точки Х_ц - положения центра масс всех точек симплекса за исключением наихудшей точки l.

_n+1

х_iц = 1/n S x_ji,

^j=1

где

n - количество точек в симплексе;

i - номер компоненты вектора X (i=1,2,...,n);

j - номер точки в симплексе.

Значение слагаемого суммы x_kj допускается равным 0.

При работе метода на каждой из итерации может вычисляться одна из особых пробных точек: точка a - точка отражения, точка g - точка растяжения, точка b -точка сжатия. Точки вычисляются по формулам:

Х_a = X_ц+a*(X_ц-Х_к), Х_b = X_ц+b*(Х_ц-Х_к), Х_g = X_ц+g*(Х_ц-Х_к).

Значения коэффициентов a=1, b=0.5 и g=2 подобраны экспериментальным путем.

После расчета точки Х_ц вычисляется пробная точка a. Далее выполняется одно из альтернативных действий.

Если Q_a > Q_l, то уже достигнут нормальный успех. В этом случае рассчитывается Xg и Qg (в надежде на сильный успех). Наилучшая из точек a или g записывается на место наихудшей k точки симплекса (конец итерации).

Если Q_l < Qa < Qk, то имеется слабый успех, и точка a записывается на место k точки (конец итерации).

Если Q_a ³ Q_k, то успеха нет. Рассчитывается X_b и Q_b.

Далее, если Q_b < Q_k, то точка b записывается на место k точки (конец итерации), иначе, если точка b хуже точки k, выполняется процедура редукции симплекса и процедура расчета значения функции в точках симплекса (конец итерации). При выполнении процедуры редукции симплекса все точки симплекса стягиваются к лучшей точке симплекса на половину своего прежнего удаления.