Главная / Основы оптимизационных методов / Поиск минимума функции одной переменной методом квадратичной параболы

Поиск минимума функции одной переменной методом квадратичной параболы

Для ускорения спуска к минимуму из некоторой точки Х0 используют локальные свойства функции вблизи этой точки. Так скорость и направление убывания можно определить по величине и знаку первой производной. Вторая производная характеризует направление выпуклости: если f»> 0, то функция имеет выпуклость вниз, иначе вверх. Вблизи локального безусловного минимума дважды дифференцируемая функция всегда выпукла вниз. Поэтому, если вблизи точки минимума функцию аппроксимировать квадратичной параболой, то она будет иметь минимум. Это свойство и используется в методе квадратичной параболы, суть которого в следующем.

Вблизи точки х0 выбираются три точки х1, х2, х3.

Вычисляется значение F1, F2, F3. Через эти точки проводится квадратичная парабола

P(z)=a*(x-x3)^2 + b*(x-x2)+c = a*z^2+b*z+c. z=x-x3, z1=x1-x3, z2=x2-x3, c= F3

(y1-y3)*z2 — (y2-y3)*z1 (y1-y3)*z2*z2 — (y2-y3)*z1*z1

A= ———————— , b= ——————————,

Z1*z2*(z1-z2) z1*z2*(z2-z1)

Если a > 0, то парабола имеет минимум в точке Zm= — b / (2*a). Следовательно, можно аппроксимировать положение минимума функции значением Хм1=х3+Zm и, если точность не достигнута, следующий спуск производить из этой точки X=Xm1, получая последовательность Xm1, Xm2, Xm3…. сходящуюся к точке Xm.

Этот метод может непосредственно применяться к функциям одной переменной. Он может быть очень полезен для выполнения линейного поиска в процедурах, где требуется найти минимум функции f(x) в точках прямой X0+LD, где Х0 — заданная точка, а LD определяет заданное направление. Значения функции F(X0+LD) на этой прямой являются значениями функции одной переменной Ф(L)= F(X0+LD).

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

F(x), начальная аппроксимация положения минимума и длинна шага h, являющаяся величиной того же порядка, что и расстояние от точки А до точки истинного минимума х* (данное условие не всегда можно удовлетворить).

3————————————————————- ———- —————— ——————— ———-

2———- ——— ——- ——— ——- — ———-

— ——- ——— ——- ——— ——- — ———- 1— — — ——— — — ——— — — — ———-

— — — ——— — — ——— — — — ———- 0—————————————————————

X0-h x0 x0+h x0 x0+h x0+2h x4 x1 x2 x3

Рис.1 рис.2

Алгоритм

Введите начальный шаг поиска h, задайте начальное значение X0, погрешность результата e.

1. Вычислить f(x0) и f(x0+h).

2. Если f(x0+h) > f(x0), то взять в качестве третьей точки X0-h и вычислить f(X0-h) [ x1=x0-h, x2=x0, x3=x0+h ].

В противном случае в качестве третьей точки взять X0+2h и найти f(X0+2h) [x1=x0, x2=x0+h, x3=x0+2h ],

3. Вычисляем y1=f(x1), y2=f(x2), y3=f(x3); Вычисляем a, b.

4. Проверяем a>0, если нет, то начальное приближение выбрано неудачно и следует закончить вычисление с таким значением и сделать два шага в сторону убывания функции x0=x0+2h и повторить снова с п.1, пока не выполнится a>0 рис 1.

5. Вычисляем Zm по выше приведенной формуле.

6. Проверяем ABSZm < e, если да, то Xm=x3+Zm, Ym=f(Xm), конец.

7. Если нет, переименовываем точки, отбрасывая точку х1: x1=x2, x2=x3, x3=x3+Zm, находим y1=y2, y2=y3, y3=f(x3).

8. Переходим на п. 4.

В программе, приведенной ниже реализован этот алгоритм.

Данный метод сходится очень быстро и является одним из наилучших методов спуска. Следует отметить, однако, что вблизи минимума расчет по приведенным здесь формулам для a и b приводит к накоплению погрешности из-за потери значащих цифр при вычитании близких чисел. Поэтому разные авторы предлагают свои эквивалентные формулы, счет с которыми более устойчив. Кроме того, в алгоритм вносятся некоторые поправки, позволяющие предусмотреть различные неприятные ситуации — переполнение, деление на 0, уход от корня.

Составить программу этим методом, найти минимум функции и сравнить с результатами, полученными ранее. Сделать вывод.

Программа метода квадратичной параболы function sqrm(f:func;x0,h, e:real):real; VAR

It:integer;

T, x1,x2,x3,Xm, y1,y2,y3,Ym, z,z1,z2,z3,a, b,c, Zm:real;

Lr, lw:text;

BEGIN it:=0; assign(lw,’p4681n46.out’);rewrite(lw); writeln(lw,’Результаты:’); writeln(‘Результаты: ‘);

If f(x0+h)>f(x0) then begin x1:=x0-h; x2:=x0; x3:=x0+h; end

Else begin x1:=x0; x2:=x0+h; x3:=x0+2*h; end; y1:=f(x1); y2:=f(x2); y3:=f(x3);

REPEAT z1:=x1-x3;z2:=x2-x3;c:=y3; a:=((y1-y3)*z2-(y2-y3)*z1)/(z1*z2*(z1-z2)); b:=((y1-y3)*z2*z2-(y2-y3)*z1*z1)/(z1*z2*(z2-z1));

If a<=0 then begin writeln(‘x0 выбрано неудачно!’); writeln(lw,’x0 выбрано неудачно!’);exit;end;

Zm:=-b/(2*a);

If abs(zm)<e then begin xm:=x3+zm;

Ym:=f(xm);

Writeln(‘При расчетах получено:’);

Writeln(‘Корень равен:………….’,xm:12:10);

Writeln(‘Значение функции:……..’,ym:12:10);

Writeln(‘Количество итераций:…..’,it);

Close(lw);exit;end;

X1:=x2;x2:=x3;x3:=x3+zm;

Y1:=y2;y2:=y3;y3:=f(x3);it:=it+1;

Writeln(lw,’X=’,x3:13:10,’ Y=’,y3:13:10);

Writeln(‘X=’,x3:13:10,’ Y=’,y3:13:10);

Until(t>0);

End;