ЧИСЛЕННЫЕ МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ

1. Основные понятия. Прямые методы минимизации.

Пусть на множестве U Í R определена функция f( x). Под минимизацией функции f(x) на множестве U будем понимать решение следующей задачи: найти хотя бы одну точку минимума x* и минимум f*= f( x*) этой функции на множестве U.

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

Напомним, что число x* Î U называется точкой абсолютного (глобального) минимума или просто точкой минимума функции f(x) на множестве U, если f( x*) ≤ f( x) для всех x Î U. Значение  называется абсолютным (глобальным) минимумом или просто минимумом f(х) на U. Множество всех точек минимума функции f(x) на множестве U будем обозначать U*.

Число Î U называется точкой локального минимума функции f(x), если существует такое число d > 0, что f( ) ≤ f(x) для всех . Значение f( ) называется локальным минимумом f( x). Всякая точка глобального минимума f(х) является и точкой локального минимума этой функции. Обратное, вообще говоря, неверно.

Отметим, что минимум функции f (х) на множестве U может и не существовать, т.е. множество U* может быть пустым. В этом случае используют обобщение понятия минимума - точную ниж­нюю грань функции f(х) на множестве U. Пусть f(х) ограничена снизу на U, т.е. f(х) ³ А ³ - ¥ для всех x Î U. Число f _* назы­вается точной нижней гранью функции f(х) на множестве U ( ), если f(х) ³ f _* при всех x Î U и для любого e> 0 найдется точка x Î U такая, что f(х_e) < f _* +e. Для неограни­ченных снизу функций f ( x ) полагают f _* = - ¥ . Если U* ¹ Æ, то .

Существование локальных минимумов функции f(х), отлич­ных от абсолютного, почти всегда затрудняет поиск точек x* Î U*, поэтому многие приближенные методы минимизации применимы только тогда, когда любой локальный минимум f(х) является одновременно и глобальным. Один из классов функций, удовлет­воряющих этому условию, составляют унимодальные функции.

Функция f(х) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа α и β, такие, что;

1) если α < а, то на отрезке [а; α ] f (х) монотонно убывает;

2) если β < b, то на отрезке [β; b] f (x) монотонно возрастает;

3) при хÎ [α ; β ]

Отметим, что возможно вырождение в точку одного или двух из отрезков [а; α ], [α ; β ] и [β; b]. Некоторые варианты располо­жения и вырождения в точку отрезков монотонности и постоян­ства унимодальной функции показаны на рис. 8.8.

 

Рис.8.1. Примеры унимодальных функций

Множество функций, унимодальных на отрезке [а; b], будем обозначать Q[а; b].

Для проверки унимодальности функции f(х) на практике обычно используют следующие критерии:

1) если функция f(х) дифференцируема на отрезке [а; b] и производная f'(х) не убывает на этом отрезке, то f( x) Î Q[а; b].

2) если функция f ( x ) дважды дифференцируема на отрезке [а; b] и f”(х) ³ 0 при x Î [а; b], то f ( x ) Î Q[а; b].

Пример 8.3. Показать, что функция  унимодальна на отрезке [3; 5].

Вторая производная функции f( x) равна . Корни полученного квадратного трехчлена х₁==2 и х₂=3. Следо­вательно, f" ( x) ³ 0, если х ³ 3 и, в частности, при xÎ [3; 5]. Используя второй критерий унимодальности, получаем, что f( x) Î Q[3; 5].

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

Метод перебора является простейшим из прямых методов ми­нимизации. Пусть f( x) Î Q[а; b]и требуется найти какую-либо из точек минимума х* функции f(х) на отрезке [а; b] с абсолютной погрешностью e > 0. Разобьем [а; b] на п равных частей точками деления , где . Вычислив значения f(х) в этих точках, путем сравнения найдем точку х_т, для которой

Далее полагаем . При этом максимальная погрешность ε _n определения точки х* равна .

Пример 8.4. Найти минимальное значение f* и точку минимума х* функции  на отрезке [1, 5; 2]. Точку х* найти с погрешностью ε = 0, 05.

f( x) Î Q[1, 5; 2], так как  при x Î [1, 5; 2].

Выбрав , вычислим значения , поместив их в таблице 8.8.

Таблица 8.1

xi	1, 50	1, 55	1, 60	1, 65	1, 70	1, 75	1, 80	1, 85	1, 90	1, 95	2, 00
f(xi)	-89, 44	-90, 45	-91, 24	-91, 79	-92, 08	-92, 12	-91, 89	-91, 37	-90, 56	-89, 44	-88, 00

