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

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

Текст подпрограммы и версий ( Фортран ) mnb2r.zip	Тексты тестовых примеров ( Фортран ) tmnb2r.zip
Текст подпрограммы и версий ( Си ) mnb2r_c.zip	Тексты тестовых примеров ( Си ) tmnb2r_c.zip
Текст подпрограммы и версий ( Паскаль ) mnb2r_p.zip	Тексты тестовых примеров ( Паскаль ) tmnb2r_p.zip

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

Назначение

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

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

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

     min  φ (x₀ + λ s) ,   a₀ ≤ λ ≤ b₀ ,
       ^λ

где x₀, s ∈ E_n, a₀, b₀, λ ∈ E₁, используется метод деления отрезка пополам.

Hа каждой итерации метода строится очередной отрезок [a_k, b_k] такой, что [a_k b_k] ⊂ [a_k - 1, b_k - 1] ⊂ ... ⊂ [a₀, b₀] и λ^* ∈ [a_i, b_i] для всех i, где λ^* - точка минимума φ (x) по направлению S.

Вычисления заканчиваются, если для некоторого k длина отрезка [a_k, b_k] меньше заданного числа ε > 0. Функция φ предполагается строго квазивыпуклой по направлению S.

B.A.Березнев. Алгоритм дихотомического поиска минимума унимодальной функции на отрезке. - Оптимизация и упpавление. М.: МГУ, 1982.

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

    SUBROUTINE  MNB2R (N, X, S, XX, A, B, EPS, C, FC, MAXK,
                                             FUN, IERR)

   Параметры

N -	разность пространства переменных (тип: целый);
X -	вещественный вектоp длины N, задающий начальную точку поиска минимума по направлению;
S -	вещественный вектоp длины N, задающий направление одномерной минимизации;
XX -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
A -	вещественная переменная, задающая нижнюю гpаницу исходного отрезка неопределенности;
B -	вещественная переменная, задающая верхнюю границу исходного отрезка неопределенности;
EPS -	заданная точность вычисления точки минимума (тип: вещественный);
C -	вещественная переменная, содержащая на выходе шаг по направлению S до вычисленной точки минимума;
FC -	вещественная переменная, содержащая на выходе минимальное значение функции по направлению;
MAXK -	заданное максимальное допустимое число вычислений функции (тип: целый);
FUN -	имя подпрограммы вычисления значения функции (см. замечания по использованию);
IERR -	целая переменная, указывающая пpичину окончания процесса:

IERR= 0 -	получено решение с заданной точностью EPS;
IERR=65 -	выполнено MAXK вычислений функции;
IERR=66 -	функция не является строго квазивыпуклой.

   Версии:  нет

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

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

Длина очередного отрезка неопределенности на k - й итерации метода pавна (B - A)/2^k, поэтому нетpудно определить число вычислений функции, необходимое для сокращения исходного отрезка до длины, меньшей EPS. Параметр MAXK в связи с этим целесообразно задавать на несколько единиц большим необходимого числа вычислений функции, чтобы избежать зацикливания.

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

           SUBROUTINE  FUN (X, F, FE)

        Параметры
        X  - точка, в которой вычисляется значение функции;
        F   - вычисленное значение функции;
        FE - точность, с которой вычисляется значение  F.

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

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

    min  φ (x) ,   -2 ≤ x ≤ 1 ,

    φ (x)  =  log(-x) ,  если  x ≤ -1 , 
    φ (x)  =  x³ + 1 ,  если  x > -1.

       DIMENSION  X(1), S(1), XX(1)
       INTEGER  N, MAXK, IERR
       REAL  X, S, XX, A, B, EPS, C, FC
       EXTERNAL  FUNC
       DATA  N, A, B, X(1), S(1), EPS, MAXK /1, -2., 1., 0., 1., 1.E-05, 20/
       CALL  MNB2R (N, X, S, XX, A, B, EPS, C, FC, MAXK, FUNC, IERR)

       SUBROUTINE  FUNC (X, F, FE)
       DIMENSION  X(1)
       IF(X(1) + 1.) 10, 10, 2
  10 F = ALOG10(-X(1))
       GO TO 30
  20 F = X(1)**3 + 1.
  30 RETURN
       END

Результаты:

      IERR  =   0
      C        =  -1.00000095
      FC      =   4.14175E-7