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

Назначение

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

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

Для решения задачи
     min  f(x) ,   x ∈ En .

При ограничениях    h i(x)  =  0 ,   i = 1, ..., m ,
                                    g i(x) ≥ 0 ,    i = m + 1, ..., P , 

используется метод скользящего (нежесткого) допуска.

B соответствии с алгоритмом исходная задача заменяется следующей

     min  f(x) ,    x ∈ En 

при ограничениях    Ф^(k) - T (x) ≥ 0,

где  Ф^(k) ≥ 0 - значение критерия допуска для нарушения ограничений решаемой задачи на  k - ом шаге алгоритма, а  T (x) ≥ 0 - функционал над множеством всех функций, задающих ограничения в исходной задаче.

Hа каждом шаге алгоритма задача безусловной минимизации решается методом деформируемого многогранника (Нельдера и Мида).

 Функция  Ф имеет вид:

      Ф(k)  =  min  { Ф(k-1) ,
                                             r+1
                                         [   ∑   || xi(k) - x(k)r+2 ||  ] (m+1) / (r+1) } ,
                                             i =1
      Ф0  =  2 (m+1) A ,
 где 

A - величина, характеризующая размер исходного многогранника (см. замечания по использованию);

m - число ограничений в виде pавенств;

x_i^(k) - вектоp, задающий положение  i - ой вершины многогранника в пространстве  Eⁿ;

r = (n - m) - число степеней свободы целевой функции  f (x);

x^(k)_r + 2 - вектоp, задающий положение вершины, которая соответствует центру тяжести рассматриваемого многогранника при  n = r;

Ф^(k - 1) - значение  Ф на (k - 1) - ом шаге алгоритма;

k = 0, 1,... - индекс, указывающий число полностью законченных шагов алгоритма.

Функционал  T (x) является мерой степени нарушения ограничений и имеет вид:

                           m                   P
       T(x)  =  + [  ∑  hi2(x)   +  ∑     Ui gi2(x) ]1/2 ,
                          i =1               i =m+1
   где  Ui  =  0   при  gi(x) ≥ 0    и   Ui  =  1   при  gi(x) < 0. 

Работа алгоритма заканчивается, если выполнено хотя бы одно из условий:

1. Ф(k) < 1.E - 8 ,
       n+1
2. (  ∑  ( f(xi(k)) - f(x(k)r+2) )2 / n )1/2  <  ACC ,
       i =1
где 

f (x_i^(k)) - значение целевой функции в  i - ой вершине многогранника на  k - ом шаге алгоритма;

f (x^(k)_r + 2) - значение целевой функции в центре тяжести многогранника на  k - ом шаге алгоритма;

ACC - точность вычисления минимума целевой функции.

Д.Химмельблау, Прикладное нелинейное программирование, Изд - во "Мир", Mосква, 1975.

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

    SUBROUTINE  MNBBR (N, NMP1, ITMAX, ITMT, ALFA, BETA,
                                              GAM, ACC, A, XYZ, XX, VEC, FF, MAXK,
                                              MAXT, FUN, FUNT, IERR) 

   Параметры 

   Версии:  нет 

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

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

               ALFA = 1
      0.4 ≤ BETA ≤ 0.6
      2.8 ≤ GAM  ≤ 3.0 

           SUBROUTINE  FUN (X, F, FE)

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

           SUBROUTINE  FUNT (X, F, FTE)

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

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

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

       SUBROUTINE  F0 (X, F, FE)
       DIMENSION  X(1)
       F = 4.*X(1) - X(2)**2 -12.
       RETURN
       END

   Подпрограмма вычисления функции  T(x)

       SUBROUTINE  T (X, F, FE)
       DIMENSION  X(1)
       F =  25. - X(1)**2 - X(2)**2
       F = F**2
       R = (X(1) - 5.)**2 + (X(2) - 5.)**2 - 16.
       R = - R
       IF(R .LT. 0.) F = F + R**2
       IF(X(1) .LT. 0.) F = F + X(1)**2
       IF(X(2) .LT. 0.) F = F + X(2)**2
       F = SQRT(F)
       RETURN
       END

   Вызывающая программа

       DIMENSION  XYZ(3, 6), VEC(2, 8), XX(2)
       EXTERNAL  F0, T
       DATA  ALFA, BETA, GAM / 1., 0.5, 2./,
      *            N, ITMAX, MAXK /2, 50, 400/
       DATA  ACC, A /1.E - 6, 0.3/, XX(1), XX(2) /1., 1./
       DATA  NMP1, ITMT, MAXT /3, 200, 500/
       CALL  MNBBR (N, NMP1, ITMAX, ITMT, ALFA, BETA, GAM, ACC, 
      *                          A, XYZ, XX, VEC, FF, MAXK, MAXT, F0, T, IERR)

Результаты:

      IERR   =  65
      FF       =  -0.3199231 + 02

      XX(1)  =  1.0012830 - 00
      XX(2)  =  4.8987190 - 00