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

Назначение

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

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

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

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

Если по каким - либо причинам затруднительно указать вершины исходного многогранника, то можно установить такой режим работы подпрограммы, когда достаточно задать в первой строке матрицы  P координаты начальной точки поиска минимума  (x^*₁, x^*₂, ..., 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.

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

    int mna5r_c (R_fp f, integer *n, real *p, integer *mp, real *y,
             real *pr, real *prr, real *pbar, real *eps, integer *iregim,
             integer *iflag, integer *itmax)

   Параметры 

   Версии 

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

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

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

struct {
    int iter;
} mna5rr_;

#define mna5rr_1 mna5rr_

int main(void)
{
    /* Local variables */
    static float pbar[2];
    extern int mna5r_c(R_fp, int *, float *, int *, float *, float *,
                       float *, float *, float *, int *, int *, int *);
    extern float f_c();
    static int i__, n;
    static float p[20] /* was [10][2] */;
    static int iflag;
    static float y[2];
    static int itmax, mp;
    static float pr[2];
    static int iregim;
    static float eps, prr[2];

#define p_ref(a_1,a_2) p[(a_2)*10 + a_1 - 11]

    n = 2;
    eps = 1e-6f;
    p_ref(1, 1) = 8.f;
    p_ref(1, 2) = 9.f;
    p_ref(2, 1) = 10.f;
    p_ref(2, 2) = 11.f;
    p_ref(3, 1) = 8.f;
    p_ref(3, 2) = 11.f;
    mp = 10;
    iregim = 1;
    itmax = 500;
    mna5r_c((R_fp)f_c, &n, p, &mp, y, pr, prr, pbar, &eps, &iregim, &iflag,
            &itmax);

    for (i__ = 1; i__ <= 3; ++i__) {
         printf("\n %16.7e %16.7e \n", p_ref(i__, 1), p_ref(i__, 2));
    }
    printf("\n\n %16.7e %16.7e \n", y[0], y[1]);
    printf("\n %5i \n", iflag);
    printf("\n %5i \n\n", mna5rr_1.iter);
    p_ref(1, 1) = 8.f;
    p_ref(1, 2) = 9.f;
    iflag = 0;
    mna5r_c((R_fp)f_c, &n, p, &mp, y, pr, prr, pbar, &eps, &iregim, &iflag,
            &itmax);

    for (i__ = 1; i__ <= 3; ++i__) {
         printf("\n %16.7e %16.7e \n", p_ref(i__, 1), p_ref(i__, 2));
    }
    printf("\n\n %16.7e %16.7e \n", y[0], y[1]);
    printf("\n %5i \n", iflag);
    printf("\n %5i \n", mna5rr_1.iter);
    return 0;
} /* main */


float f_c(float *x, int *n)
{
    /* System generated locals */
    float ret_val, r__1, r__2;

    /* Parameter adjustments */
    --x;

    /* Function Body */
/* Computing 2nd power */
    r__1 = x[1] - .5f;
/* Computing 2nd power */
    r__2 = x[2] - 6.f;
    ret_val = r__1 * r__1 * 4.f + r__2 * r__2;
    return ret_val;
} /* f_c */


Результаты: 

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

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

      y  =  (0.109821e - 5,  0.472409e - 6)

      iflag = 1 ,                 mna5rr_1.iter = 32 

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

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

      y  =  (0.140809e - 5,  0.196219e - 5)

      iflag = 1 ,                 mna5rr_1.iter = 32