Текст подпрограммы и версий
mne1r_c.zip , mne1d_c.zip 		Тексты тестовых примеров
tmne1r_c.zip , tmne1d_c.zip

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

Назначение

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

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

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

             min  f(x) ,      x ∈ En ,

где f (x) - выпуклая недифференцируемая функция, применяется субградиентный метод последовательной релаксации с построением сопряженных направлений. Для ускорения сходимости и уточнения длины шага может проводиться одномерная минимизация по направлению.

Коннов И.В. Субградиентный метод последовательной релаксации для решения задач оптимизации. Деп.ВИНИТИ, N 531 - 83.

Демьянов В.Ф., Васильев Л.Ф. Недифференцируемая оптимизация. М.: Наука, 1981.

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

    int mne1r_c (real *f, real *fe, S_fp func, real *g, real *ge,
            integer *ierr, integer *i0, integer *n, real *rm, S_fp subg, real *up,
             real *x, real *xe)

   Параметры
f - вещественная переменная, содержащая вычисленное минимальное значение f (x);
fe - заданная точность решения задачи по функции (тип: вещественный);
func - имя подпрограммы вычисления значения функции f (x) (см. замечания по использованию);
g - вещественный вектор длины  n, содержащий субградиент функции  f в вычисленной точке  x;
ge - вещественный вектор длины  n, задающий точность решения задачи по субградиенту;
ierr - целая переменная, указывающая причину окончания процесса;
ierr=1 - найден минимум с заданной точностью по аргументу;
ierr=2 - найден минимум с заданной точностью по функции;
ierr=3 - найден минимум с заданной точностью по субградиенту;
ierr=4 - выполнено максимальное (см. up (4)) количество вычислений функции;
ierr=5 - истекло заданное время, отведенное пользователем на решение задачи (см. up (5));
ierr=6 - произошло замедление счета (см.замечания по использованию);
i0 - целый вектор длины  n, задающий фиксированные на время минимизации компоненты вектора  x: если i0 (i) = 0, то i - ая компонента вектора  x остается равной своему начальному значению;
n - размерность пространства переменных (тип: целый);
rm - вещественный вектор длины 2n, используемый в подпрограмме как рабочий;
subg - имя подпрограммы вычисления субградиента функции f (x) (см.замечания по использованию);
up - вещественный вектор длины 9, задающий управляющие параметры алгоритма;
up(1) - заданная начальная длина шага;
up(2) - заданная константа дробления шага, 0 < up (2) < 1;
up(3) - заданный коэффициент, определяющий величину убывания функции на одной итерации, 0 < up (3) < 1;
up(4) - заданное максимально допустимое количество вычислений функции;
up(5) - время, отведенное центральному процессору на решение задачи, задается пользователем в секундах;
up(6),up(7) - параметры, формирующие критерий замедления счета; рекомендуется задавать на входе up (6) = 0, тогда эти параметры вычисляются автоматически внутри подпрограммы;
up(8) - заданный параметр, определяющий, через сколько итераций проводится одномерная минимизация (см. замечания по использованию);
up(9) - заданный признак печати сообщения об окончании счета: up (9) = 1 - печатается сообщение о выполнившемся критерии останова, up (9) = 0 - сообщение не печатается;
x - вещественный вектор длины  n; при обращении к подпрограмме содержит заданную начальную точку поиска, при выходе содержит точку минимума функции f (x);
xe - вещественный вектор длины  n, задающий точность решения задачи по аргументу. 
   Версии
mne1d_c - решение задачи безусловной минимизации выпуклой недифференцируемой функции многих переменных субградиентным методом, при этом вычисления проводятся с удвоенной точностью. Параметры f, fe, g, ge, rm, x, xe подпрограммы mne1d_c и подпрограмм func, subg должны иметь тип double. Тип остальных параметров не изменяется. 
   Вызываемые подпрограммы
mnb8r_c - подпрограмма минимизации функции многих переменных по заданному направлению методом золотого сечения; вызывается при работе подпрограммы mne1r_c;
mnb8d_c - подпрограмма минимизации по заданному направлению методом золотого сечения; вычисления проводятся с двойной точностью; вызывается при работе подпрограммы mne1d_c 
   Замечания по использованию
  Подпрограммы func и subg составляются пользователем.
Первый оператор подпрограммы вычисления функции должен иметь вид: 
   int func(float *x, float *f, float *fe)
Параметры:
x - вещественный вектор длины  n, содержащий текущую точку пространства, в которой вычисляется значение функции;
f - вещественная переменная, содержащая вычисленное значение функции в точке  x;
fe - вещественная переменная, содержащая на входе заданную точность вычисления значения функции в точке  x, а на выходе - достигнутую точность.
  Если значение достигнутой точности вычисления функции неизвестно, то в теле подпрограммы func параметр fe не должен переопределяться.
Первый оператор подпрограммы вычисления субградиента должен иметь вид:
    int subg(float *x, float *g, float *ge, int *i0)
