Методы прямого поиска экстремума функции одной переменной

3. МЕТОДЫ ПРЯМОГО ПОИСКА ЭКСТРЕМУМА  ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

 

 

В самом общем виде идея методов  прямого поиска экстремума функции  одной переменной состоит в следующем. Первоначально устанавливаются  границы интервала неопределенности, относительно которого точно известно, что он содержит точку экстремума. Затем длину интервала последовательно уменьшают специальным образом так, чтобы не исключить из него экстремальную точку. В итоге длина интервала уменьшается до величины, удовлетворяющей заранее заданной точности. Под экстремумом в этих методах всегда понимается минимум. Случай максимизации функции g(x) сводится к случаю минимизации путем введения новой функции fix) = - g(x).

Методы  прямого поиска применимы только к унимодальным функциям.

Определение. Функция fix) называется унимодальной на отрезке [а, Ь], если она непрерывна на этом отрезке и существуют числа х\, х_ъ а < х_х< х₂ < Ь, такие, что:

1. fix) монотонно убывает на отрезке [а, х\], если а < х\\
2. fix) монотонно возрастает на отрезке [х_ь Ь], если х₂ < Ь\
3. в точке jc*e[jci, х₂] функция fix) достигает своего минимального значения:/„,„ = fix*).

Отрезок [а, Ь], на котором ищется минимум  унимодальной функции, называется отрезком локализации минимума.

Ниже приведены  примеры графиков унимодальных функций.

 

 

 

 

 

 

 

 

Рис. 11. Функция имеет Рис. 12. Функция имеет

нестрогий минимум на отрезке [х\, х₂] строгий минимум в точке х, = х₂

 

 

11111111111111111111111111111111111111111111111111111111111111111111111111111111111

 

Воспользуемся вторым признаком, для чего последовательно найдем первую и вторую производные данной функции: у' = 1пх + 2х - 2, у" = Их + 2. Отсюда видно, что у" > 0 при всех хе[1; 2], так как на этом отрезке содержатся только положительные значения х.

2) Проверить на унимодальность  функцию f(x) = х², jce[l; 10].

Применяя формулу Лейбница, находим  последовательно

у '=(\ + \пх)х^х, у" + (i + inx)¹ В силу того, что выражение, содержа- 
щее натуральный логарифм, возводится в квадрат, получаем, что у" > 0 при 
любых значениях переменной х из заданного интервала. Следовательно, ис- 
ходная функция унимодальна на заданном интервале.

В прямых методах  минимизации функции применяется  следующая лемма.

Лемма об отрезке локализации минимума. Пусть функция fix) унимо- 
дальна на отрезке [а, 6], х_их₂е[а; Ъ] х_{<х₂. Тогда, если fix _{) <Л*2), то х*е[а, х₂]; 
tzmfix_{) >fix₂.), то x*g[x_u Ь].

Приведем  графическую иллюстрацию данной леммы. На рис. 15 пока- 
зан случай fixi) <fix₂). Это означает, что функция fix) возрастает на [х_ь х₂]. 
Следовательно, минимум функцииДх) содержится на отрезке [а, х₂], поэтому 
[х₂, Ь] можно исключить из рассмотрения.

 

 

1111111111111111111111111111111111111111111111111111111111111111111111111111111

На рис. 16 представлен случай fix\) >fix₂). Здесь функция fix) убывает на [х_ь х₂]. Поэтому согласно лемме минимум функции fix) содержится на отрезке [х_ь Ь], следовательно, [а,х\] можно отбросить.

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

 

 

 

 

 

 

 

 

3.2. Метод перебора

Метод перебора является простейшим из прямых методов минимизации. Пусть функция fix) унимодальна на отрезке [а, Ъ] и требуется найти точку минимума я;* функции fix) на заданном отрезке с абсолютной погрешностью е > 0. Для этого разобьем отрезок [a, b] на п равных частей точками

.Ь-а .

_х =_a + i ,/ = 0,1,..., и,

п

Ь-а

где п > . Вычисляя значения fix) в этих точках, путем сравнения найдем

8

точку х_т, для которой

/(xj = min/(*,).

0</<//

Другими словами, выбирается точка х_т, в которой исходная функция принимает наименьшее из вычисленных значений. После этого точку х_т принимают за точку минимума: х « х_т, f « f(x_m).

Пример. fix)=x⁴ + 8х³ - вх² - 12х —> min, хе[1, 5; 2], е = 0,05. *

Функция унимодальна, так как/'(х) - 12х² + 48х - 12 > 0 при всех значениях *е[1, 5; 2]. Выберем п = {Ь- а)/е„ = (2 - 1,5)/0,05 = 10 и вычислим значения Дх/), гдех, = 1,5 +/-0,05,/' = 0, 1, ...,10. Найденные х,- и значения функции fix) занесем в таблицу:

 

г,	1,5	1,55	1,6	1,65	1,7	1,75	1,8	1,85	1,9	1,95	2
Л*,)	-89,4	-90,2	-91,2	-91,8	-92,08	-92,12	-91,9	-91,4	-90,5	-89,4	-88

 