Из таблицы 8.1 находим х*» 1, 75, f* » -92, 12.

Метод перебора, предполагающий предварительный выбор то­чек x_i, называется также пассивной стратегией поиска точки минимума х*. На практике точки х  выбираются за­ранее, когда удобно провести п+1 независимых экспериментов по измерению значений f( x), а последовательное измерение этих значений трудоемко или невозможно, например ввиду нехватки времени. Однако использование уже полученной в предыдущих экспериментах информации о функции f( x)для выбора очередной точки x_i измерения (вычисления) f( x) приводит к более эффектив­ному поиску точки х*. Методы минимизации, в которых точки x_i определяются в процессе поиска точки минимума с помощью най­денных ранее значений функции f( x), называются последователь­ными методами.

Метод деления отрезка пополам является простейшим после­довательным методом минимизации. Он позволяет для любой функ­ции f( x) Î Q[а; b]построить последовательность вложенных отрезков , каждыйизкоторых содержит хотя бы одну из точек минимума х* функции f(х) Пусть e> 0 - требуемая точность определения точки х*. Выбрав , построим последовательности , используя рекуррентные формулы:

 если                                                        (8.1)

 если

Переход от отрезка  к отрезку  методом деления отрезка пополам иллюстрируется на рис. 8.2а), если  и на рис. 8.2б), если

а)                                           б)

Рис.8.2. Метод деления пополам

Полагая , находим х* с абсолютной погреш­ностью, не превосходящей величины

Используя условие , из последнего выражения можно найти необходимое число шагов п для обеспечения требуемой точ­ности e. Однако на практике часто поступают иначе: определив границы отрезка , вычисляют  и сравнивают с заданной точностью e.

Пример 8.5. Решить пример 8.4 методом деления отрезка по­полам.

Положим d=0, 02 < 2e=0, 8. Построим последовательность вложенных отрезков  по формулам (8.1), записывая резуль­таты вычислений в таблицу 8.2:

Таблица 8.2

n	an	bn						Примечание
0	1, 50	2, 00	0, 25	1, 74	1, 76	-92, 135	-92, 096
1	1, 50	1, 76	0, 13	1, 62	1, 64	-91, 487	-91, 696
2	1, 62	1, 76	0, 07	1, 68	1, 70	-91, 995	-92, 084
3	1, 68	1, 76	0, 04					, точность достигнута

 

Следовательно, х* »1, 72, и f* » f (1, 72)=92, 13.

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

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

Золотое сечение отрезка[а; b]осуществляется двумяточками:

причем x₁ есть вторая точка золотого сечения отрезка [а; х₂]. а х₂ - первая точка золотого сечения отрезка [х₁; b].

Зная одну из точек золотого сечения отрезка [а; b], другую можно найти по одной из формул

                                                     (8.2)

Пусть f( x) Î Q[а; b]и требуется найти точку минимума функ­ции f(х) на [а; b]. Построим последовательности , следующим образом:

, если                                     (8.3)

если

 

где  - первая и вторая точки золотого сечения отрезка .

Для определения чисел по найденным  необходимо выполнить следующие операции:

1) найти одну из точек золотого сечения отрезка  по известной другой точке , используя формулы (8.2);

2) вычислить значение f(х) во вновь найденной точке золотого сечения (значение в другой точке  уже вычислено на одном из предыдущих шагов);

3) сравнить значения  и  и найти  по формулам (8.3).                                                 

Таким образом, на каждом шаге определения  требуется вычисление одного значения f(х). Положив , найдем точку минимума х* с точностью :

откуда следует, что число шагов п метода золотого сечения, обеспе­чивающее заданную точность ε нахождении точки х*, должно удовле­творять неравенству

                               (8.4)

Пример 8.6. Решить предыдущий пример методом золотого сечения.

Вычисления проведем по формулам (8.3), представив результаты в таблице 8.3.

Т а б л и ц а 8.3

n	an	bn						Примечание
1	1, 500	2, 000	0, 309	1, 691	1, 809	-92, 049	-92, 096
2	1, 500	1, 809	0, 191	1, 618	1, 691	-91, 464	-92, 049
3	1, 618	1, 809	0, 118	1, 691	1, 736	-92, 049	-92, 138
4	1, 691	1, 809	0, 073	1, 736	1, 764	-92, 138	-92, 083
5	1, 691	1, 764	0, 045		1, 736		-92, 138	, точность достигнута

 

Из таблицы 8.3 получаем . Заметим, что если воспользоваться формулой (8.4), то необходимое число шагов п можно определить заранее. В нашем случае п ≥ 4, 79, т. e. п =5, и отпадает необходимость во втором столбце таблицы 8.3.

