Текст подпрограммы и версий ( Фортран )
mnr6r.zip , mnr6d.zip 		Тексты тестовых примеров ( Фортран )
tmnr6r.zip , tmnr6d.zip
Текст подпрограммы и версий ( Си )
mnr6r_c.zip , mnr6d_c.zip 		Тексты тестовых примеров ( Си )
tmnr6r_c.zip , tmnr6d_c.zip

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

Назначение

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

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

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

                 min  f (x) ,
                 x∈Q 
    Q = { x:  x ∈ En ,   aj ≤ xj ≤ bj ,   aj > - ∞,   bj < ∞ ,   j = 1, 2, ..., n } ,

используется модификация метода Дэвидона - Флетчера - Пауэлла. Вычисленная точка  xk ∈ Q, где  k - номер итерации, считается точкой минимума, если выполнено хотя бы одно из следующих условий:

1.  | xjk - xjk - 1 | ≤ XE(J) для всех  j = 1, 2, ..., n, где  xk = (x1k, x2k,..., xnk ) - точка вычисленная на  k - й итерации, а XE - заданный вектор точности решения по аргументу;
2.  | f (xm ) - f (xm - 1) | ≤ FE для всех  m = k, k - 1, k - 2, где  xm - точка, вычисленная на  m - й итерации, а FE - заданная точность решения задачи по функции;
3.  | f 'j (xk ) | ≤ GE (J) для всех  j = 1, 2, ..., n, где  f 'j (xk ) -  j - я компонента градиента функции  f (x) в точке  xk, а GE - заданный вектор точности решения по градиенту;
4.  выполнено заданное число итераций;
5.  истекло заданное время счета;
6.  произошло замедление счета (см. замечания по использованию).

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

М.Базара, К.Шетти. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982.

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

    SUBROUTINE  MNR6R (X, XE, I0, A, B, N, FUNC, F, FE, GRAD, G,
                                               GE, UP, RM, IRM, TMAX, IERR) 
   Параметры
X - вещественный вектор длины  N; при обращении к подпрограмме содержит заданную начальную точку поиска, на выходе содержит точку минимального вычисленного значения  f (x);
XE - вещественный вектор длины  N, задающий точность решения задачи по аргументу;
I0 - целый вектор длины  N, задающий фиксированные на время минимизации компоненты вектора  X: если I0 (J) = 0, то  J - я компонента вектора  X остается равной своему начальному значению; в противном случае I0 (J) = 1;
A - вещественный вектор длины  N, задающий ограничения снизу на переменные;
B - вещественный вектор длины  N, задающий ограничения сверху на переменные;
N - размерность пространства переменных (тип: целый);
FUNC - имя подпрограммы вычисления значения функции  f (x) (см. замечания по использованию);
F - вещественная переменная, содержащая вычисленное минимальное значение  f (x);
FE - заданная точность решения задачи по функционалу (тип: вещественный);
GRAD - имя подпрограммы вычисления градиента функции  f (x) (см. замечания по использованию);
G - вещественный вектор длины  N, содержащий градиент функции;
GE - вещественный вектор длины  N, задающий точность решения задачи по градиенту;
UP - вещественный вектор длины 4, задающий управляющие параметры алгоритма:
UP(1) - заданная относительная погрешность, позволяющая управлять счетом;
UP(2) - заданное положительное целое число, используемое в критерии замедления счета (см. замечания по использованию);
UP(3) - заданное вещественное число большее единицы, используемое в критерии замедления счета;
UP(4) - вещественное число большее единицы, задающее значение константы дробления шага;
RM - вещественный вектор длины 3 + 3N + N2;
RM(1) - на входе - заданное допустимое число итераций, на выходе - выполненное число итераций;
RM(2) - выполненное число вычислений функции;
RM(3) - выполненное число вычислений градиента;
  остальные элементы массива RM используются как рабочие;
IRM - целый вектор длины  N, используемый как рабочий;
TMAX - вещественная переменная, содержащая заданное время счета (в сек.);
IERR - целая переменная, указывающая причину окончания счета:
IERR=1 - найден минимум с заданной точностью по аргументу;
IERR=2 - найден минимум с заданной точностью по функционалу;
IERR=3 - найден минимум с заданной точностью по градиенту;
IERR=4 - выполнено заданное число итераций;
IERR=5 - истекло время;
IERR=6 - произошло замедление счета. 
   Версии
