Текст подпрограммы и версий ( Фортран )
mna5r.zip , mna5d.zip
Тексты тестовых примеров ( Фортран )
tmna5r.zip , tmna5d.zip
Текст подпрограммы и версий ( Си )
mna5r_c.zip , mna5d_c.zip
Тексты тестовых примеров ( Си )
tmna5r_c.zip , tmna5d_c.zip

Подпрограмма:  MNA5R

Назначение

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

Математическое описание

Пусть задана функция N переменных F (x1, x2, ..., xN) и пусть известны координаты N + 1 вершин многогранника, задаваемых в виде матрицы P (N + 1, N), каждая строка которой содержит координаты соответствующей вершины многогранника в пространстве En. Вершины многогранника рассматриваются в качестве пробных векторов при поиске локального минимума функции  F.

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

Если по каким - либо причинам затруднительно указать вершины исходного многогранника, то можно установить такой режим работы подпрограммы, когда достаточно задать в первой строке матрицы  P координаты начальной точки поиска минимума  (x*1, x*2, ..., x*N). В этом случае в качестве исходного в подпрограмме строится правильный многогранник (регулярный симплекс) следующим образом:

             |  x*1              x*2             x*3            ...      x*n        |
             |  x*1 + d1     x*2 + d2     x*3 + d2     ...     x*n + d2  |
   P  =   |   x*1 + d2     x*2 + d1     x*3 + d2     ...     x*n + d2  |   ,
             |  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
             |   x*1 + d2     x*2 + d2     x*3 + d1     ...     x*n + d1  |

  где    d1  =  ((n + 1)1/2 + n - 1) / (n √2)  ,     d2   =   ((n + 1)1/2 - 1) / (n √2) 

Д.Химмельблау. Прикладное нелинейное программирование. Изд - во "Мир", 1975.

Использование

    SUBROUTINE  MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS,
                                              IREGIM, IFLAG, ITMAX) 

Параметры

F - имя вещественной подпрограммы - функции вычисления F (x1, x2, ..., xN), имеющей два следующих формальных параметра:
X - вещественный вектор длины  N, содержащий координаты точки, в которой вычисляется значение функции  F;
N - количество переменных (тип: целый)
N - количество переменных (тип: целый);
P - вещественный двумерный массив размеров MP на N, содержащий на входе в подпрограмму, либо в своих первых N + 1 строках координаты вершин исходного многогранника (случай, когда IREGIM = 1), либо в своей первой строке координаты начальной точки поиска минимума (случай, когда IREGIM = 0); на выходе из подпрограммы содержит координаты вершин многогранника, полученного на последней итерации; в качестве искомой точки минимума может быть взята его любая вершина, если IFLAG = 1;
MP - первая размерность двумерного массива  P в вызывающей программе, MP ≥ N + 1 (тип: целый);
Y - вещественный вектор длины  N, на выходе из подпрограммы содержащий значения функции  F в вершинах многогранника, полученного на последней итерации;
            PR -
         PRR  
         PBAR  
вещественные векторы длины  N, используемые в подпрограмме в качестве рабочих;
EPS - заданное допустимое отклонение между наибольшим и наименьшим значениями, которые функция  F принимает в вершинах текущего деформируемого многогранника (тип: вещественный);
IREGIM - задает режим работы подпрограммы (тип: целый); если IREGIM = 0, то в первой строке массива  P задаются координаты начальной точки поиска минимума (в этом случае подпрограмма сама строит исходный многогранник); если IREGIM = 1, то в массиве  P следует задать все вершины исходного многогранника;
IFLAG - целая переменная, служащая для сообщения о том, удалось ли найти локальный минимум за ITMAX или меньше итераций; при этом:
IFLAG=0 - когда минимум функции  F не найден; тогда массив  P содержит координаты вершин многогранника, полученного на последней итерации;
IFLAG=1 - когда точка минимума найдена;
ITMAX - заданное максимальное количество итераций (тип: целый).

Версии

MNA5D - поиск минимума функции многих переменных методом деформируемого многогранника без вычисления производной; при этом все вещественные параметры должны иметь тип DOUBLE PRECISION, а подпрограмма - функция  F должна быть описана как DOUBLE PRECISION  FUNCTION.

Вызываемые подпрограммы: нет

Замечания по использованию

 

В подпрограммах MNA5R и MNA5D имеется общий блок COMMON /MNA5RR/ ITER. Переменная ITER полагается равной количеству итераций, выполненных при поиске минимума функции. Если IFLAG = 0, то ITER = ITMAX. В этом случае следует либо увеличить ITMAX, либо увеличить EPS.

Необходимо иметь в виду, что точка минимума, как правило, вычисляется с точностью на 2 - 3 порядка худшей, чем EPS.

Пример использования

       REAL  P(10, 2), Y(2), PR(2), PRR(2), PBAR(2) 
       EXTERNAL  F 
       COMMON /MNA5RR/ ITER 
       N = 2 
       P(1, 1) = 8.0 
       P(1, 2) = 9.0 
       P(2, 2) = 10.0 
       P(2, 2) = 11.0 
       P(3, 1) = 8.0 
       P(3, 2) = 11.0 
       MP = 10 
       EPS = 1.E - 6 
       IREGIM = 1 
       ITMAX = 500 
       CALL  MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS, IREGIM,
      *                           IFLAG, ITMAX) 
       P(1, 1) = 8.0 
       P(1, 2) = 9.0 
       IFLAG = 0 
       CALL  MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS, IREGIM,
      *                           IFLAG, ITMAX) 

       FUNCTION  F (X, N) 
       DIMENSION X(N) 
       F = 4.0*(X(1) - 0.5)**2 + (X(2) - 6.0)**2 
       RETURN 
       END 

Результаты: 

- после первого обращения к подпрограмме:

      P(1, 1) = 0.500369 ,      P(1, 2) = 6.00074 
      P(2, 1) = 0.500333 ,      P(2, 2) = 5.99983 
      P(3, 1) = 0.499807 ,      P(3, 2) = 5.99971 

      Y  =  (0.109821E - 5,  0.472409E - 6)

      IFLAG = 1 ,                 ITER = 32 

- после второго обращения к подпрограмме:

      P(1, 1) = 0.499617 ,      P(1, 2) = 5.99909 
      P(2, 1) = 0.500631 ,      P(2, 2) = 5.99939 
      P(3, 1) = 0.500202 ,      P(3, 2) = 6.00099 

      Y  =  (0.140809E - 5,  0.196219E - 5)

      IFLAG = 1 ,                 ITER = 32