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

Назначение

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

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

   Для решения задачи:

       min  f(x) ,    x∈Q ,
        x
где     Q = { x:  A1*x = B1 ,   A ≤ x ≤ B } ,
       x, A, B - векторы из  En ,
             B1 - вектор из  Em ,
             A1 - вещественная матрица  m * n . 

Используется модификация метода условного градиета. В процессе счета каждое новое приближение определяется по формуле:

     xk+1  =  xk + αk(yk - xk) , 

где    y_k - минимум линейной функции  < f ' (x_k), x - x_k > при  x ∈ Q;
   f ' (x_k) - градиент функции  f точке  x_k;
        α_k - величина шага по направлению спуска  p_k = y_k - x_k.

B программе предусмотрены четыре критерия останова: по времени, по числу итераций, по величине сдвига в пространстве аргумента и по изменению функции.

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

    int mnr5r_c (integer *n, integer *m, real *x, real *xe,
            integer *i0, real *a, real *b, real *b1, integer *la, real *a1, 
            integer *ns, real *t, S_fp func, real *f, real *fe, S_fp grad,
            real *g, real *ge, real *up, real *rm, integer *irm, shortint *irm1,
            integer *ierr)

   Параметры 

   Версии:  нет 

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

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

           int func(float *x, float *f, float *fe)

       Параметры
       x   - вещественный вектор длины  n, задающий
               точку пространства, в которой вычисляется
               значение функции;
       f   - вещественная переменная, содержащая
               вычисленное значение функции в точке  x;
       fe - заданная точность вычисления функции в
               точке  x (тип: вещественный).  

           int grad(float *x, float *g, float *ge, int *io)

       Параметры
       x   - вещественный вектор длины  n, задающий 
               точку пространства, в которой вычисляется градиент;
       g   - вещественный вектоp длины  n, содержащий
               вычисленный градиент функции в точке  x;
       ge - вещественный вектоp длины  n, содержащий
               абсолютные точности, с которыми требуется
               вычислить компоненты градиента;
       i0  - целый вектоp длины  n, используемый при
               вычислении градиента:  если  i0(j) = 1,
               то в  g(j) засылается значение  j-ой
               компоненты градиента, если  i0(j) = 0,
               то в  g(j) засылается 0. 

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

     min  f(x)  =  4x12 + 3x22

                  x1 + 3x2 - x3  =  5
             0.5x1 + 2x2 - x4  =  2

             10-6 ≤ x1 ≤ 5
             10-6 ≤ x2 ≤ 5
             10-6 ≤ x3 ≤ 5
             10-6 ≤ x4 ≤ 5

int main(void)
{
    /* Initialized data */
    static int io[4] = { 1,1,1,1 };
    static float up[4] = { 100.f,3.f,2.f,1e-12f };
    static float a1[6] = { 1.f,.5f,3.f,2.f,-1.f,-1.f };
    static int ns[6] = { 1,2,1,2,1,2 };
    static float x[4] = { 5.f,.1f,1.f,1.f };
    static float ge[4] = { 1e-6f,1e-6f,1e-6f,1e-6f };
    static float xe[4] = { 1e-11f,1e-11f,1e-11f,1e-11f };
    static float a[4] = { 1e-6f,1e-6f,1e-6f,1e-6f };
    static float b[4] = { 5.f,5.f,5.f,5.f };
    static float b1[4] = { 5.f,2.f,0.f,0.f };
    static float t[4] = { 2.f,2.f,1.f,1.f };
    static float fe = 1e-7f;

    /* Local variables */
    extern int grad_c(), func_c();
    static int ierr;
    extern int mnr5r_c(int *, int *, float *, float *, int *, float *,
                       float *, float *, int *, float *, int *, float *,
                       U_fp, float *, float *, U_fp, float *, float *,
                       float *, float *, int *, shortint *, int *);
    static float f, g[4];
    static int m, n, la;
    static float rm[58];
    static int irm[16];
    static shortint irm1[8];

    la = 6;
    m = 4;
    n = 4;
    rm[0] = 20.f;
    mnr5r_c(&n, &m, x, xe, io, a, b, b1, &la, a1, ns, t, (U_fp)func_c, &f,
            &fe, (U_fp)grad_c, g, ge, up, rm, irm, irm1, &ierr);

    printf("\n %5i \n", ierr);
    printf("\n %12.3e %12.3e \n", rm[1], rm[2]);
    printf("\n %12.3e \n", f);
    printf("\n %12.4e %12.4e %12.4e %12.4e \n", x[0], x[1], x[2], x[3]);
    printf("\n %12.3e \n", rm[0]);
    return 0;
} /* main */

int func_c(float *x, float *f, float *fe)
{
    /* Parameter adjustments */
    --x;

    /* Function Body */
    *f = x[1] * 4 * x[1] + x[2] * 3 * x[2];
    return 0;
} /* func_c */

int grad_c(float *x, float *g, float *ge, int *io)
{
    static int i__;

    /* Parameter adjustments */
    --io;
    --ge;
    --g;
    --x;

    /* Function Body */
    for (i__ = 1; i__ <= 4; ++i__) {
/* l3: */
        g[i__] = 0.f;
    }
    if (io[1] == 0) {
        goto l1;
    }
    g[1] = x[1] * 8;
l1:
    if (io[2] == 0) {
        goto l2;
    }
    g[2] = x[2] * 6;
l2:
    return 0;
} /* grad_c */


Результаты:

      ierr = 2 ;  кoличecтвo итepaций  = 7 ;
      nf (кoличecтвo вычиcлeний фyнкции)  = 8 ;
      ng (кoличecтвo вычиcлeний гpaдиeнтa)  = 22 ;
      f  =  7.692 ;
      x  =  (0.3846,  1.538,  10-6,  1.269) .