БЧА НИВЦ МГУ. MNA5R_C. Задача безусловной минимизации функции многих переменных

Текст подпрограммы и версий
mna5r_c.zip , mna5d_c.zip

Тексты тестовых примеров
tmna5r_c.zip , tmna5d_c.zip

Подпрограмма: 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^*₁              x^*₂             x^*₃            ...      x^*_n        |
             |  x^*₁ + d₁     x^*₂ + d₂     x^*₃ + d₂     ...     x^*_n + d₂  |
   P  =   |   x^*₁ + d₂     x^*₂ + d₁     x^*₃ + d₂     ...     x^*_n + d₂  |   ,
             |  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
             |   x^*₁ + d₂     x^*₂ + d₂     x^*₃ + d₁     ...     x^*_n + d₁  |

  где    d₁  =  ((n + 1)^1/2 + n - 1) / (n √2)  ,     d₂   =   ((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)

   Параметры

f -	имя вещественной подпрограммы - функции вычисления F (x₁, x₂, ..., x_n), имеющей два следующих формальных параметра:

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_c -

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

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

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

В подпрограммах mna5r_c и mna5d_c имеется внешняя структура с именем mna5rr_ , содержащая элемент целого типа с именем iter. Переменная iter полагается равной количеству итераций, выполненных при поиске минимума функции. Если iflag = 0, то iter = itmax. В этом случае следует либо увеличить itmax, либо увеличить eps.

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

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

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