MNR6D - решение задачи минимизации дифференцируемой функции многих переменных при наличии двусторонних ограничений на переменные методом Дэвидона - Флетчера - Пауэлла с двойной точностью. Все вещественные массивы и переменные, кроме TMAX и UP, должны иметь тип DOUBLE PRECISION. 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

Подпрограммы FUNC и GRAD составляются пользователем.
Первый оператор подпрограммы вычисления функции должен иметь вид:

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

В теле подпрограммы FUNC параметр FE не должен переопределяться.

Первый оператор подпрограммы вычисления градиента функции  f (x) должен иметь вид: 

           SUBROUTINE  GRAD (X, G, GE, I0)
        Параметры:
        X   - вещественный вектор длины  N, задающий точку
                пространства, в которой вычисляется градиент;
        G   - вещественный вектор длины  N, содержащий
                градиент функции в точке  X;
        GE - вещественный вектор длины  N, содержащий на
                входе заданную покомпонентную точность
                вычисления градиента функции, на выходе -
                достигнутую точность вычисления градиента;
        I0  - целый вектор, управляющий вычислением градиента:
                если I0(J) = 0, то полагается G(J) = 0 .
                Значение GE в теле подпрограммы не должно
                переопределяться.

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

Управляющие параметры:
  UP (1) ∈ [ 0.01 ÷ 0.001 ] позволяет временно фиксировать компоненты, по которым функция медленно меняется, подбирается экспериментально;
  UP (2)  - целое число от 2 до 15 - количество подряд идущих итераций, за которые изменения функции должны уменьшиться в UP (3) раз;
  UP (3) ∈ [ 1.1 ÷ 10. ];
  UP (4) > 1.,  UP (4) ∈ [ 1.2 ÷ 100. ] - параметр дробления отрезка на котором минимизируется функция; корректируется в процессе счета
 

Параметры UP (2) и UP (3) используются в критерии замедления счета. С помощью этого критерия фиксируются ситуации, когда изменения функции на каждой итерации на несколько порядков меньше, чем разность между текущим значением и минимальным.

В начале счета и перед выходом из подпрограммы фиксируются значения счетчика времени центрального процессора. TMAX - допустимое время работы центрального процессора, которое пользователь отводит для решения задачи (в сек.).

Если счет закончился при одновременном выполнении нескольких критериев, значение IERR состоит из нескольких цифр. Каждая цифра расшифровывается отдельно, например, IERR = 15 означает, что IERR = 1 и IERR = 5, т.е. достигнута точность по аргументу и истекло время.

Используются служебные подпрограммы: MLU01, MNR11, MNR1N, MNR1Q, MNR2D, MMKRIT, UTMN05, UTMN06, MNR6F, MNR64, MNRUG, MNRU3.

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

Найти минимальное значение функции 
      f(x)  =  ( x2 - x12 )2 + ( 1 - x1 )2

    - 1.3 ≤ x1 ≤ 0.5 ,   0.5 ≤ x2 ≤ 1. 

Начальное приближение     x0  =  ( - 1.2, 1. )

Точное решение:     x* = (0.5, 0.5) ,    f* = 0.3125

       REAL  RM(13), A(2), B(2), X(2), XE(2), G(2), GE(2), UP(4) 
       INTEGER  I0(2), IRM(2) 
       EXTERNAL  FUNC, GRAD 
       DATA  A /- 1.3, 0.5/, B /0.5, 1./ 
       DATA  X /- 1.2, 1/, XE /2*1.E - 18/ 
       DATA  FE /1.E - 18/, GE /2*1.E - 10/ 
       DATA  I0 /2*1/, RM(1) /100./, TMAX /30./ 
       DATA  N /2/, UP /1.E - 15, 10., 1.2, 100./ 
       CALL  MNR6R (X, XE, I0, A, B, N, FUNC, F, FE, GRAD, G,  
      *                          GE, UP, RM, IRM, TMAX, IERR) 

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

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

Результаты: 

      IERR = 1      F = 0.313      X = (0.5, 0.5) 
      RM(1) = 7    RM(2) = 8       RM(3) = 4