Параметры:
x - вещественный вектор длины  n, содержащий текущую точку пространства, в которой вычисляется субградиент;
g - вещественный вектор длины  n, содержащий вычисленный субградиент (произвольный из множества субградиентов) в точке  x;
ge - вещественный вектор длины  n, содержащий на входе заданную покомпонентную точность вычисления субградиента функции, а на выходе - достигнутую точность вычисления субградиента;
i0 - целый вектор фиксированных компонент, управляющий вычислением компонент субградиента: если i0 (i) = 0, то полагается g (i) = 0.
  Если значение достигнутой точности ge (i) для некоторого  i неизвестно, то в теле подпрограммы subg параметр ge (i) не должен переопределяться.

Имена подпрограмм вычисления значения функции и ее субградиента должны быть определены в вызывающей программе оператором extern.

Не рекомендуется проводить одномерную минимизацию на каждой итерации, так как построенное направление не является, вообще говоря, направлением наискорейшего убывания.

Рекомендуется задавать up (8) > 4, либо up (8) = 0 (в этом случае одномерная минимизация не проводится).

Для лучшего согласования управляющих параметров в процессе счета полезно задавать начальный шаг достаточно большим.

Признак выхода из подпрограммы по замедлению счета ierr = 6 указывает на слишком медленную сходимость алгоритма, то есть изменение функции на каждой итерации оказывается на несколько порядков меньше, чем разность между текущим значением и минимальным.

При работе подпрограммы mne1r_c используются следующие служебные подпрограммы:
mne1r1_c, mne1r2_c, mne1r3_c, mne1r4_c, mne1r5_c, mmkrit, mnr1n_c, utmn05_c, utmne1_c,
а также внешняя структура с именем mmkric_ , содержащая элементы zf, kr, akr, df.

При работе подпрограммы mne1d_c используются следующие служебные подпрограммы:
mne1d1_c, mne1d2_c, mne1d3_c, mne1d4_c, mne1d5_c, mmkrid_c, mnr1nd_c, utmn05_c, utmne1_c,
а также внешняя структура с именем mmkrd_ , содержащая элементы zf, kr, akr, df

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

Найти минимальное значение функции  
      f(x)  =  | x1 + 2 | + | 4x2 - 6 | ;

   начальное приближение  x  =  (- 3., 1.)

int main(void)
{
    /* Initialized data */
    static float fe = 1e-7f;
    static float xe[2] = { 1e-8f,1e-8f };
    static float ge[2] = { .001f,.001f };
    static float up[9] = { 5.f,.7f,.3f,500.f,600.f,0.f,0.f,10.f,1.f };
    static int i0[2] = { 1,1 };
    static int n = 2;
    static float x[2] = { -3.f,1.f };

    /* Local variables */
    static int ierr;
    extern int mne1r_c(float *, float *, U_fp, float *, float *, int *,
                       int *, int *, float *, U_fp, float *, float *, float *);
    static float f, g[2];
    extern int conus_c();
    static float rm[4];
    extern int subcon_c();

    mne1r_c(&f, &fe, (U_fp)conus_c, g, ge, &ierr, i0, &n, rm, (U_fp)subcon_c,
            up, x, xe);

    printf("\n %13.7f %13.7f \n", x[0], x[1]);
    printf("\n %13.7f \n", f);
    printf("\n %13.7f %13.7f \n", g[0], g[1]);
    printf("\n %5i \n", ierr);
    printf("\n %9.3f \n", up[4]);
    return 0;
} /* main */

int conus_c(float *x, float *f, float *fe)
{
    /* Initialized data */
    static float a[2] = { 1.f,4.f };
    static float b[2] = { -2.f,6.f };

    static int i__;
    static float arg;

    /* Parameter adjustments */
    --x;

    /* Function Body */
    *f = 0.f;
    for (i__ = 1; i__ <= 2; ++i__) {
        arg = a[i__ - 1] * x[i__] - b[i__ - 1];
        *f += abs(arg);
/* l1: */
    }
    return 0;
} /* conus_c */

int subcon_c(float *x, float *g, float *ge, int *i0)
{
    /* Initialized data */
    static float a[2] = { 1.f,4.f };
    static float b[2] = { -2.f,6.f };

    /* Builtin functions */
    double r_sign(float *, float *);

    /* Local variables */
    static int i__;
    static float arg;

/*  Вычисляет субградиент ф-ции conus */
    /* Parameter adjustments */
    --i0;
    --ge;
    --g;
    --x;

    /* Function Body */
    for (i__ = 1; i__ <= 2; ++i__) {
        if (i0[i__] == 0) {
            goto l2;
        }
        arg = a[i__ - 1] * x[i__] - b[i__ - 1];
        g[i__] = (float)r_sign(&c_b14, &arg) * a[i__ - 1];
        goto l1;
l2:
        g[i__] = 0.f;
l1:
        ;
    }
    return 0;
} /* subcon_c */
 

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

   Библиотека НИВЦ МГУ, подпрограмма mne1r_c
   Выполнено максимальное количество вычислений функции

          x  = - 2.0000001     1.5000000     
          f  =   0.0000001 

          ierr  =  4