Из таблицы находим х* » 1,75, f_mm = f(\,15) « -92,12.

 

 

 

 

3.3. Метод дихотомии

Пусть на интервале [а, Ь] требуется  найти минимум унимодальной 
функции Дх). Положим / = 0 и разобьем исходный отрезок точками

x₂=3L±^8. 5>0, (3.1)

при а₀ = а, Ь₀ = Ь. Обычно выбирается де{^2е), где е - погрешность 
вычислений. В найденных точках вычисляются значения заданной функции, 
после чего к ним применяется лемма об отрезке локализации минимума: если 
fixi) <fix₂), то в качестве отрезка локализации минимума выбирается [a_h х₂], 
если же/jxi) >fix₂) - то отрезок [х_и Ъ,]. После этого полагается / := / + 1 и 
вычисляется очередная пара точек х_х, х₂ по формулам (3.1). Процесс будет 
завершен, как только на очередном шаге выполнится условие (Ь_п-а_п)/2 < е. 
После этого за точку минимума принимается, как правило, середина послед- 
него отрезка локализации.

Пример, fix) = х^л + 8х³ - 6х² - 72х/ш'л, хе[1,5;2], е = 0,05.

Функция унимодальна, как было показано в п. 3.2. Выберем д = 0,02. Оп- 
ределим точки первого разбиения: = ²-0,02=1,73 = ^{1,5 + 2} 4- 0,02 = 1,77.

Процесс дальнейших вычислений представлен  таблицей:

п	а„	Ьп	(Ь„-а„У2	Х\	х2	fix l)	< >	fixi)
0	1,5	2	0,25	1,73	1,77	-92,1382	<	-92,0605
1	1,5	1,77	0,135	1,615	1,655	-91,4282	>	-91,8272
2	1,615	1,77	0,0775	1,673	1,713	-91,9547	>	-92,1191
3	1,673	1,77	0,0485

 

 

Итак, + ^:1-⁷⁷ _{= 17}22, f_min-Д1,735) - -92,138

 

Процесс разбиения  и последовательного уменьшения отрезка локализации минимума показан на рис. 17.

1,5 1.73 1.77 2 ■  1 1 

 

1,5 1.615 1.655 1.77   I 1 

'г⁷'³ 1.77

1,673 1.77       Рис. 17. Уменьшение отрезка локализации в методе дихотомии

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

Определение. Элементы последовательности F, называются числами Фибоначчи, если F₀ = F\= 1, F_i+l = F_iA + F_n i = 1, 2, 3, ... . Для примера выпишем пятнадцать первых членов последовательности Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... .

Элементы последовательности Фибоначчи  используются в методе Фибоначчи для нахождения первых двух точек разбиения отрезка локализации минимума по формулам

х_х=а + ^-(Ъ-а), х ₂=а + ^±(Ь-а), (3.2)

F_N ■ F_n

где [а, Ъ] - исходный отрезок локализации минимума.

После вычисления значений минимизируемой функции в точках х\ их₂ применяется лемма об отрезке локализации минимума: если/ОгО <fix₂), то выбирается отрезок [а₉ х₂]; если же fix\) >fix₂), то необходимо выбрать отрезок [x_h Ь]. При этом вторая точка разбиения становится первой, если выбирается отрезок [х_ь Ь], а первая точка разбиения становится второй точкой, если выбирается отрезок [а, х₂]. Пусть для примера выбран отрезок [а,х₂]. Обозначим правую границу через b = х₂. Тогда точка х_и находящаяся внутри этого отрезка, получит обозначение х₂, а значение функции/^) в «старой» точке х\ станет значением функции fix₂) в «новой» точке х₂. Новая точка х\ выбирается симметрично текущей точке х₂ относительно середины отрезка локализации минимума. Схематически этот процесс изображен на рис. 18.

1—t

JCl х?

_J L

1111111111111111111111111111111111111111

В случае перехода к отрезку [х_ь b] аналогичный процесс проиллюстрирован на рис. 19.

*2

^а | |  ^Ь

Рис. 19. Перенос значениям

 

 

 

 

 

 

В обоих случаях для нахождения одной из точек при известной  другой используется формула

x_l+x₂ = a + b (3.3)

Число N в формулах (3.2) служит также для определения количества необходимых итераций при решении конкретной задачи минимизации унимодальной функции следующим образом.

Пусть е ~ 0,05 - заданная точность вычислений. Вычисляется величина т = Не = 20, затем определяются два последовательных члена ряда Фибоначчи, между которыми заключено число т: 13 < m < 21 = F-j. После этого принимается N=7. Величина N- 1 = 6 показывает, сколько итераций необходимо проделать для завершения вычислений. На N - 1 итерации та из точек xi или х₂, которая перейдет внутрь последнего отрезка локализации минимума, и будет являться точкой минимума исходной функции.

Пример, fix) = х⁴ + 8х³ - 6х² - 72х min, хе[1,5; 2], е = 0,05.

Унимодальность функцииДх) была установлена  в п. 3.2. При заданном значении ..с  имеем N=7, как это было показано выше. Точки первого разбие-

8 13

ния найдем по формулам (2): х, = 1,5+—f2-1,5,) «1,691, х₂ = 1,5+—(2-1,5;al,8L

Итерационный процесс представлен  таблицей, в которой стрелками  показан перенос значений х, и fix), i = 1,2, при очередном изменении интервала локализации минимума.

 

п	а»	ь„	х\	Л-2	Л*)	< >	Л*2>
0	1,5	2 .	1,691ч	1,81	-92,00) ^	<	-91,806
1	1,5	1,81	1,619	^1,691	-91,475	>	^-92,049
2	1,619 1,691 1,691	1,81 1,81 1,762	1,691 У 1,738 У 1,715	1,738 1,762 ^1,738	-91,049^ -92,137 < -92,123		-92,137 -92,09 ^-92,137
	1,715 1,715	1,762 1,7382	1,7387	1,7382 41,738	-92,137с	г	-92,1*6 ^-92,137

 

Таким образом, х* ~ 1,738, f_mia ~fi 1,738) = -92,137

 

 

 

3.5. Метод золотого  сечения

 

Определение. Деление отрезка на две неравные части таким образом, что отношение длины всего отрезка к длине большей его части равно отношению длины большей части к длине меньшей части, называется золотым сечением отрезка.

На рис. 20 показано золотое сечение  отрезка АВ точкой С: = АС СБ

А  ^С,  В

Рис. 20. Золотое сечение отрезка  АВ точкой С

Золотое сечение можно найти из уравнения F_i+i = /^г_/_₁ + F_h если искать его решение среди геометрических прогрессий с членом /'. Тогда получим уравнение t¹ = t + /^м или i'\t² - / - 1) = 0, откуда следует, что t² - t - 1 = 0.

_ 1 + л/5

Один из корней последнего уравнения, а именно t-—-—» 1,618, и называется золотым сечением. Обозначим его как т = 1,618.

Пусть минимум унимодальной функции fix) ищется на отрезке [0, 1]. Первые

две точки разбиения отрезка  выбираются как х_] = 4г-« 0,382, х₂ = — « 0,618 и

т х

являются симметричными друг другу относительно середины отрезка локализации минимума. В общем случае золотое сечение отрезка [а, Ь] осуществляется двумя точками

 

X! = а + 0,382(6 - а), х₂ = а + 0,618(6 - а), (3.4)

причем х\ есть вторая точка золотого сечения отрезка [а, х₂], а х₂ - первая точка золотого сечения отрезка [х_ь Ь]. К выбранным точкам применяется лемма об отрезке локализации минимума. После перехода к «суженному» отрезку локализации одна из двух точек разбиения переносится в новый отрезок, как это показано на рис. 18 и рис. 19, вместе со значением функции в этой точке. Вторая точка разбиения нового отрезка определяется с помощью формулы (3.3). Процесс поиска минимума будет завершен, как только на п-й итерации будет выполнено условие

(0 £Щ"ф-а)<е.

Та из точек х\ или х₂, которая перейдет внутрь последнего отрезка локализации минимума вместе с соответствующим значением функции, и будет являться решением поставленной задачи.

 

 

 

Пример, fix) = х⁴ + 8х³ - 6х~ - 72х -> min, хе[ 1,5; 2], г = 0,05.

Унимодальность функции Дх) была установлена в п. 3.2. Точки перво- 
го разбиения найдем по формулам (3.4):

х, - 1,5 + 0,382(2- 1,5) ~ 1,691, х₂ = 1,5 + 0,618(2 - 1,5) ~ 1.809.

 

 

 

 

 

 

 

 

Итерационный процесс решения  представлен таблицей, в которой  стрелками показан перенос значений х, и fix) при очередном изменении интервала локализации минимума.

 

 

 

Упражнения. Следующие задачи минимизации функции fix) на за- 
данном отрезке с точностью е решить методом

а) перебора; б) дихотомии; в) Фибоначчи; г) золотого сечения.

 

 

1.	/(х) = xsinx + 2cosx, jc е [-5; -4], £ = 0,02.
2.	f(x) = х4 + 8х3 - 6х2 - 72х + 90, х е /"1,5;2], е = 0,05.
3.	f(x) = х6 + Зх2 + 6х -1, х е [-1;07,8 = 0,06.
4.	д;2 /(x) = 10xlnx-y, х е [0,5; 1],* = 0,05.
5.	/(х) = х2 + 2 xlg — - 2^, х е [1,5; 2], е - 0,01.
6.	/(х) = Зх4 -10х3 + 21х2 + 12х, х е [0; 0,5], е = 0,01.
7.	/(x) = ^-2x2, х g [3,5;4,5], £ — 0,02. In 2
8.	/(х) = - ix3 + 2х, х е [-1,5;- 1], е = 0,01.