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

Подпрограмма:  MNB2R (модуль MNB2R_p)

Назначение

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

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

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

     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.

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

procedure MNB2R(N :Integer; var X :Array of Real;
                var S :Array of Real; var XX :Array of Real;
                var A :Real; var B :Real; EPS :Real; var C :Real;
                var FC :Real; MAXK :Integer; FUN :Proc_F1_MN;
                var IERR :Integer);

Параметры

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 составляется пользователем. Первый оператор подпрограммы должен иметь вид:

      procedure FUN (var X :Array of Real; var F :Real; FE :Real);

        Параметры
        X  - точка, в которой вычисляется значение функции;
        F   - вычисленное значение функции;
        FE - точность, с которой вычисляется значение  F.
Параметp FE не должен переопределяться в теле подпрограммы FUN.

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

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

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

Unit TMNB2R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNB2R_p, MNB2R_p;

function TMNB2R: String;

implementation

function TMNB2R: String;
var
IERR :Integer;
C,FC :Real;
X :Array [0..0] of Real;
S :Array [0..0] of Real;
ХХ :Array [0..0] of Real;
const
N :Integer = 1;
A :Real = -2.0;
B :Real = 1.0;
EPS :Real = 1.0E-05;
МАХК :Integer = 20;
begin
Result := '';  { результат функции }
{ прототип оператора DАТА на FORTRANе  }
X[0] := 0.0;
S[0] := 1.0;
MNB2R(N,X,S,XX,A,B,EPS,C,FC,MAXK,FMNB2R,IERR);
Result := Result + Format('%s',[' C=']);
Result := Result + Format('%20.16f ',[C]);
Result := Result + Format('%s',['  FC=']);
Result := Result + Format('%20.16f ',[FC]);
Result := Result + Format('%s',['  IERR=']);
Result := Result + Format('%2d ',[IERR]) + #$0D#$0A;
UtRes('TMNB2R',Result);  { вывод результатов в файл TMNB2R.res }
exit;
end;

end.

Unit fmnb2r_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;

procedure fmnb2r(var X :Array of Real; var F :Real; FE :Real);

implementation

procedure fmnb2r(var X :Array of Real; var F :Real; FE :Real);
label
_10,_20,_30;
begin
if ( X[0]+1.0 ) < 0
 then goto _10
 else if ( X[0]+1.0 ) > 0
       then goto _20
       else goto _10;
_10:
F := Log10(-X[0]);
goto _30;
_20:
F := IntPower(X[0],3)+1.0;
_30:
end;

end.

Результаты:

      IERR  =   0
      C        =  -1.00000095
      FC      =   4.14175E-7