Поиск минимума функции многих переменных методом Нелдера - Мида

           end;

 

     { вычисляем  координаты цента тяжести}

         for q:=1 to n do Point_H[q] := 0;

          for i:=1 to n+1 do

           begin

             if i<>num_H then

              for q:=1 to n do

                   Point_H[q] := Point_H[q]+(N_kub[i][q])/n;

           end;

 

     { проверяем  критерий останова }

       len_max:=0;

       for q:=1 to n do len_max := len_max+sqr(N_kub[1][q]-Point_H[q]);

 

       for j:=2 to n+1 do

        begin

          len:=0;

          for q:=1 to n do len:=len+sqr(N_kub[j][q]-Point_H[q]);

          if len>len_max then len_max := len;

        end;

 

       len:=0; for q:=1 to n do len:=len+sqr(e[q]);

       if len_max < len then break;

 

       { выполняем отражение с a>0 }

       for q:=1 to n do

       Point_new[q] := Point_H[q] + a*(Point_H[q]-N_kub[num_H][q]);

 

       F_new := Formula(Point_new);

 

       if F_new <= Fmin then

        begin

        { выполняем растяжение}

          for q:=1 to n do

          Point_new2[q] := Point_H[q] + gamma*(Point_new[q]-N_kub[num_H][q]);

          F_new2 := Formula(Point_new2);

 

          if F_new2 <= F_new then

           begin

              for q:=1 to n do N_kub[num_H][q] := Point_new2[q];

              continue;

           end

          else

           begin

              for q:=1 to n do N_kub[num_H][q] := Point_new[q];

              continue;

           end;

 

        end;

 

       pr := 0;

 

       for j:=1 to n+1 do

        begin

          if j<>num_L then

             if (F_new<=Fmin) or (F_new>=Formula(N_kub[j])) then pr :=1;

        end;

       if pr = 0 then

        begin

           for q:=1 to n do N_kub[num_H][q] := Point_new[q];

           continue;

        end;

 

       if F_new<Fmax then

        begin

        { сжатие к основанию }

          for q:=1 to n do

          N_kub[num_H][q] := Point_H[q]+beta*(N_kub[num_H][q]-Point_H[q]);

          continue;

        end

       else

        begin

          for j:=1 to n+1 do

           begin

            if j<>num_L then { сжатие к лучшей  вершине }

            for q:=1 to n do

             N_kub[j][q] := N_kub[num_L][q] + 0.5*(N_kub[j][q]-N_kub[num_L][q]);

           end;

          continue;

        end;

     end;

end;

 

 

begin

 

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Результаты тестирования

Функция , точность 0.001

 

==Shag 1

  x[1]=[3.00000, 4.00000],  f(x[1])=4.000000

  x[2]=[2.00000, 5.00000],  f(x[2])=10.000000

  x[3]=[3.00000, 6.00000],  f(x[3])=16.000000

==Shag 2

  x[1]=[3.00000, 4.00000],  f(x[1])=4.000000

  x[2]=[2.00000, 5.00000],  f(x[2])=10.000000

  x[3]=[2.00000, 3.00000],  f(x[3])=2.000000

==Shag 3

  x[1]=[3.00000, 4.00000],  f(x[1])=4.000000

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[2.00000, 3.00000],  f(x[3])=2.000000

==Shag 4

  x[1]=[2.75000, 3.25000],  f(x[1])=1.625000

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[2.00000, 3.00000],  f(x[3])=2.000000

==Shag 5

  x[1]=[2.75000, 3.25000],  f(x[1])=1.625000

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.75000, 2.25000],  f(x[3])=0.625000

==Shag 6

  x[1]=[2.87500, 2.62500],  f(x[1])=0.406250

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.37500, 2.12500],  f(x[3])=0.156250

==Shag 7

  x[1]=[2.93750, 2.31250],  f(x[1])=0.101563

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.18750, 2.06250],  f(x[3])=0.039063

==Shag 8

  x[1]=[2.96875, 2.15625],  f(x[1])=0.025391

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.09375, 2.03125],  f(x[3])=0.009766

==Shag 9

  x[1]=[2.98438, 2.07813],  f(x[1])=0.006348

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.04688, 2.01563],  f(x[3])=0.002441

==Shag 10

  x[1]=[2.99219, 2.03906],  f(x[1])=0.001587

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.02344, 2.00781],  f(x[3])=0.000610

==Shag 11

  x[1]=[2.99609, 2.01953],  f(x[1])=0.000397

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.01172, 2.00391],  f(x[3])=0.000153

==Shag 12

  x[1]=[2.99805, 2.00977],  f(x[1])=0.000099

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.00586, 2.00195],  f(x[3])=0.000038

==Shag 13

  x[1]=[2.99902, 2.00488],  f(x[1])=0.000025

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.00293, 2.00098],  f(x[3])=0.000010

==Shag 14

  x[1]=[2.99951, 2.00244],  f(x[1])=0.000006

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.00146, 2.00049],  f(x[3])=0.000002

==Shag 15

  x[1]=[2.99976, 2.00122],  f(x[1])=0.000002

  x[2]=[3.00000, 2.00000],  f(x[2])=0.000000

  x[3]=[3.00073, 2.00024],  f(x[3])=0.000001

==========================================

Результат:

 Точка 1:  Значение  функции: 0.000002

   [2.99976, 2.00122]

 Точка 2:  Значение  функции: 0.000000

   [3.00000, 2.00000]

 Точка 3:  Значение  функции: 0.000001

   [3.00073, 2.00024]

 

 

Выводы

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

 

Литература

 

1. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988
2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987
3. Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании. М.: Финансы и статистика, 1999.