Текст подпрограммы и версий ( Фортран )
mn11r.zip 		Тексты тестовых примеров ( Фортран )
tmn11r.zip
Текст подпрограммы и версий ( Си )
mn11r_c.zip 		Тексты тестовых примеров ( Си )
tmn11r_c.zip
Текст подпрограммы и версий ( Паскаль )
mn11r_p.zip 		Тексты тестовых примеров ( Паскаль )
tmn11r_p.zip

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

Назначение

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

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

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

     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.

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

    SUBROUTINE  MN11R (N, X, XE, A, B, G, H, FSTEP, IPAR, MAXK,
                                              F, FE, KOUNT, I0, RM, IERR) 
   Параметры
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;
FSTEP - начальная длина шага (тип: вещественный);
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 } ,  где

    G  - трехдиагональная матрица, у которой
         верхняя и нижняя диагонали равны
         ( 0.5, 0.5, 0.5, 0., 0.5, 0.5, 0., 0.5, 0. ) ,
         а главная диагональ равна
         ( 100., 100., 100., 100., 20., 20., 20., 3., 3., 1. ) .

    h  =  ( - 202; - 202; - 202; - 200; - 42; - 42; - 40; - 8; - 6; - 2 ) ;

    ai  =  - 2 ,   i  =  1 , ..., 10 ;
    bi  =    2 ,   i  =  1 , ..., 10 .

   Начальная точка    xi0  =  - 1 ,   i = 1, ..., 10 .    Q(x0)  =  1419 .

   Точка минимума    x* ≈ (1.0050; 1.0000; 1.0000; 0.9950; 1.0250;
                                            1.0000; 0.9750; 1.2000; 0.8000; 1.0000)
    Q(x*) ≈ - 473.2300

       INTEGER  I, N, IPAR, MAXK, KOUNT, I0, IERR
       REAL  A, B, G, H, F, FE, FSTEP, RM, X, XE
       DIMENSION  A(10), B(10), H(10), I0(10), X(10), XE(10), G(35), 
      *                      RM(51)
       DATA  N, FE, XE /10, 5.E - 10, 10*5.E - 10/
       DATA  FSTEP, IPAR, MAXK /1., 1, 1000/
       DATA  G /100., 0.5, 100., 0., 0.5, 100., 0., 0., 0.5, 100., 4*0., 20., 
      *               4*0., 0.5, 20., 5*0., 0.5, 20., 7*0., 3., 7*0., 0.5, 3., 
      *               9*0., 1./
       DATA  H /- 202., - 202., - 202., - 200., - 42., - 42., - 40., - 8., 
      *               - 6., - 2./
       DATA  A, B, X /10* - 2., 10*2., 10* - 1./
       CALL  MN11R (N, X, XE, A, B, G, H, FSTEP, IPAR, MAXK, F, FE,
      *                          KOUNT, I0, RM, IERR)

Результаты:
      
       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