Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/cat/mn/mn06r.htm
Дата изменения: Thu Nov 26 13:47:14 2015
Дата индексирования: Sun Apr 10 01:24:42 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. MN06R. Задача минимизации функции многих переменных с ограничениями
Текст подпрограммы и версий ( Фортран )
mn06r.zip 		Тексты тестовых примеров ( Фортран )
tmn06r.zip
Текст подпрограммы и версий ( Си )
mn06r_c.zip 		Тексты тестовых примеров ( Си )
tmn06r_c.zip

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

Назначение

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

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

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

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

используется метод покоординатного спуска.

Некоторая вычисленная точка  xk ∈ Q считается точкой минимума  f (x) на  Q, если выполнено хотя бы одно из следующих условий:

1.  | xjk - xjk - 1 | ≤ EPSX j  для всех  j = 1, ..., n, где  xk = (x1k, ..., xnk) - точка, полученная на  k - ой итерации метода, а EPSX - заданный вектоp точности решения задачи по аpгументу;
2.  | f (xk) - f (xk - 1) | ≤ EPSF, где  xk - точка, вычисленная на  k - той итерации метода, а EPSF - заданная точность решения задачи по функционалу.

Жданов B.A., Алгоритмы покоординатного спуска. Пакет минимизации. Алгоритмы и программы. Изд - во МГУ, вып.2, 1976.

Пшеничный Б.Н., Метод минимизации функции без вычисления производных, Кибернетика, N 4, 1973.

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

    SUBROUTINE  MN06R (N, X, XE, I0, A, B, FUN, F, FE, UP,
                                             RM, IERR) 
   Параметры
N - размерность пространства переменных (тип: целый);
X - вещественный вектоp длины  N: при обращении к подпрограмме содержит заданную начальную точку поиска, на выходе содержит точку минимума функции  f (x);
XE - вещественный вектоp длины  N, содержащий заданную точность решения задачи по аpгументу;
I0 - целый вектоp длины  N, используемый в подпрограмме как рабочий;
A - вещественный вектоp длины  N, задающий ограничения снизу на переменные;
B - вещественный вектоp длины  N, задающий ограничения свеpху на переменные;
FUN - имя подпрограммы вычисления значения функции  f (x) (см. замечания по использованию);
F - вещественная переменная, содержащая вычисленное минимальное значение  f (x);
FE - заданная точность решения задачи по функционалу (тип: вещественный);
UP - вещественный вектоp длины (N + 3), первые N + 1 компонент которого используются в подпрограмме как рабочие;
UP(N+2) - начальная длина шага;
UP(N+3) - параметр, упpавляющий вариантом алгоритма покоординатного спуска: если UP (N + 3) = 1, то используется вариант с ускоpенным дроблением шага;
RM - вещественный вектоp длины (3 * N + 8), последние 3 * N + 6 компонент которого используются в подпрограмме как рабочие;
RM(1) - на выходе из подпрограммы содержит число фактически выполненных итераций метода;
RM(2) - при обращении к подпрограмме содержит заданное максимально допустимое число вычислений функции, на выходе - фактически выполненное число вычислений функции;
IERR - целочисленная переменная, указывающая пpичину окончания процесса:
IERR=12 - найден минимум с заданной точностью по аpгументу и по функционалу;
IERR= 4 - выполнено заданное максимальное число вычислений функции, но точность не была достигнута. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

           SUBROUTINE  FUN (X, F, EPSF)

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

Параметр EPSF не должен переопределяться в теле подпрограммы FUN и может не использоваться для вычисления  f (x). Имя подпрограммы вычисления значения функции должно быть определено в вызывающей программе оператором EXTERNAL.

Если решается задача безусловной минимизации (т.е.  Q = En), то следует задать  A (J) = - C и  B (J) = C, где  C - достаточно большое представимое в машине вещественное число.

Используются служебные подпрограммы: MN061, MN062, MN063, MN064.

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

    min  f(x) ,
x ∈ Q  =  { x:  x ∈ E4,  -3 ≤ xj ≤ 4,  j = 1, ..., 4 }
f(x)  =  (x1 + 10x2)2 + 5(x3 - x4)2 + (x2 - 2x3)4 + 10(x1 - x4)4

Точка условного минимума является внутpенней точкой множества  Q, а именно  x* = (0., 0., 0., 0.),  f (x*) = 0.0 

       DIMENSION  X(4), A(4), B(4), I0(4), UP(7), XE(4), RM(20)
       EXTERNAL  FUNC
       DATA  FE, RM(2), N, XE /1.E-8, 1570., 4, 4*1.E-4/
       DATA  A, B, X /4*-3., 4*4., 3., -1., 0., 1./
       N = 4
       UP(N + 2) = 1.
       UP(N + 3) = 0.
       CALL  MN06R (N, X, XE, I0, A, B, FUNC, F, FE, UP, RM, IERR)

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

       SUBROUTINE  FUNC (X, F, FE)
       DIMENSION  X(4)
       F = ( X(1) + 10.*X(2) )**2 + 5.*( X(3) - X(4) )**2 +
      *     ( X(2) - 2.*X(3) )**4 + 10.*( X(1) - X(4) )**4
       RETURN
       END

Результаты:
                    TOЧKA MИHИMУMA
    -0.480621-01 ,     0.480707-02 ,     -0.204811-01 ,     -0.205545-01

    F  =  0.101415-04

    IERR  =  4
    RM(1)  =  1071
    RM(2)  =  1570