Методы безусловной многомерной оптимизации. Шипилов С.А. - 9 стр.

                                              9
      4.2.2. Метод Нельдера – Мида (деформируемых многогранников)

     Данный метод является существенно более эффективным, чем простей-
ший алгоритм регулярных симплексов, за счет того, что симплекс меняет свою
форму от цикла к циклу. Рабочий цикл алгоритма состоит из следующих опе-
раций.
    1. Выбирают начальный (обычно регулярный) симплекс x(1) -x(2)-…- x(n+1) и,
       как и в предыдущем алгоритме, рассчитывают значения целевой функ-
       ции в его вершинах.
    2. Из найденных значений целевой функции                          ищут   максимальное
       ymax=f(xmax) и минимальное значение ymin=f(xmin).
    3. Отображают “наихудшую” вершину относительно центра тяжести xц.т
       противоположной грани с коэффициентом α =1 в формулах (4.1).
    4. Анализируют результат отображения, сравнивая значение функции в
       отображенной вершине с ее значениями в вершинах предыдущего сим-
       плекса.
          a) Если при этом значение функции в новой вершине оказалось мень-
             ше, чем наилучшее значение предыдущего симплекса, т.е.
             y(n+2) < ymin , то проводят растяжение симплекса, увеличивая в β>1
             (обычно β =2) раз расстояние от отраженной вершины до центра
             тяжести xц.т -             x (n+3) = β x ( n+ 2) + (1 − β ) x ц.т. . (4.2)
                    Если после операции растяжения значение функции в новой
             точке уменьшается, т.е. y(n+3) < y(n+2), то эта вершина принимается за
             вершину нового симплекса, если же увеличивается, то в качестве
             новой вершины берется точка, полученная после отображения y(n+2).
          b) Когда значение функции в отображенной вершине меньше, чем в
             наихудшей вершине предыдущего симплекса, но больше, чем во
             всех остальных, то производят операцию сжатия c коэффициен-
             том β < 1 (обычно β = 0,5) в формуле (4.2).
        c) Если значение функции в отображенной точке больше, чем в наи-
           худшей вершине предыдущего симплекса, т.е. y(n+2) > ymax , то про-
           изводят редукцию (уменьшение размеров симплекса обычно в два
           раза), т.е. координаты всех вершин симплекса сдвигаются на поло-
           вину расстояния до наилучшей точки x (k ) = x min + 0,5(x(k) - x min ) .
     В качестве критерия остановки авторы алгоритма рекомендуют средне-
квадратичную величину разности значений функции в вершинах симплекса и

                                        [( )               ]
                                                           2
                             1 n+1
среднего ее значения, т.е.       ∑    f x ( k ) − f (x ц.т. ) ≤ ε ,
                           n + 1 i =1
       где ε - заданная точность.