В прямых методах минимизации, рассмотренных выше, требуется, чтобы функция f(х)  была унимодальной. Если f(х) этим свойством не обладает, то применение указанных методов приводит, вообще говоря, к неверному результату. Кроме того, во многих случаях доказательство унимодальности функции f(х)  бывает за­труднительно.

Метод ломаных является последовательным методом, рассчитан­ным на минимизацию произвольных (не обязательно унимодаль­ных) функций, удовлетворяющих условию Липшица. Говорят, что функция f(х) удовлетворяет на отрезке [а; b] условию Липшица, если существует такое число L > 0 (константа Липшица), что

\ f( x')- f( x" )\< L\ x'- x" \                                                       (8.5)

для всех х', х" Î [а; b].

Для проверки условия Липшица на практике используют сле­дующий факт: если функция f(х) имеет на отрезке [а; b] ограниченную производную, то она удовлетворяет условию (8.5), где .

Пусть функция f(х) удовлетворяет на [а; b]условию Липшица с константой L. Опишем метод ломаных для минимизации f(х).

Положим

и реализуем следующую схему вычислений:

Шаг 1. Вместо пары чисел  образуем двеновые пары  и  следующим образом:

 где .

Шаг 2. Из полученных двух пар  и  выберем ту, у которой вторая компонента минимальна. Обозначим ее  и исключим из рассматриваемого множества (очевидно, на данном шаге в качестве  можно взять любую из пар , ). Вместо пары  добавляем две новые пары  и , компоненты которых находятся по формулам

 где .

В результате получим множество, состоящее из трех пар чи­сел (х, р).

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

 где .                  (8.6)

Полагая х* ≈ , f* ≈ f( ), получим приближенное решение задачи минимизации. Точность определения f* характеризуется неравенствами .

Геометрически метод ломаных состоит в построении последовательности ломаных, приближающихся к графику функции f(х) снизу и имеющих угловые коэффициенты всех звеньев, равные ±L (рис. 8.3).

Рис. 8.3. Метод ломаных

Пример 8.7. Методом ломаных найти минимум f* функции на отрезке [10; 15] с точностью 0, 01 и точку минимума х*.

Функция f(х) дифференцируема на указанном отрезке. Так как

при хÎ [10; 15], то f(х) удовлетворяет условию Липшица с константой L=0, 18.

Найдя = 12, 056, =-0, 281, продолжим вычисления, используя соотношения (8.6). Результаты вычислений представим в таблице 8.4.  

Т а б л и ц а 8.4

n	Исключаемая пара		f( )			Включенные пары
1	12, 056	-0, 281	-0, 041	1, 093	0, 240	10, 963	13, 149	-0, 161
2	10, 963	-0, 161	-0, 091	0, 316	0, 070	10, 647	11, 279	-0, 126
3	13, 149	-0, 161	0, 042	0, 921	0, 203	12, 228	14, 070	-0, 059
4	10, 647	-0, 126	-0, 088	0, 171	0, 038	10, 475	10, 818	-0, 107
5	11, 279	-0, 126	-0, 085	0, 186	0, 041	11, 094	11, 465	-0, 106
6	10, 475	-0, 107	-0, 083	0, 110	0, 024	10, 365	10, 586	-0, 095
7	10, 818	-0, 107	-0, 091	0, 073	0, 016	10, 745	10, 891	-0, 099
8	11, 094	-0, 106	-0, 090	0, 072	0, 016	11, 022	11, 166	-0, 098
9	11, 465	-0, 106	-0, 078	0, 126	0, 028	11, 339	11, 591	-0, 092
10	10, 891	-0, 099	-0, 091	0, 035	0, 008< e

 

Из таблицы 8.4 находим х* » 10, 891, f* » f (10, 891) =-0, 098.

Отме­тим, что f (х) Ï Q[10; 15], поэтому из методов минимизации, рассмотренных выше, в данном случае применим только метод ломаных.

2. Методы минимизации, основанные на использовании производных функции.

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

Mетод касательных применяется для минимизации выпуклых дифференцируемых функций. Функция f (х) называется выпуклой на отрезке [а; b],  если

                                (8.7)

 для произвольных х', х" Î [а; b]и .

Проверка условия (7) почти всегда вызывает затруднения, поэтому на практике используют следующий критерий выпуклости:

Для того, чтобы дважды дифференцируемая на отрезке [а; b] функция f(х) была выпуклой на отрезке [а; b], необходимо и доста­точно, чтобы f" [ x)≥ 0 при всех х Î [а; b].

Опишем метод касательных. Пусть f(х) - выпуклая дифферен­цируемая на отрезке [а; b]функция, причем . Построим последовательности , в соответствии с рекуррентными соотношениями

,                                             (8.8)

при ,                                                                      (8.9)

при .                                          

После п шагов полагаем . Требуемая точ­ность минимизации f( x) считается достигнутой, если производная f'(c) достаточно близка к нулю, т. е. | f'(c_п)| £ e, где e> 0 - заданное число, характеризующее точность.

Метод касательных имеет простой геометрический смысл: вели­чина с _{n -1} из (8.8) - это абсцисса точки пересечения касательных к графику f ( x ), проведенных в граничных точках отрезка  (рис. 8.4а)). Рис. 8.4б) и 8.4в) поясняют формулы (8.9) для случаев  и  соответственно. Отрезок  выби­рается так, чтобы x * Î .Если условие  не выполняется, то

