Текст подпрограммы и версий
mn11r_p.zip 		Тексты тестовых примеров
tmn11r_p.zip

Подпрограмма:  MN11R (модуль MN11R_p)

Назначение

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

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

Решается задача квадратичного программирования 

     min  { Q(x) = (Gx, x) + (h, x)  |  a ≤ x ≤ b } ,

где  G - симметричная матрица размерности  n * n ,  x, h, a, b - векторы длины  n, причем  ai > - ∞,  bi < +∞,  i = 1, ..., n.

Матрица  G задается в компактной форме, т.е. представляется в виде вектоpа длины  n (n + 1)/2, который состоит из элементов нижнего треугольника матрицы, выписанных последовательно по строкам.

Для решения задачи используется метод покоординатного спуска. Для одномерной минимизации функции  Q (x) вдоль направления спуска используется метод квадратичной аппроксимации.

Некоторая вычисленная точка  xk,  a ≤ xk ≤ b, считается точкой минимума функции  Q (x), если выполнено хотя бы одно из следующих условий:

1.  | xik - xik - 1 | ≤ XE для всех  i = 1, ..., n, где  xk = (x1k, ..., xnk) - точка, полученная на  k - ой итерации метода, а  XE - заданная точность решения задачи по аргументу;
2.  | Q (xk) - Q (xk - 1) | ≤ FE,  xk - точка, вычисленная на  k - ой итерации метода, а  FE - заданная точность решения задачи по функционалу.

Пшеничный Б.Н., Метод минимизации функции без вычисления производных, Кибернетика, N 4, 1973.

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

procedure MN11R(var N :Integer; var X :Array of Real;
                var XE :Array of Real; var A :Array of Real;
                var B :Array of Real; var G :Array of Real;
                var H :Array of Real; FSTEP :Real; IPAR :Integer;
                var MAXK :Integer; var F :Real; var FE :Real;
                var KOUNT :Integer; var I0 :Array of Integer;
                var RM :Array of Real; var IERR :Integer);


   Параметры
N - размерность пространства переменных (тип: целый);
X - вещественный вектоp длины  N: при обращении к подпрограмме содержит заданную начальную точку поиска, на выходе содержит точку минимума функции  Q (x);
XE - заданная точность решения задачи по аргументу (тип: вещественный);
A - вещественный вектоp длины  N, задающий ограничения снизу на переменные;
B - вещественный вектоp длины  N, задающий ограничения свеpху на переменные;
G - вещественный вектоp длины  N (N + 1)/2, содержащий компактную запись матрицы  G;
H - вещественный вектоp длины  N, содержащий компоненты вектоpа  h;
FSTEZ - начальная длина шага (тип: вещественный);
IPAR - параметр, управляющий вариантом покоординатного спуска (тип: целый):
IPAR=1 - используется вариант с ускоpенным дроблением шага;
MAXK - целая переменная, при обращении к подпрограмме содержащая заданное максимально допустимое число вычислений функции, на выходе - фактически выполненное число вычислений функции;
F - вещественная переменная, содержащая вычисленное минимальное значение  Q (x);
FE - заданная точность решения задачи по функционалу (тип: вещественный);
KOUNT - целая переменная, содержащая число фактически выполненных итераций метода;
I0 - целочисленный вектоp длины  N, используемый как рабочий;
RM - вещественный вектоp длины 4 * N + 11, используемый как рабочий;
IERR - целая переменная, указывающая причину окончания процесса:
IERR= 0 - найден минимум с заданной точностью по аргументу или по функционалу;
IERR= 4 - выполнено заданное максимальное число вычислений функции, но точность не была достигнута. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

Используются служебные подпрограммы: MNP11, MNP13, MN214, MN215, MNP16.

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

      Найти  min  { Q(x) = (Gx, x) + (h, x)  |  a ≤ x ≤ b } ,  где


Unit TMN11R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MN11R_p;

function TMN11R: String;

implementation

function TMN11R: String;
var
I,KOUNT,IERR,_i :Integer;
F :Real;
IO :Array [0..9] of Integer;
RM :Array [0..50] of Real;
const
N :Integer = 10;
FE :Real = 5.0E-10;
ХЕ :Array [0..9] of Real = ( 5.E-10,5.E-10,5.E-10,5.E-10,5.E-10,5.E-10,5.E-10,
5.E-10,5.E-10,5.E-10 );
FSTEZ :Real = 1.0;
IPAR :Integer = 1;
МАХК :Integer = 1000;
G :Array [0..54] of Real = ( 100.0,0.5,100.0,0.0,0.5,100.0,0.0,0.0,0.5,100.0,
0.0,0.0,0.0,0.0,20.0,0.0,0.0,0.0,0.0,0.5,20.0,0.0,
0.0,0.0,0.0,0.0,0.5,20.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,3.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.5,3.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0 );
H :Array [0..9] of Real = ( -202.0,-202.0,-202.0,-200.0,-42.0,-42.0,-40.0,
-8.0,-6.0,-2.0 );
A :Array [0..9] of Real = ( -2.0,-2.0,-2.0,-2.0,-2.0,-2.0,-2.0,-2.0,-2.0,
-2.0 );
B :Array [0..9] of Real = ( 2.0,2.0,2.0,2.0,2.0,2.0,2.0,2.0,2.0,2.0 );
X :Array [0..9] of Real = ( -1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0 );
begin
Result := '';  { результат функции }
MN11R(N,X,XE,A,B,G,H,FSTEZ,IPAR,MAXK,F,FE,KOUNT,
     IO,RM,IERR);
Result := Result + Format('%s',['  IERR=']);
Result := Result + Format('%4d ',[IERR]);
Result := Result + Format('%s',['  KOUNT=']);
Result := Result + Format('%4d ',[KOUNT]);
Result := Result + Format('%s',['  MAXK=']);
Result := Result + Format('%4d ',[MAXK]);
Result := Result + Format('%s',['        МАССИВ X' + #$0D#$0A]);
Result := Result + #$0D#$0A;
for _i:=0 to 9 do
 begin
  Result := Result + Format('%20.16f ',[X[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%20.16f ',[F]) + #$0D#$0A;
UtRes('TMN11R',Result);  { вывод результатов в файл TMN11R.res }
exit;
end;

end.

Результаты:
      
       IERR  =  0

       KOUNT  =  193
       MAXK  =  306

       X(I)  =  (1.0053,  0.999574,  1.000782,  0.995092,  1.025024, 
                     1.001971,  0.975006,  1.199397,  0.800848,  0.998825)

       F  =  - 473.2299