Метод деформируемого многогранника (метод Нелдера—Мида)

Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х. Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (рис. 1.6). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

Рис. 1.6.Интерпретация алгоритма метода деформируемого многогранника

Введем следующие обозначения:

x[i, k] =(x1[i, k], …, xj[i, k], …, xn[i, k])^Т, где i = 1, ..., п + 1; k = 0, 1, ..., - i-я вершина многогранника на k-м этапе поиска; х[h, k] — вершина, в которой значение целевой функции максимально, т. е. f(х[h, k] = max{f(x[1, k]), …, f(x[n+1, k])}; х[l, k] - вершина, в которой значение целевой функции минимально, т. е. f(х[l, k]) =min {f(x[1, k]), …, f(x [n+1, k])}; х [п+2, k]- центр тяжести всех вершин, за исключением х[h, k]. Координаты центра тяжести вычисляются по формуле

Алгоритм метода деформируемого многогранника состоит в следующем.

1. Осуществляют проецирование точки х[h, k] через центр тяжести:

x[n+3, k] =x[n+2, k] + a(x[n+2, k] - x[h, k]) , где а > 0 - некоторая константа. Обычно а = 1.

2. Выполняют операцию растяжения вектора х[n+3, k] - х[n+2, k]:

x[n+4, k] =x[n+2, k] + α(x[n+3, k] - x[n+2, k]), где α > 1 - коэффициент растяжения. Наиболее удовлетворительные результаты получают при 2,8 <= α <= 3.

Если f(x[n+4, k]) < f(х[l, k]), то х[h , k] заменяют на x[n+4, k] и продолжают вычисления с п. 1 при k = k + 1. В противном случае х[h, k] заменяют на х[n+3, k] и переходят к п. 1 при k = k + 1.

3. Если f(x[n+3, k]) > f(х[i, k]) для всех i, не равных h, то сжимают вектор x[h, k] - x[n+2, k]:

x[n+5, k] =x[n+2, k] + (х[h, k] – x[n+2, k] ), где β > 0 - коэффициент сжатия. Наиболее хорошие результаты получают при 0,4 <= β <= 0,6.

Затем точку х[h, k] заменяют на х[n+5, k] и переходят к п. 1 при k = k+ 1.

4. Если f(x[n+3, k])> f(x[h, k]), то все векторы х[i, k] - х[l, k] . i= 1,..., п + 1, уменьшают в два раза:

x[i, k] = x[l, k] + 0,5(x[i, k] - x[l, k]) .

Затем переходят к п. 1 при k= k + 1.

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

,

где e = (е1 ,..., еn) - заданный вектор.

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