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

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

Назначение

Минимизация функции многих переменных по заданному направлению на заданном отрезке методом деления пополам (дихотомический поиск).

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

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

     min  φ (x0 + λ s) ,   a0 ≤ λ ≤ b0 ,
       λ

где  x0, s ∈ En,   a0, b0, λ ∈ E1, используется метод деления отрезка пополам.

Hа каждой итерации метода строится очередной отрезок  [ak, bk] такой, что  [ak bk] ⊂ [ak - 1, bk - 1] ⊂ ... ⊂ [a0, b0] и  λ* ∈ [ai, bi] для всех  i, где λ* - точка минимума  φ (x) по направлению  S.

Вычисления заканчиваются, если для некоторого  k длина отрезка  [ak, bk] меньше заданного числа  ε > 0. Функция  φ предполагается строго квазивыпуклой по направлению  S.

B.A.Березнев. Алгоритм дихотомического поиска минимума унимодальной функции на отрезке. - Оптимизация и упpавление. М.: МГУ, 1982.

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

    int mnb2r_c (integer *n, real *x, real *s, real *xx, real *a,
            real *b, real *eps, real *c, real *fc, integer *maxk, S_fp fun, 
            integer *ierr)

   Параметры
n - разность пространства переменных (тип: целый);
x - вещественный вектоp длины  n, задающий начальную точку поиска минимума по направлению;
s - вещественный вектоp длины  n, задающий направление одномерной минимизации;
xx - вещественный вектоp длины  n, используемый в подпрограмме как рабочий;
a - вещественная переменная, задающая нижнюю гpаницу исходного отрезка неопределенности;
b - вещественная переменная, задающая верхнюю границу исходного отрезка неопределенности;
eps - заданная точность вычисления точки минимума (тип: вещественный);
c - вещественная переменная, содержащая на выходе шаг по направлению  s до вычисленной точки минимума;
fc - вещественная переменная, содержащая на выходе минимальное значение функции по направлению;
maxk - заданное максимальное допустимое число вычислений функции (тип: целый);
fun - имя подпрограммы вычисления значения функции (см. замечания по использованию);
ierr - целая переменная, указывающая пpичину окончания процесса:
ierr= 0 - получено решение с заданной точностью eps;
ierr=65 - выполнено maxk вычислений функции;
ierr=66 - функция не является строго квазивыпуклой. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Длина очередного отрезка неопределенности на  k - й итерации метода pавна (b - a)/2k, поэтому нетpудно определить число вычислений функции, необходимое для сокращения исходного отрезка до длины, меньшей eps. Параметр maxk в связи с этим целесообразно задавать на несколько единиц большим необходимого числа вычислений функции, чтобы избежать зацикливания.

  2. 

Подпрограмма fun составляется пользователем. Первый оператор подпрограммы должен иметь вид: 

            int fun(float *x, float *f, float *fe)

        Параметры
        x  - точка, в которой вычисляется значение функции;
        f   - вычисленное значение функции;
        fe - точность, с которой вычисляется значение  f.
Имя подпрограммы вычисления функции должно быть определено в вызывающей программе в операторе extern. Параметp fe не должен переопределяться в теле подпрограммы fun.

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

    min  φ (x) ,   -2 ≤ x ≤ 1 ,

    φ (x)  =  log(-x) ,  если  x ≤ -1 , 
    φ (x)  =  x3 + 1 ,  если  x > -1.


int main(void)
{
    /* Initialized data */
    static int n = 1;
    static float a = -2.f;
    static float b = 1.f;
    static float x[1] = { 0.f };
    static float s[1] = { 1.f };
    static float eps = 1e-5f;
    static int maxk = 20;

    /* Local variables */
    extern int func_c();
    static int ierr;
    extern int mnb2r_c(int *, float *, float *, float *, float *, float *,
                       float *, float *, float *, int *, U_fp, int *);
    static float c__, fc, xx[1];

    mnb2r_c(&n, x, s, xx, &a, &b, &eps, &c__, &fc, &maxk,
            (U_fp)func_c, &ierr);

    printf("\n %15.7f \n", c__);
    printf("\n %17.7e \n", fc);
    printf("\n %5i \n", ierr);
    return 0;
} /* main */

int func_c(float *x, float *f, float *fe)
{
    /* System generated locals */
    float r__1;

    /* Builtin functions */
    double r_lg10(float *);

    /* Parameter adjustments */
    --x;

    /* Function Body */
    if (x[1] + 1.f <= 0.f) {
        goto l10;
    } else {
        goto l20;
    }
l10:
    r__1 = -x[1];
    *f = (float)r_lg10(&r__1);
    goto l30;
l20:
/* Computing 3rd power */
    r__1 = x[1];
    *f = r__1 * (r__1 * r__1) + 1.f;
l30:
    return 0;
} /* func_c */


Результаты:

      ierr  =   0
      c__      =  -1.00000095
      fc      =   4.14175e-7