1. Задание
Разработать программу, реализующую систему поиска экстремума функции

f(x₁, x₂ = 1/x₁ + x₁³ — 7x₁² + x₁x₂ — x₂² + 9x₁ + 3x₂ + 12

используя комбинацию многомерного и одномерного методов: метода случайного поиска (спуска) и метода Фибонначи.

Исходный вектор: x⁰=(-2, 0)^T или x⁰=(2, 4)^T

2. Описание методов

2.1 Метод случайного поиска (спуска)

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

Характерной особенностью вычислительной стороны этого метода решения задач математического программирования является то, что применение этих методов неразрывно связано с использованием ЭВМ, в первую очередь потому, что такие задачи являются задачами большого объема и недоступны для ручного счета.

В данной задаче используется модифицированный двумерный метод поиска с изменяемыми значениями радиуса окружности, начальной точки, и добавленным коэффициентом сжатия/растяжения радиуса.

Для проверки на достижение оптимума используется счетчик попыток нахождения произвольной точки, которая бы являлась возможным направлением.

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

Алгоритм метод случайного поиска (спуска):
1. Датчик случайных чисел генерирует угол окружности, по которому рассчитываются координаты точки

2. Сравнивается значение функции в найденной точке и в центре окружности

3. Если значение в центре окружности больше, то найдено нужное направление, переходим к пункту 4, иначе уменьшаем счетчик попыток и переходим к пункту 1. Если значение счетчика достигло нуля, значит на окружности данного радиуса нет точек оптимальнее данной, следовательно, оптимум найден.

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

Реализация метода в программе:
Данная функция возвращает координаты случайной точки (NewX, NewY) на окружности радиуса R с центром в точке OldX, OldY в возможном направлении, задаваемом функцией f и переменной SearchMode, указывающей тип искомого экстремума: максимум (-1) или минимум (1). Число попыток tries задает условие для завершения алгоритма, а параметр Stretch характеризует изменение радиуса окружности для следующей итерации.

function RandomSearch (OldX, OldY: extended; var NewX, NewY,
R:extended;Stretch:extended;tries,SearchMode:integer):boolean;
var angle:extended;
temp_func:extended;
begin
temp_func:=SearchMode*f(OldX,OldY);
repeat
angle:=random*2*Pi;
NewX:=OldX+R*sin(angle);
NewY:=OldY+R*cos(angle);
dec(tries);
until ((temp_func > SearchMode*f(NewX,NewY)) or (tries = 0));
if tries = 0 then
RandomSearch := False
else
begin
RandomSearch := True;
R:= R*Stretch;
end;
end;

2.2. Метод Фибоначчи

Данный метод представляет собой разновидность одномерного поиска экстремума функции путем последовательного сужения интервала неопределенности. Единственное ограничение, накладываемое при этом на исследуемую функцию – требование строгой унимодальности на заданном интервале.

На заданном отрезке AB выбирают две точки X1 и X2, симметричные друг другу. Обычно они отстоят друг от друга на достаточном расстоянии E (интервал нечувствительности), чтобы четко зафиксировать, в какой части интервала AB находится оптимум. Предположим, что можно вычислить F(x) N раз.

На первом этапе можно считать E=0 и точку X(N-1) расположить в середине отрезка L(N-1), а затем точку X(N) расположить справа или слева от первой точки на достаточно малом расстоянии E не равном нулю. Из рисунка следует, что интервал неопределенности имеет длину L(N) тогда L(N-1)=2*L(N)-E. На предыдущем этапе точки X(N-1) и X(N-2) должны быть помещены симметрично внутри интервала L(N-2) на расстоянии L(N-1) от концов. Следовательно L(N-2)=L(N-1)+L(N)

Аналогично L(N-3)=L(N-2)+L(N-1)

В общем случае L(T-1)=L(T)+L(T+1) при 1L(N-1)=2*L(N)-E
L(N-2)=L(N-1)+L(N)=3*L(N)-E
L(N-3)=L(N-2)+L(N-1)=5*L(N)-2*E
L(N-4)=L(N-3)+L(N-2)=8*L(N)-3*E
………………
L(N-J)=Ф(J+1)*L(N)-Ф(J-1)*E
Где J=1,2,…. N-1, а Ф(К) — последовательность чисел Фибоначчи Ф(0)=1, Ф(1)=1, Ф(К)=Ф(К-1)+Ф(К-2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…)

Если начальный интервал L(1)=B-A, то конечный: L(N)=L(1)/Ф(N)+E*Ф(N-2)/Ф(N), следовательно, после N вычислений интервал уменьшится в Ф(N) раз.

Алгоритм метод Фибоначчи:
1. Задается точность E и число вычислений N
2. Вычисляется длина начального интервала L(1)=B-A
3. Вычисляем L(2)=Ф(N-1)/Ф(N)*L(1)+(-1)N*E/Ф(N). Х2=А+L(2). Вычисляем F(X2)
4. Находим X1=A+(B-X2) и F(X1)
5. Сравниваем F(X1) и F(X2).
1) если X1X2 и F(X1)=F(X2) остается [X1,B]. A=X1, переходим к шагу 6
4) Если X1>X2 и F(X1)>=F(X2) остается [A,X1]. B=X1, переходим к шагу 6
6. K=K+1 Если Krepeat
end_search := RandomSearch(OldX,OldY,NewX,NewY,R,
Stretch,NTries,SearchMode);
Dec(OverflowCount);
if doGraph then GraphForm.PlotLine(OldX,OldY,NewX,
NewY,Mashtab);
if end_search then
begin
fibonacci(OldX,OldY,NewX,NewY,FiboX,FiboY,fiboN,
fiboE,SearchMode);
Memo1.Lines.Add('Start'
+floattostrf(OldX,ffFixed,3,3)+','+
floattostrf(OldY,ffFixed,3,3)+'->'+
floattostrf(f(OldX,OldY),ffFixed,3,3));
Memo1.Lines.Add('End '
+floattostrf(NewX,ffFixed,3,3)+','+
floattostrf(NewY,ffFixed,3,3)+'->'+
floattostrf(f(NewX,NewY),ffFixed,3,3));
Memo1.Lines.Add('Fibon '
+floattostrf(FiboX,ffFixed,3,3)+','+
floattostrf(FiboY,ffFixed,3,3)+'->'+
floattostrf(f(FiboX,FiboY),ffFixed,3,3));
Memo1.Lines.Add('');
OldX:=FiboX;
OldY:=FiboY;
end;
until (Not end_search) OR (OverflowCount = 0);
……………………………………….

