5.1. методы одномерной оптимизации.

5.1. методы одномерной оптимизации.

Постановка задачи

Пусть функция f(x) определена на P е E1. Задачей одномерной оптимизации будем называть задачу, в которой требуется найти шах(шіп)f (x), x є P .

Решением или точкой максимума (минимума) этой задачи назовем такую точку X* є P, что f (x*) > (<)f (x) для всех x є P . Запишем

f (x) = max(mm)f(x) (5.1)

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

Определение. Функция f(x) называется унимодальной на множестве Р, если существует единственная точка x ее максимума на Р и для любых x1, x2 є P

f(xi) < f(x2) < f(x*), если x1 < x2 < x*;

f(x ) > f(x1) > f(x2), если x < x1 < x2.

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

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

Поиск отрезка, содержащего точку максимума. Алгоритм Свенна.

Исходные данные. X0 начальная точка, h шаг поиска (h>0). Шаг 1. Вычислить f (x0).f (x0 + h), f (x0 h), k=1.

Шаг 2. Если f (x0 -h) < f (x0) < f (x0 + h) , то x1=x0+h, перейти к шагу 4. Шаг 3. Если f (x0 h) > f (x0) > f (x0 + h), то x1=x0-h, h=-h, перейти к шагу 4, в противном случае

(f (x0 h) < f (x0) > f (x0 + h)), a = x0 h, b = x0 + h, конец.

Шаг 4. xk+1 = xk + 2k ■ h, Вычислить f (xk+1).

Шаг 5. Если f (xk+1) > f (xk), то k=k+1, перейти к шагу 4.

Шаг 6. Если h>0, то a = xk-1,b = xk+1, конец; в противном случае

a = xk+l, b = xk-1, конец.

Заметим, что случай f (x0 h) > f (x0) < f (x0 + h) (шаг 3) не

рассматривается, так как он противоречит предположению об унимодальности функции f(x).

Пример 5.1.

f (x) = 200x x2 -10000;x0 = 30;h = 5 f (= f (30) = -4900; f (x0 + h) = f (35) = -4225; f (x0 h) = f (25) = -5625

*

Поскольку f (x0 -h) < f (x0) < f (x0 + h) ,то x >30, x1=35. Далее x2 = x1 + 2 ■ h = 35 +10 = 45. f (= f (45) = -3025 > f (x1), x* > 35,x3 = x2 + 22 ■ h = 45 + 20 = 65. f (x,) = f (65) = -1225 > f (

х* > 45,х3 = х2 + 22 • h = 65 + 40 = 105.

/(Х4) = f (105) = -25 > f (Х3)

х* > 65,х3 = х2 + 22 • h = 105 + 80 = 185.

f (= f (185) = -7225 > f (

х* < 185,a = 65,b = 185.

Метод золотого сечения. Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Легко показать, что золотое сечение отрезка [a, b] производится двумя точками y и z, симметричными относительно середины отрезка.

a

3

b

Ъ-а = b-y = b-a = z-a =x = S+± = 1,6180. b У У a z a b z 2 Отсюда

y = (A-1)a + (Л-1)2 b = 0,618 • a + 0,382 • b z = (Л-1)2 a + (Л1)b = 0,382 • a + 0,618 • b

Нетрудно также проверить, что точка y производит золотое сечение отрезка [a, z], а точка z производит золотое сечение отрезка [y, Ь]. На этом свойстве, позволяющем на каждой итерации вычислять значение функции лишь в одной пробной точке, и основан алгоритм метода золотого сечения.

Исходные данные. [a, b] отрезок, содержащий точку максимума, є параметр окончания счета.

Шаг 1. Л = ^Y^' k=1, ak=a; bk=b;

y = (Л1К + (Л-1)2 bk; A = f(y ); z = (Л-1)Ч + (Л1)bk; B = f(z).

Шаг 2.

Если A>B, то перейдем к шагу 4.

Шаг 3.

ak+1 = y; bk+1 = bk;

У = z; A = B;

z = (A-1)2 ak+1 + (A1)bk+1;

B = f (z), перейти к шагу 5.

Шаг 4.

ak+1 = ak; bk+1 = z; z = y; B = A; y = (A1K+1 + (A-1)2 bk+1; A = f (y)

Шаг 5.

Если bk+1 -ak+1 < є, то X* є +1,bk+1], конец.

Шаг 6.

k=k+1, перейти к шагу 2. Пример 5.2.

Найти точку максимума функции f (x) = sm( x) на отрезке [1,5; 1,6], є = 0,002.

A =1,6180; a = 1,5 ; b1 = 1,6.

y = 0,6180 -1,5 + 0,3820 • 1,6 = 1,5382

z = 0,3820 -1,5 + 0,6180 -1,6 = 1,5618

A = sm( y ) = 0,99947; B = sm( z ) = 0,99996.

Итерация 1.

Так как A<B, То a2 = y = 1,5382; b2 = b1 = 1,6; a2 = y = 1,5382; b2 = b1 = 1,6;

y = z = 1,5618; A = B = 0,99996;

z = 0,3820 • 1,5382 + 0,6180 • 1,6 = 1,5764

B = sm( z) = 0,999984;

b2 a2 = 0,0618 >є.

Итерация 2.

Так как A<B, то a3 = y = 1,5618; b3 = b2 = 1,6. y = z = 1,5764; A = B = 0,99998;

z = 0,3820 -1,5618 + 0,6180 -1,6 = 1,5854 ; B = sm( z) = 0,99989;

b3 a3 = 0,0382 >є.

Итерация 3.

Так как A>B, то a4 = a3 = 1,5618; b4 = z = 1,5854.

z = у = 1,5764; B = A = 0,99998;

у = 0,6180 • 1,5618 + 0,3820 • 1,5854 = 1,5708;

A = 1,00000;

b4 a4 = 0,0236 >s. Итерация 4.

Так как A>B, то a5 = a4 = 1,5618; b5 = z = 1,57564.

z = у = 1,5708; B = A = 1,00000;

у = 0,6180 • 1,5618 + 0,3820 • 1,5764 = 1,5674;

A = sm( у) = 0,99999;

b5 -a5 = 0,0146 <s, следовательно, X* є [1,5618; 1,5764].

Домашнее задание 5.1.

Методом Свенна найти отрезок, содержащий точку экстремума унимодальной функции f(x), уточнить точку экстремума методом Золотого сечения, s = 0,05.

f(x)=x +1—шіп

f(x)=3x-x2-1—»max

f(x)=2x-x2-1—max

f(x)=2x2+3—шіп

f(x)=x +x+1—шіп

f(x)=10x2+7x+1—шіп

f(x)=15x-2x2+5—rnax

f(x)=3+7x-2x2—rnax

f(x)=4-3x2—rnax

f(x)=5-4x-x2—rnax