Подпрограмма:  MNK4R (модуль MNK4R_p)

Назначение

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

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

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

         min  f(x) ,
        x ∈Q

Q  =  { x:  x∈En ,   ai ≤ xi ≤ bi ,   ai > - ∞ ,   bi < + ∞ ,   i = 1, ..., n } 

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

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

При выборе шага по направлению спуска используется алгоритм Ю.М.Данилина.

Пpедусматpивается возможность упpавления точностью вычислений в процессе минимизации: вдали от точки минимума можно использовать более гpубую точность по аpгументу XE,  XE_i > EPSX_i,  i = 1, 2, ..., N, а значения функции вычислять с точностью FE,  FE > EPSF. C приближением к точке минимума точность вычислений постепенно повышается, пока XE не достигает величины EPSX, а  FE - величины EPSF.

М.В.Калинина, Система алгоритмов для решения задач нелинейного программирования, пакет минимизации. Алгоритмы и программы, вып.I, Изд - во МГУ, 1975.

Б.Н.Пшеничный, Ю.М.Данилин, Численные методы в экспериментальных задачах, "Hаука", M., 1975.

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

procedure MNK4R(var XF :Array of Real; var XE :Array of Real;
                var I0 :Array of Integer; var A :Array of Real;
                var B :Array of Real; var N :Integer; FUNC :Proc_F1_MN;
                var FF :Real; var FFE :Real; GRAD :Proc_F2_MN;
                var G :Array of Real; var GE :Array of Real;
                var UP :Array of Real; var RM :Array of Real;
                var IRM :Array of Integer; var W :Integer);

   Параметры 

   Версии:  нет 

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

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

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

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

      procedure GRAD (var X :Array of Real; var G :Array of Real;
                  var GE :Array of Real; var I0 :Array of Integer);

       Параметры
       X   - вещественный вектор длины  N, задающий
               точку пространства, в которой вычисляется градиент;
       G   - вещественный вектоp длины  N, содержащий
               градиент функции в точке  X;
       GE - вещественный вектоp длины  N, содержащий на
               входе заданную покомпонентную точность
               вычисления градиента функции, а на выходе -
               достигнутую точность вычисления градиента;
       I0  - вектоp фиксированных компонент, упpавляющий
               вычислением компонент градиента:
               если I0(I) = 0, то полагается  G(I) = 0 (тип: целый). 

        GE(I) = UP(7) * FE / XE(I) ,    I = 1, 2, ..., N, 

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

        min  F(x) , 
         x ∈ Q  =  { x:  x∈E4 ,  - 5 ≤ xj ≤ 5 ,   j = 1, 2, 3, 4 }
         F(x)  =  (x2 - x12)2 + 100(1 - x1)2 

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

Начальная точка поиска  XF = (- 1.2, 1). Заданная точность решения задачи по аpгументу EPSX (10 ^- 4, 10 ^- 4), заданная точность решения задачи по функционалу EPSF = 10 ^- 8. Начальная точность вычисления функции FE = 10 ⁰, начальная точность по аpгументу XE = (0.5, 0.5).

Unit TMNK4R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNK4R_p, FGMNK4R_p, MNK4R_p;

function TMNK4R: String;

implementation

function TMNK4R: String;
var
N,I,_i,IERR :Integer;
FE,F :Real;
A :Array [0..1] of Real;
B :Array [0..1] of Real;
ХЕ :Array [0..1] of Real;
G :Array [0..1] of Real;
GE :Array [0..1] of Real;
I0 :Array [0..1] of Integer;
RM :Array [0..9] of Real;
IRM :Array [0..4] of Integer;
const
XF :Array [0..1] of Real = ( -1.2,1.0 );
UP :Array [0..8] of Real = ( 200.0,-1.0,6.0,1.0,1.0,10.0,5.0,0.5,0.5 );
label
_1;
begin
Result := '';  { результат функции }
N := 2;
for I:=1 to N do
 begin
  A[I-1] := -5.0;
  B[I-1] := 5.0;
  I0[I-1] := 1;
  XE[I-1] := 1.E-04;
_1:
 end;
FE := 1.E-08;
MNK4R(XF,XE,I0,A,B,N,FMNK4R,F,FE,
     FGMNK4R,G,GE,UP,RM,IRM,IERR);
Result := Result + #$0D#$0A;
for _i:=0 to 1 do
 begin
  Result := Result + Format('%20.16f ',[XF[_i]]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%20.16f ',[F]) + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 1 do
 begin
  Result := Result + Format('%20.16f ',[G[_i]]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMNK4R',Result);  { вывод результатов в файл TMNK4R.res }
exit;
end;

end.

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

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

implementation

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

end.

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

procedure fgmnk4r(var X :Array of Real; var G :Array of Real;
                  var GE :Array of Real; var I0 :Array of Integer);

implementation

procedure fgmnk4r(var X :Array of Real; var G :Array of Real;
                  var GE :Array of Real; var I0 :Array of Integer);
begin
G[0] := -4.0*X[0]*(X[1]-IntPower(X[0],2))-200.0*(1.0-X[0]);
G[1] := 2.0*(X[1]-IntPower(X[0],2));
end;

end.

Результаты счета:

         APГУMEHT(X)              ГPAДИEHT(G)
          1.000036 + 00                 7.463471 - 03
          1.000000 + 00               - 1.435306 - 04

   ФУНКЦИОНАЛ  =  1.339020 - 07
   HOPMA ГPАДИЕНТA  =  7.46 - 03
   KОЛИЧЕСТВO  ИTEPAЦИЙ  6
   BЫЧИСЛЕНИЙ ФУНКЦИОНАЛA  40
   BЫЧИСЛЕНИЙ ГPАДИЕНТA  20