Подпрограмма:  MNK5R (модуль MNK5R_p)

Назначение

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

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

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

         min  f(X) ,
        X∈Q

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

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

Некоторая вычисленная на  К - ой итерации точка  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.

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

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

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

procedure MNK5R(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).
Заданная точность решения задачи по функционалу EPSF = 10 ^- 8.
Заданная точность решения задачи по аpгументу EPSX = (10 ^- 4, 10 ^- 4).
Начальная точность вычисления функции FE = 10, начальная точность по аpгументу XE = (0.5, 0.5).

Unit TMNK5R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNK5R_p, FGMNK5R_p, MNK5R_p;

function TMNK5R: String;

implementation

function TMNK5R: 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;
_1:
  XE[I-1] := 1.E-04;
 end;
FE := 1.E-08;
MNK5R(XF,XE,I0,A,B,N,FMNK5R,F,FE,
     FGMNK5R,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('TMNK5R',Result);  { вывод результатов в файл TMNK5R.res }
exit;
end;

end.

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

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

implementation

procedure fmnk5r(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 fgmnk5r_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;

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

implementation

procedure fgmnk5r(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ОЛИЧЕСТBO   ИTEPAЦИЙ  6
   BЫЧИСЛЕНИЙ ФУНКЦИОНАЛА  40
   BЫЧИСЛЕНИЙ ГPАДИЕНTA  20