а) х*=а при f’ (а) > 0, f’ ( b) > 0;

б) х*= b  при f’ (а) < 0, f’ ( b) < 0;

в) х*=а, если f'( a)=0, и х*= b, если f’( b)=0.

Пример 8.8. Убедиться, что функция выпукла на [-1; 1] и минимизировать ее методом касательных с точностью | f'(c)| £ 0, 05.

Так как > 0, то f(х) - выпуклая функция; кроме того, . Проведем вычисления по формулам (8.8), (8.9), поместив результаты вычислений в таблицу 8.5.

Таблица 8.5

n	an	bn	f(an)	f(bn)	f'(an)	f'(bn)	cn	f'(cn)	Примечание
0	-1, 00000	1, 00000	1, 368	3, 718	-1, 632	4, 718	0, 11586	1, 355
1	-1, 00000	0, 11586	1, 368	1, 136	-1, 632	1, 355	-0, 41637	-0, 173
2	-0, 41637	0, 11586	0, 833	1, 136	-0, 173	1, 355	-0, 14313	0, 580
3	-0, 41637	-0, 14313	0, 833	0, 887	-0, 173	0, 580	-0, 27804	0, 201
4	-0, 41637	-0, 27804	0, 833	0, 835	-0, 173	0, 201	-0, 34679	0, 013	| f'(cп)| £ e

 

Из таблицы 8.5 находим х* »-0, 347; f* » f (-0, 347)= 0, 827.

Метод Ньютона, использующийне только первую, но и вто­рую производные функции f( x), при определенных условиях обеспе­чивает значительно более высокую, чем рассмотренные выше методы минимизации, скорость сходимости к точке минимума х*.

Пусть f( x) - выпуклая дважды дифференцируемая на R функ­ция. Выбрав начальное приближениех₀, построим последователь­ность

                                              (8.10)

Считая неравенство | f'(х_п)| £ e (e - достаточно малое число) усло­вием достижения требуемой точности вычислений, положим х* ≈ , f* ≈ f( ).

При неудачном выборе Хц последовательность (10) может рас­ходиться. Если же точка х₀ достаточно близка к х*, то эта последо­вательность сходится к х* достаточно быстро.

Оценка скорости сходимости может быть сформулирована сле­дующим образом. Пусть f( x) - дважды дифференцируемая на R функция, причем при всех x Î R . и f" '(х) удовлетво­ряет условию Липшица на R с константой L. Тогда, если началь­ное приближение х₀ удовлетворяет условию , то последовательность (8.10) сходится к единственной точке мини­мума х* функции f(х) на R, причем

Пример 8.9. Методом Ньютона найти точку минимумах*и минимальное значение f* функции  с точностью | f'(х_п)| £ 10^-7.

Выберем х₀=3 и проведем вычисления по формуле (8.10), запи­сывая результаты в таблице 8.6.

Таблица 8.6

n	х n	f(xn)	f'(xn)	f''(xn)
0	3, 0000000	-0, 0986123	3, 66666667	12, 1111111
1	2, 6972477	-0, 7558858	0, 98513176	5, 9713067
2	2, 5322701	-0, 8488508	0, 20829036	3, 5556858
3	2, 4736906	-0, 8553636	0, 02089779	2, 8560149
4	2, 4663735	-0, 8554408	0, 00029922	2, 7744434
5	2, 4662656	-0, 8554408	0, 00000006< 10-7

Окончательно х* » 2, 4662656, f'*»-0, 8554408.

Метод Ньютона часто используется на завершающем этапе минимизации, когда точка минимума х* грубо найдена другим, менее трудоемким методом и требуется найти х* с большой точ­ностью.

⇐ Предыдущая123456789Следующая ⇒

Поделиться: