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

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/mn_htm_p/mnb6r_p.htm
Дата изменения: Thu Nov 5 15:20:27 2015
Дата индексирования: Sun Apr 10 02:47:40 2016
Кодировка: Windows-1251

Текст подпрограммы и версий
mnb6r_p.zip , mnb6e_p.zip

Тексты тестовых примеров
tmnb6r_p.zip , tmnb6e_p.zip

Подпрограмма: MNB6R (модуль MNB6R_p)

Назначение

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

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

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

     min  φ (x) ,   x ∈ E_n
      ^x
 используется алгоритм  Нелдера - Мида.

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

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

procedure MNB6R(N :Integer; NP1 :Integer; var ITMAX :Integer;
                var ALFA :Real; var BETA :Real; var GAM :Real;
                var ACC :Real; A :Real; var X :Array of Real;
                var XCEN :Array of Real; var Z :Array of Real;
                var XREF :Array of Real; var XCON :Array of Real;
                var XEX :Array of Real; var XX :Array of Real;
                var FF :Real; var MAXK :Integer; FUN :Proc_F1_MN;
                var IERR :Integer);

   Параметры

N -	размерность пространства переменных (тип: целый);
NP1 -	целая переменная, значение которой на входе в подпpогpамму должно быть pавно N + 1;
ITMAX -	целая переменная, на входе задающая максимально допустимое число итераций алгоритма; на выходе ее значение pавно фактически выполненному числу итераций;
ALFA -	вещественная переменная, задающая параметр метода (см. замечания по использованию);
BETA -	вещественная переменная, задающая параметр метода (см. замечания по использованию);
GAM -	вещественная переменная, задающая параметр метода (см. замечания по использованию);
ACC -	вещественная переменная, задающая точность вычисления минимума по функционалу;
A -	вещественная переменная, задающая размер исходного многогранника (см. замечания по использованию);
X -	вещественный двумеpный массив размера NP1 * N, используемый в подпрограмме как рабочий;
XCEN -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
Z -	вещественный вектоp длины NP1, используемый в подпрограмме как рабочий;
XREF -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
XCON -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
XEX -	вещественный вектоp длины N, используемый в подпрограмме как рабочий;
XX -	вещественный вектоp длины N, на входе задающий начальную точку поиска; на выходе содержит точку с минимальным вычисленным значением функции;
FF -	вещественная переменная, содержащая минимальное вычисленное значение функции;
MAXK -	целая переменная, на входе задающая максимально допустимое число вычислений значения функции; на выходе содержит фактически выполненное число вычислений функции;
FUN -	имя подпрограммы вычисления значения минимизиpуемой функции (см. замечания по использованию);
IERR -	целая переменная, служащая для сообщения о причине окончания процесса; при этом:

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

   Версии:

MNB6E -

Решение задачи безусловной минимизации функции многих переменных без вычисления производной, при этом вычисления проводятся с расширенной (Extended) точностью. Параметры ALFA, BETA, GAM, ACC, A, X, XCEN, Z, XREF, XCON, XEX, XX, FF, F, FE подпрограммы MNB6E и подпрограммы FUN должны иметь тип Extended. Тип остальных параметров не изменяется.

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

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

Параметры ALFA, BETA и GAM являются соответственно параметрами отражения, сжатия и растяжения при построении построении многогранника.

Анализ влияния значений этих параметров на скорость сходимости процесса показывает, что в общем случае целесообразно задавать ALFA = 1, а выбор значений параметpов BETA и GAM подчинить условиям:

           0.4 ≤ BETA ≤ 0.6
           2.8 ≤ GAM  ≤ 3.0

Процесс минимизации начинается с построения правильного симплекса в E_n с начальной точкой поиска в одной из вершин. Размер симплекса определяется значением параметpа A, равного расстоянию между двумя ближайшими веpшинами симплекса.

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

 
        procedure FUN (var X :Array of Real; var F :Real; FE :Real);

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

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

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

    min  { φ (x)  =  ( x₁ - 1 )² + 10 ( x₂ - 1 )² + 100 ( x₃ - 1 )² + 1000 ( x₄ - 1 )² } ,   x ∈ E₂
    x₀  =  ( -1., -2., -3., -4. )
    x^*  =  ( 1., 1., 1., 1. )
    φ (x^*)  =  0.

Unit TMNB6R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNB6R_p, MNB6R_p;

function TMNB6R: String;

implementation

function TMNB6R: String;
var
NP1,I,IERR :Integer;
FF :Real;
X :Array [0..19] of Real;
XCEN :Array [0..3] of Real;
Z :Array [0..4] of Real;
XREF :Array [0..3] of Real;
XCON :Array [0..3] of Real;
ХЕХ :Array [0..3] of Real;
ХХ :Array [0..3] of Real;
const
ALFA :Real = 1.0;
ВЕТА :Real = 0.5;
GАМ :Real = 2.0;
N :Integer = 4;
IТМАХ :Integer = 10000;
МАХК :Integer = 2500;
АСС :Real = 1.0E-09;
A :Real = 1.0;
begin
Result := '';  { результат функции }
{ прототип оператора DАТА на FORTRANе  }
XX[0] := -1.0;
XX[1] := -2.0;
XX[2] := -3.0;
XX[3] := -4.0;
NP1 := N+1;
for I:=1 to N do
 begin
  Result := Result + Format('  X(%3d ) = %20.16f ',
 [I,XX[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
MNB6R(N,NP1,ITMAX,ALFA,BETA,GAM
     ,ACC,A,X,XCEN,Z,XREF,XCON,XEX,XX,FF,MAXK,FMNB6R,IERR);
Result := Result + Format('%s',['  IERR = ']);
Result := Result + Format('%2d ',[IERR]) + #$0D#$0A;
Result := Result + Format('  %4d ',[ITMAX]);
Result := Result + Format('%s',['  ИTEPAЦИЙ']);
Result := Result + Format('  %4d ',[MAXK]);
Result := Result + Format('%s',['  ВЫЧИСЛЕНИЙ ФYHKЦИИ']);
Result := Result + Format('%s',['  F(X) = ']);
Result := Result + Format('%20.16f ',[FF]) + #$0D#$0A;
for I:=1 to N do
 begin
  Result := Result + Format('  X(%3d ) = %20.16f ',
 [I,XX[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMNB6R',Result);  { вывод результатов в файл TMNB6R.res }
exit;
end;

end.

Unit fmnb6r_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;

procedure fmnb6r(var X :Array of Real; var F :Real; FE :Real);

implementation

procedure fmnb6r(var X :Array of Real; var F :Real; FE :Real);
begin
F := IntPower(X[0]-1.0,2)+10*IntPower(X[1]-1.0,2)
    +100.0*IntPower(X[2]-1.0,2)+1000.0*IntPower(X[3]-1.0,2);
end;

end.

Результаты:

      IERR     =  1
      ITMAX  =  199
      MAXK   =  539

      FF    =  0.90732750 - 09
      X(1)  =  0.99998510 + 00
      X(2)  =  0.99999270 + 00
      X(3)  =  0.10000010 + 01
      X(4)  =  0.10000000 + 01