Реализация метода в программе:
Функция возвращает требуемое число из последовательности Фибоначчи.

function fibo1(n:integer): int64;
var i:integer;
fm:array[1..900] of int64;
begin
fm[1]:=1;
fm[2]:=1;
for i:=3 to n do fm[i]:=fm[i-2]+fm[i-1] ;
result:=fm[n];
end;

Функция, реализующая алгоритм x1,y1, x2,y2 — координаты отрезка, на котором будет искаться оптимум. x3,y3 — координаты оптимальной точки, n — число вычислений функции, e — точность (интервал нечувствительности)

procedure fibonacci(x1,y1,x2,y2:extended;var x3,y3:extended;
n:integer; e:extended; SearchMode:integer);
var
k:integer;
a,b,l:extended;
p {координаты отрезков},r{значения функции}:array[1..4]of
extended;
begin
l:=sqrt(sqr(x2-x1)+sqr(y2-y1)); {длина отрезка}
a:=0;
b:=l;
p[1]:=a;
p[3]:=b;
p[2]:=a+((b-a)*fibo1(n-1)+e*pow(-1,n))/fibo1(n);
k:=1;
r[2]:=SearchMode*ff(p[2],x1,x2,y1,y2,l);
while k<=n do begin p[4]:=p[1]-p[2]+p[3]; r[4]:=SearchMode*ff(p[4],x1,x2,y1,y2,l); if r[4]>r[2] then
if p[2]=p[4]
begin
p[3]:=p[2];
p[2]:=p[4];
r[2]:=r[4];
end;
inc(k);
end;
x3:=p[2]*(x2-x1)/l+x1;
y3:=p[2]*(y2-y1)/l+y1;
end;

Служебная функция для подсчета (-1)^К

function pow(a:extended;b:integer):extended;
var
i:integer;
p:extended;
begin
p:=a;
for i:=1 to b-1 do p:=p*a;
pow:=p;
end;

3. Аналитический анализ функции

f(x₁, x₂ = 1/x₁ + x₁³ — 7x₁² + x₁x₂ — x₂² + 9x₁ + 3x₂ + 12;
d(f/dx₁) = -1/x₁² + 3 x₁²2 — 14x₁ + x₂ + 9
d(f/dx₂ = x₁ — 2x₂ + 3
d²f/dx₂² = -2

4. Использование программы

Интерфейс программы состоит из главного окна, в котором вводятся параметры расчета и из окна отображения, в котором графически отображается ход решения.

Главное окно разделено на две части: поля ввода параметров слева и большое текстовое поле справа, в которое будут выводиться промежуточные результаты работы алгоритма. При запуске программы поля уже заполнены данными, обеспечивающими поиск одного из максимумов функции. Для расчета достаточно нажать на пункт меню «Считать».

Возможности программы:
• Изменение всех параметров алгоритмов поиска экстремума, в том числе и характера экстремальной точки (максимум или минимум)
• Графическое отображение функции с использованием линий уровня, изменяемым масштабом и сдвигом области вывода (сдвиг начала координат).
• Вывод хода решения как в графическом (воспроизведение отрезков, получаемых на каждом шаге алгоритма), так и в текстовом режиме, что позволяет переносить данные в другие программы для дальнейшего использования.

Комментарии запрещены.