БЧА НИВЦ МГУ. MNB8R. Задача безусловной минимизации функции многих переменных

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/mn/mnb8r.htm
Дата изменения: Thu Apr 30 08:03:23 2015
Дата индексирования: Sun Apr 10 00:46:26 2016
Кодировка: Windows-1251

Текст подпрограммы и версий ( Фортран ) mnb8r.zip mnb8d.zip	Тексты тестовых примеров ( Фортран ) tmnb8r.zip tmnb8d.zip
Текст подпрограммы и версий ( Си ) mnb8r_c.zip mnb8d_c.zip	Тексты тестовых примеров ( Си ) tmnb8r_c.zip tmnb8d_c.zip
Текст подпрограммы и версий ( Паскаль ) mnb8r_p.zip , mnb8e_p.zip	Тексты тестовых примеров ( Паскаль ) tmnb8r_p.zip , tmnb8e_p.zip

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

Назначение

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

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

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

    min  φ (x⁰ + α s) ,   x⁰ ∈ E_n ,   s ∈ E_n ,   α ∈ R ,
     ^α

используется метод золотого сечения. При этом предполагается, что задан отрезок [a, b] изменения параметра α такой, что функция φ (x), рассмотренная вдоль направления s, принимает на [a, b] свое минимальное значение.

В.Г.Карманов, Математическое программирование, Изд - во "Hаука", M., 1975, стp.153 - 155.

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

    SUBROUTINE  MNB8R (N, X, S, XX, FUN, AA, BB, EPSX, EPS,
                                             ITMAX, MAXK, FMIN, XMIN, KOUNT,
                                             ITER, NACC, IERR)

   Параметры

N -	размерность пространства переменных (тип: целый);
X -	вещественный вектоp длины N, задающий начальную точку x⁰ поиска одномерного минимума;
S -	вещественный вектоp длины N, задающий направление поиска;
XX -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
FUN -	имя подпрограммы вычисления значения минимизиpуемой функции;
AA -	нижняя граница интервала, содержащего точку минимума (тип: вещественный);
BB -	верхняя граница интервала, содержащего точку минимума (тип: вещественный);
EPSX -	заданная точность вычисления точки минимума по аpгументу (тип: вещественный);
EPS -	заданная точность вычисления минимума по функционалу (тип: вещественный);
ITMAX -	заданное максимально допустимое число итераций метода (тип: целый);
MAXK -	заданное максимально допустимое число вычислений функции (тип: целый);
FMIN -	вещественная переменная, на выходе из подпрограммы содержащая вычисленное максимальное значение функции;
XMIN -	вещественная переменная, на выходе из подпрограммы содержащая значение шага α до точки минимума по направлению;
KOUNT -	целая переменная, на выходе из подпрограммы содержащая выполненное число вычислений функции;
ITER -	целая переменная, на выходе из подпрограммы содержащая выполненное число итераций;
NACC -	целая переменная, задающая признак варианта алгоритма:

NACC=1 -	на каждой итерации вычисляется только одна новая контрольная точка;
NACC=2 -	для каждого нового интервала вычисляются обе контрольные точки (см. замечания по использованию);

IERR -

целая переменная, служащая для сообщения об ошибках и причинах окончания поиска:

IERR= 1 -	достигнута точность EPS;
IERR= 2 -	достигнута точность EPSX;
IERR=65 -	заданная точность EPSX ≤ 0;
IERR=66 -	заданные значения AA, BB, и EPSX таковы, что либо BB ≤ AA, либо (BB - AA) < EPSX;
IERR=67 -	выполнено ITMAX итераций, но ни EPSX, ни EPS не достигнуты;
IERR=68 -	выполнено MAXK вычислений функции, но ни EPSX, ни EPS не достигнуты.

   Версии

MNB8D -

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

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

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

В подпрограмме MNB8D и подпрограмме FUN параметры X, S, XX, AA, BB, EPSX, EPS, FMIN, XMIN, F, FE должны иметь тип DOUBLE PRECISION. Тип остальных параметров не меняется.

Подпрограмма FUN составляется пользователем.

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

           SUBROUTINE  FUN (X, F, FE)

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

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

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

На очередной итерации метода на интервале [a^k, b^k] фиксиpуются две контрольные точки v₁ и v₂, такие что a^k < v₁ < v₂ < b^k.

При NACC = 1 в качестве одной из точек (v₁ или v₂) используется точка, вычисленная на пpедыдущей итерации. При этом погрешность вычислений может накапливаться от итерации к итерации. При NACC = 2 на каждой итерации v₁ и v₂ вычисляются заново, однако число вычислений функции на каждой итерации удваивается.

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

    min  φ (x⁰ + α s) ,   x⁰ ,   s ∈ E₁ ,    x⁰ = 0.0 ,   s = 1.0
      ^α 
    φ (x)  =  100*e^-x + x 
    Оптимальное значение   α^*  =  - ln(0.01)
    φ (x⁰ + α^* s)  =  1 - ln(0.01)

       DIMENSION  X(1), S(1), XX(1)
       EXTERNAL  FUNC
       DATA  N, X(1), S(1) /1, 0., 1./
       DATA  AA, BB, EPS, EPSX /4.2, 4.8, 1.E-16, 1.E-6/
       DATA  ITMAX, MAXK, NACC /100, 100, 1/
       CALL  MNB8R (N, X, S, XX, FUNC, AA, BB, EPSX, EPS, ITMAX,
      *                         MAXK, FMIN, XMIN, KOUNT, ITER, NACC, IERR)

       SUBROUTINE  FUNC (X, F, FE)
       DIMENSION  X(1)
       F = 100.*EXP(-X(1)) + X(1)
       RETURN
       END

Результаты:

      IERR  =  1
      ITER  =  14

      FMIN  =  5.605170 + 00
      XMIN  =  4.605681 + 00

      KOUNT  =  15