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

Назначение

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

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

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

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

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

    SUBROUTINE  MNR5R (N, M, X, XE, I0, A, B, B1, LA, A1, NS, T,
                                              FUNC, F, FE, GRAD, G, GE, UP, RM,
                                              IRM, IRM1, IERR) 

   Параметры 

   Версии:  нет 

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

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

           SUBROUTINE  FUNC (X, F, FE)

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

           SUBROUTINE  GRAD (X, G, GE, I0)

       Параметры
       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

       INTEGER*2  IRM1(8)
       INTEGER  I0(4), N, M, DA, IRM(14), IERR, NS(6)
       REAL  X(4), A(4), B(4), B1(4), A1(6), T(4), F, FE, G(4), UP(4), RM(62)
       REAL  XE(4), GE(4)
       DATA  I0 /4*1/, X /5., 0.1, 1., 1./
       DATA  GE /4*1.E - 6/, XE /4*0.1E - 10/
       DATA  A /4*1.E - 6/, B /4*5./
       DATA  A1 /1., 0.5, 3., 2., - 1., - 1./, B1 /5., 2., 0., 0./
       DATA  T /2., 2., 1., 1./, FE /0.1E - 6/, NS /1, 2, 1, 2, 1, 2/
       DATA  UP /100., 3., 2., 1.E - 12/
       EXTERNAL  GRAD, FUNC
       LA = 6
       M = 4
       N = 4
       RM(1) = 20
       CALL  MNR5R (N, M, X, XE, I0, A, B, B1, LA, A1, NS, T, FUNC,
      *                          F, FE, GRAD, G, GE, UP, RM, IRM, IRM1,IERR)

       SUBROUTINE  FUNC (X, F, FE)
       REAL  X(4), F, FE
       F = 4*X(1)*X(1) + 3*X(2)*X(2)
       RETURN
       END

       SUBROUTINE  GRAD (X, G, GE, I0)
       REAL  X(4), G(4), GE(4)
       INTEGER  I0(4)
       DO 3  I = 1, 4
    3 G(I) = 0.
       IF(I0(1) .EQ. 0) GO TO 1
       G(1) = 8*X(1)
    1 IF(I0(2) .EQ. 0) GO TO 2
       G(2) = 6*X(2)
    2 RETURN
       END

Результаты:

      IERR = 2 ;  KOЛИЧECTBO ИTEPAЦИЙ  = 7 ;
      NF (KOЛИЧECTBO BЫЧИCЛEHИЙ ФУHKЦИИ)  = 8 ;
      NG (KOЛИЧECTBO BЫЧИCЛEHИЙ ГPAДИEHTA)  = 22 ;
      F  =  7.692 ;
      X  =  (0.3846,  1.538,  10-6,  1.269) .