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

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

Назначение

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

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

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

     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.

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

    int mn11r_c (integer *n, real *x, real *xe, real *a, real *b,
            real *g, real *h, real *fstep, integer *ipar, integer *maxk,
            real *f, real *fe, integer *kount, integer *i0, real *rm,
            integer *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_c, mnp13_c, mn214_c, mn215_c, mnp16_c.

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

      Найти  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


int main(void)
{
    /* Initialized data */
    static int n = 10;
    static float b[10] = { 2.f,2.f,2.f,2.f,2.f,2.f,2.f,2.f,2.f,2.f };
    static float x[10] = { -1.f,-1.f,-1.f,-1.f,-1.f,-1.f,-1.f,-1.f,-1.f,-1.f };
    static float fe = 5e-10f;
    static float xe[10] = { 5e-10f,5e-10f,5e-10f,5e-10f,5e-10f,5e-10f,5e-10f,
                           5e-10f,5e-10f,5e-10f };
    static float fstep = 1.f;
    static int ipar = 1;
    static int maxk = 1000;
    static float g[55] = { 100.f,.5f,100.f,0.f,.5f,100.f,0.f,0.f,.5f,100.f,0.f,
            0.f,0.f,0.f,20.f,0.f,0.f,0.f,0.f,.5f,20.f,0.f,0.f,0.f,0.f,0.f,.5f,
            20.f,0.f,0.f,0.f,0.f,0.f,0.f,0.f,3.f,0.f,0.f,0.f,0.f,0.f,0.f,0.f,
            .5f,3.f,0.f,0.f,0.f,0.f,0.f,0.f,0.f,0.f,0.f,1.f };
    static float h__[10] = { -202.f,-202.f,-202.f,-200.f,-42.f,-42.f,-40.f,
                               -8.f,-6.f,-2.f };
    static float a[10] = { -2.f,-2.f,-2.f,-2.f,-2.f,-2.f,-2.f,-2.f,-2.f,-2.f };

    /* Local variables */
    extern int mn11r_c(int *, float *, float *, float *, float *, float *,
                       float *, float *, int *, int *, float *, float *,
                       int *, int *, float *, int *);
    static int ierr;
    static float f;
    static int kount, io[10], i;
    static float rm[51];

    mn11r_c(&n, x, xe, a, b, g, h__, &fstep, &ipar, &maxk, &f, &fe, &kount,
            io, rm, &ierr);

    printf("\n %5i \n", ierr);
    printf("\n %5i \n", kount);
    printf("\n %5i \n", maxk);
    for (i = 0; i <= 5; i += 5) {
         printf("\n %14.6f %14.6f %14.6f %14.6f %14.6f \n",
                x[i], x[i+1], x[i+2], x[i+3], x[i+4]);
    }
    printf("\n %16.7e \n", f);
    return 0;
} /* main */


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