Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/mn_htm_c/mna5r_c.htm
Дата изменения: Tue Apr 28 07:57:16 2015
Дата индексирования: Sun Apr 10 02:02:46 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. MNA5R_C. Задача безусловной минимизации функции многих переменных
Текст подпрограммы и версий
mna5r_c.zip , mna5d_c.zip
Тексты тестовых примеров
tmna5r_c.zip , tmna5d_c.zip

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

Назначение

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

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

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

В подпрограмме mna5r_c выполняется итерационный процесс, на каждом этапе которого к многограннику применяются операции отражения, растяжения или сжатия в зависимости от топографии функции  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.

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

    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 (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_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