Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Васильев Ф.П. Лекции по методам решения экстремальных задач

.pdf

Скачиваний:

Добавлен:

25.10.2023

Размер:

14.17 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 385 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

40 МИНИМИЗАЦИЯ ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ [ Г л . 1

< у . Далее, если а < (3, то /(и)		строго монотонно убывает при а <
<С«<\|3 и Нш/(ы) = / (Р ) =	/*,	ибо в противном случае, как нетруд-
—0
но видеть, функция J (и) не может быть выпуклой на [а, Ь]. Анало
гично, если у <.Ь, то J{u )	строго монотонно возрастает при у < « <

<С.Ь и lim/(u) = / (у ) = / * . Таким образом,	J{u )^ Q *[a,	Ь]. А
u-»v+o
Пусть функция J (и) выпукла и непрерывно дифференцируема
на отрезке [а, 6 ]. Согласно теореме 2 J (и)	принадлежит	Q*[a, Ь].

Опишем метод касательных для ее минимизации. Через L(u, v) будем обозначать линейную функцию L(u, v) = / ( о ) -j-J'(v) (и— v)

переменной и,	a^:us£Zb при каждом фиксированном аЕ [а , Ь). В си
лу теоремы 1	J ( u ) ^ L ( u , v) при всех « е [а , b]. В качестве началь

ного приближения может быть взята любая точка Uoe(a, Ь]. Далее

составляем функцию L(u, и0) и следующую			точку	щ определяем
из условия min L	(и, и0) = Ь ( щ , и0)	(очевидно	щ =	а	или	щ = Ь ) .
а < ц < Ь	ибо если J'(u0) =	0, то, как следует			из	неравен
Пусть /'(«о)^=0,
ства (2 ) при v=	uq, точка «о будет точкой минимума,				и процесс на

этом прекращается. Зная «ь определяем L(u, и{), составляем но вую функцию Pi (и) = т а хЬ(и, щ) и находим ы2 из условия Р i («2) =

i = 0 , l

= m in P i(« ) (рис. 5). Пусть точки Uo, и.\, ..., ип (n^sl ) уже извест-

	Р и с. 5
ны и /'(«„) =5^=0 ((если /'(«„) =	0 , то из	(2 )	при v = un следует,	что
ип — искомая точка минимума). Тогда составляем функцию
Рп(и) = шах L (и, Ui) = max{L(u,			ип), P„_i(u)}
(естественно принять P 0 (w)==L(«, и0)),		и	следующую точку	ип+1
находим из условия Рп (ип+ 1) =	min Рп (и) и т. д.
	о<и< 6

S Щ	Выпуклые	функции. Метод касательных	41
Нетрудно	видеть, что	Р п (ц) — непрерывная кусочно-линейная

функция, и график ее представляет собой ломаную, состоящую из отрезков касательных к графику функции J(u ). Поэтому описан ный метод естественно назвать методом касательных.

Т е о р е м а 3. Пусть функция J (и) выпукла и непрерывно диф ференцируема на отрезке [а,Ь], и пусть построенная выше после

довательность {а„} такова, что /'(«„) =#=0, п— 0,						1, ... Тогда:
1)	\im Pn (un+l) = J* =			inf J(u);
	п-юо			a^.u^.b
2)	последовательность			{«„} имеет не более		двух предельных
точек,	совпадающих с. a * — inf(У, u* =				supU, где V — множест
во точек минимума J {и)			на [а, Ь]. Если		U* состоит из одной точки
и, то lim an= « .
П-*оо
Д о к а з а т е л ь с т в о .				Заметим, что при выполнении условий
теоремы		функция J {и)	удовлетворяет		условию	Липшица с кон
стантой		L = m ax{\| / /(a) \|,		\|Д(&)\|} (см.	теорему	1). Кроме того,
согласно		неравенству (2 ) L(u, ип)^ .1(и ) при всех « е [а , Ь] и всех
п = 0 ,	1,	... Тогда ломаная		Р „(ы ), построенная		из отрезков каса

тельных указанным выше способом, обладает свойствами 1)— 4), сформулированными перед теоремой 9.1. Поэтому буквальным пов торением доказательства теоремы 9.1 молено убедиться, что любая предельная точка последовательности {«„} принадлежит множест

ву U*. Однако J {и)	непрерывна и строго квазивыпукла	на [а, Ь],
поэтому U* либо представляет собой отрезок			либо
состоит из единственной точки и*. По условию 1'{ип) Ф 0			и, сле
довательно, Опфи*.	Тогда предельными для последовательности
{«„} могут быть лишь точки и* или и*, а в случае и =		и**	имеет
место равенство \\тип= и*. Д
П — > СЮ

При описании метода касательных выше предполагалось суще ствование производной J'(u) во всех точках ц е [а , Ь]. Однако этот метод может быть приспособлен для поиска минимума любой вы пуклой функции на отрезке [а, Ь], лишь бы она достигала своей нижней грани на этом отрезке. Дело в том, что выпуклая на [а, Ь\ функция во всех внутренних точках этого отрезка непрерывна, имеет конечные левые и правые производные

/ '(« + <))= П т . /(“ + *> -/(?> , h

J ’ (и — 0) = П т n u ) - J ( a - h )

’h->+a ft

причем У [и—0) ^ / '(ы + О ) (см. ниже				упражнение 2). Поэтому в
описанном	выше	методе	касательных	можно	принять L(u, -ап) ==
= J (ип)	{и—	ип), где	] п — произвольная		постоянная, удовлет-

42	МИНИМИЗАЦИЯ	ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ	[Гл. I
воряющая	неравенствам	J'{u„—0) ^ / п^ / '(м п+ 0 ) ;	неравенство
J (и) ^ L ( u ,	ип), а ^ и ^ .Ь ,	при этом сохранится (см. упражнение3).
На практике удобнее брать Зп из условия \|/„\| = m in {\| / '(«n— 0) \|,

U /(un + 0) \|}.	Если при некотором п окажется, что / '(ип— 0 ) ^ 0 ^
(м „+ 0),	то ип — точка минимума (см. упражнение 4), и в

этом случае процесс прекращается. Чтобы избежать возможных

равенств Д ( а + 0 ) = — оо или J'{b —0 ) = +			оо, удобно начинать про
цесс поиска с точек uQ=a-\-h0 и U\ = b—hi			с тем, чтобы следующее
приближение «2 взять из условия минимума Р 2(«) =xnax{L-(u, и0)\
L(u, Mi)}.	Здесь	ho, hi — положительные	величины, выбираемые
из условия,	чтобы	/'(а+Ао+О ) и J'(b — hi—0 ) помещались в раз

рядной сетке ЭВМ. Если окажется, что /'(я+Ао+О) и J'(b —h0— 0) положительны [отрицательны], то точку минимума следует искать на отрезке а^ и ^ а-\ -1г0 [A— hi^ -U ^ b] с помощью методов, не требующих вычисления производной функции.

При такой модификации метод касательных пригоден для по иска минимума любой выпуклой функции на любом конечном от резке; утверждения теоремы 3 остаются при этом справедливыми. Поскольку ломаная из отрезков касательных аппроксимирует функцию J {и) лучше, чем ломаная из § 9, то следует ожидать, что метод касательных для выпуклых функций, вообще говоря, сходится быстрее метода ломаных из § 9. Оптимальная стратегия

поиска минимума выпуклых функций описана в работе [242].
Упражнения.	1. Если /(«) выпуклая функция на отрезке [а, b],
то
J (и)—	J (v)	J (w) — j (v)	^	J ( w ) — J (u)
---------------------- -----------------------------				w— и	(3)
и —	v	w — v

при всех и, v, w, a^Zv<u<Cwz£:b. Доказать. Выяснить геометри ческий смысл этих неравенств.

У к а з а н и е . Использовать выпуклость функции и представ

ление u=-av-\- ( 1— a) w, где u < u < .w , а = —— — ,	0	1 .
ш — V		I (и) во
2. Доказать, что выпуклая на отрезке [а, Ь]	функция	I (и) во

всех внутренних точках отрезка непрерывна и имеет конечные ле

вые и правые производные J'(udtO),				причем		J'(u — 0 )^ Д ( ы + 0 ),
и е (й , Ь). Доказать,		что / '(ц + 0) —		неубывающая			непрерывная
справа функция,	/'(и—0 ) — неубывающая					непрерывная		слева
функция.
У к а з а н и е .	Пользуясь		неравенствами			(3), доказать,		что
J (и) — J (и — т)		J ( u ) — J ( u — h)		г -	j ( u - \ - h ) — J (и) ^
-------------------------------		- С ----------------	;------------		---------------;---------------		-С
		^ y ( u - j - t ) — J (и)						(4)
		•Ч.------------------------	х

при всех т, Л, лишь бы 0 < А < т ; и, ы ±т,					u ± t e [ a , Ь].

S щ	Выпуклые функции. Метод касательных		43
3. Если J	{и) выпукла на отрезке [а, Ь], то
	Ли) > J (v) +	J'n-iu — v)	(5)
при всех и, v,	а <1 и К Ь,	где J n— произвольное	число,

такое, что J' (о — 0) < J„ < J' {и + 0).
У к а з а н и е . Воспользоваться	доказательством	неравенства
(2), рассмотрев случаи u > v и	и неравенством	J'(v —0) ^

</ '( и + 0 ).

4.Точка н.*е[а, 6 ] является точкой мйнимума выпуклой функ

ции / (и) на отрезке (а, Ь] тогда и только тогда,					если / '(« * + 0 ) ^		0 ,.
J'(u*— 0 ) ^ 0 . В	частности, если / '(«) существует и a< iu < ib,						то
J'( u * ) — 0. Доказать.
У к а з а н и е .	Принять в (5)		Уп — 0.
5. Доказать, что выпуклая на отрезке [а, Ь]					функция I {и) диф-'
ференцируема почти всюду на этом отрезке.
У к а з а н и е .	Воспользоваться			монотонностью		функций
Г (и— 0 ), / '(м + 0 ) и показать, что J'{u—0 ) = / /(м + 0 ) во						всех точ
ках непрерывности/Дц+О) (или J'{u —0 )).
6 . Доказать,	что выпуклая		на отрезке (а, Ь] функция /(и)
удовлетворяет условию Липшица на каждом отрезке						ле
жащем строго внутри [а,		6 ]. На примере функции J ( u ) = — ] f 1— и2
убедиться, что в		общем	случае	здесь	нельзя	полагать
а = а , р= й.
У к а з а н и е .	Пользуясь неравенствами (3), (4), показать, что
	3’ (а + 0 ) < ~ (и)— J —			(ft— 0 )
		и — V
при всех а ■%и,	v -< ft.
7. Доказать,	что выпуклая на отрезке [а, Ь\ функция J (и) аб
солютно непрерывна на каждом отрезке					лежащем стро
го внутри [а, Ь].
8 . Для того чтобы дифференцируемая функция J (и)						на отрез

ке [а, Ь] была выпуклой, необходимо и достаточно, чтобы произ водная J'(u) не убывала на [а, Ь]. Необходимость доказана в тео реме 1 ; докажите достаточность.

9. Для того чтобы дважды дифференцируемая функция J (и) на отрезке [а, Ь] была выпуклой, необходимо и достаточно, чтобы

/"(и) Г5:0	при а ^ и ^ Ь . Доказать. .
10. Для		выпуклости функции J (и)	на интервале а < ы < ф	не
обходимо	и	достаточно существования	такой функции l{v),	а <

44		МИНИМИЗАЦИЯ		ФУНКЦИИ	ОДНОЙ ПЕРЕМЕННОЙ				[Гл. 1
< у < 6 ,		чтобы J(u)^J(v)-\-l(v) (и—о)					при верх и, а<.и<.Ь.			До
казать.		Покажите,	что l(v )= J'(v )		почти всюду.
11.		Если	J {и) выпукла		и	монотонно		возрастает на		отрез
[а, 6],	а	функция	u = z(x ) выпукла			на	отрезке	c ^ . x ^ d ,	и z{x ) е
е [ а , Ь]		при х е [ с ,d], то J(z(x))			выпукла на {с,б\. Доказать.
			§	11. МЕТОД ПАРАБОЛ
В	двух предыдущих			параграфах			минимизируемая		функция
J (и)	аппроксимировалась кусочно-линейными функциями Р п(и), и

исходная задача заменялась последовательностью задач миними

зации функций 'Рп (и). Однако вместо кусочно-линейных функций
в качестве аппроксимирующих функций Р п (и) могут быть выбра
ны и другие классы функций. Если Р п-(ц), л = 0 , '1,	..., достаточно
хорошо аппроксимируют исходную функцию J (и)	равномерно на

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

Итак, пусть / (u )eQ *[a ,					b] и пусть требуется определить точ
ку и* минимума /(и)				на [а,	Ь]	с заданной точностью е > 0 .
О п р е д е л е н и е				1. Тройку точек			{о—т,		v, v-\-h) (h, т > 0 )		на
зовем удачной, если каждая					из	этих	точек		принадлежит отрезку
.[а, Ь] и, кроме того, Д~ = J ( v ) —J ( v —т ) ^ 0 ,								A + = J { v ) —J(v - j- h )^ .О,
Д -+ Д + < 0 .						точек {v—т,			v, о+/г}
Т е о р е м а		1.	Если тройка							удачная,	то
через точки (и—т,			J ( v —т )),		(о,	/(и)),	(o-f/i, J(v-{-h))			на плоско
сти (и,	J) можно провести параболу L(u) ==pu2-{-qu-\~c с коэффи
циентом	р > 0,	причем		точка	w = ------— •—				минимума L(u)		при
							2	р
— о о < ;«< ; + оо удовлетворяет неравенству
			\v— w\ <			т а х {т , h).

Д о к а з а т е л ь с т в о . Искомая парабола является обычным интерполяционным многочленом и имеет вид [19]

t м

g ) . < - » > < ■ - ; - * >

( 1)

§ И]				Метод парабол						45
Так как	тройка точек		{и- -т, v,		v + h}	удачная,			то
				Д-	д+ \	1		> 0
		Р = ( -			h J х-j- h			> 0
					h J х-j- h
и минимум L (и)		на	числовой оси •— ос <					и <	+ ° °	достигается в
точке
		Ш =		V + ■	/I2д- — т2А+
		Ш =		V + ■	тД+ -f ЛД"
					тД+ -f ЛД"
Отсюда	следует,	что
			1	[Я2 1Д-\| —	т2 )Д+Ц <		— max {Л,			т}.
			2 т \| Д + \| + Л \| Д - \|

Последнее неравенство доказывается элементарно, простым рассмот

рением случаев h2J А— J — т2 \|Д +\|>0		и Л2\|Д~\|—-т 2\|Д + \| < 0 . ^
Опишем метод парабол в сочетании с методом золотого се
чения. Пусть сделано k	шагов ( k ^ 3 )	метода золотого сечения и
найден отрезок [с^, bk],	содержащий точку минимума и* функции
J (и) на [я, 6 ]. Примем	гипотезу о том,, что функция J (и) на от

резке [ад, bh] хорошо аппроксимируется параболой. Если строго квазивыпуклая функция J (и) достаточно гладкая на отрезке [ah, bk] и сам отрезок [a*, bk] имеет достаточно малую длину, а < а к^ и * ^ ~ b h < b , то такая гипотеза вполне правдоподобна, поскольку в окре стности внутренней точки минимума гладкая функция, вообще го воря, близка к параболе. Далее возьмем одну из точек ип, произ водящих золотое сечение отрезка [a*, bh], и вычислим значение J (Uk) (если только оно еще не было вычислено на последнем шаге

метода золотого сечения).	Если bk— Я д ^ is, то точку uk принимаем
за точку минимума и*, и	процесс на этом заканчивается. Пусть

bk—«А>'е. Тогда проверяем, является ли тройка {ал, Uk, Ьк} удач ной или нет. Если эта тройка неудачная, то делаем следующий шаг

метода золотого сечения, находим отрезок {Яй+ь bk+i] и с ним по ступаем так же, как с отрезком [a,k, bk].

Пусть тройка		(aft, uk,	bk} удачная,		и пусть	wk — точка мини
мума	параболы	( 1 )	с v=Uk,	т = т h— Uh— a-k,			h = h k = b k —
— ик.	Согласно теореме 1
		IЧ — wk I < у		max ihk> **}.
Положим ak=m ax { \|uk — wk \|; e/4}.
Нетрудно проверить,			что uk — ak,		uk + ak 6	[ak, bk\. Вычислим
	Ak = J (uk) — J {u k — a k) , b t =				J (uk) — J (u k +		ац).

МИНИМИЗАЦИЯ

ФУНКЦИИ ОДНОЙ

ПЕРЕМЕННОЙ

\Гя. 1

В зависимости

от

знаков

Ак ,

возможны 4 случая.

Дй < 0 ,

A t < 0 , А/Г +

Дй~< 0 . Это значит, что тройка {ик — ак, ик,

ик 4 - ак} —

удачная.

Полагаем

ak+ i = u k — ak,

Ьк±\ = ик -f- ак

отрезком

[ай+ь

6 ^+1] поступаем так

же,

как с

предыдущим

отрезком

[ай, Ьк].

2. AJ-< 0 ,

Afe".>0. Тогда полагаем ak+\ =

ик, Ьк+[ = Ьк и с отрезком

[afe+i, 6 й+1] поступаем так же,

как

[а*, Ьк]. 3.

Д Г > 0 ,

Д ^ < 0 .

Тогда принимаем ай+1 = ай, Ьк+\ = ик и с

отрезком

[ай+ь 6 fc+i] пос

тупаем так же, как

с \ак, Ьк]\ 4. А ^ > 0 ,

A t > 0 . Тогда

на [аЛ, Ьк[ де

лаем

следующий шаг метода

золотого

сечения,

находим

отрезок

[ай+1, 6 fe+i]

и с ним поступаем

так же,

как с предыдущим

отрезком

[ай, Ьк]. Впрочем, если заранее известно, что функция J (и) строго

квазивыпукла на [ай, Ьк\,

то последний

случай возможен

лишь при

АГ = Дк" = 0 , т. е.

J (и) =

J* —

inf

(и)

при ик— аА-< и <^ик + ак. Здесь остается

принять

качестве точки

минимума любую точку из отрезка

[ик — ак, uk -f a A],

и процесс

поиска на этом заканчивается.

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

вательность вложенных стягивающихся отрезков [ак, Ьк]\

[ай+ь 6 *+ i] с : [ай, bk], Ьк+\— ай+] <

(Ьк— ак).

Отсюда видно, что на классе функций Q*[a, b] метод парабол по скорости сходимости не уступает методу золотого сечения и йенам-' ного уступает ему по числу вычислений значений функции J(u ). Если же функция / (« )e Q *[a , b], хорошо аппроксимируется пара болой хотя бы в некоторой окрестности точки минимума, то метод парабол может оказаться гораздо лучше плана Фибоначчи и по скорости сходимости, и по числу вычислений значений функции. Разумеется, это не противоречит оптимальности плана Фибоначчи, ибо этот план был выработан из расчета нд «наихудшую» функцию из класса Q*[a, b], что не исключает возможности построения бо лее эффективных методов поиска минимума на «хороших» под классах из Q*[a, Ь]. Для функций, не являющихся строго квазивыпуклыми, описанный метод парабол приводит, вообще говоря, лишь к точке локального минимума.

Нетрудно модифицировать метод парабол так, чтобы можно былс пользоваться параболами ( 1 ) при выполнении лишь условия

не требуя неположительности величин Д+, А- . Од

X + ' Т < ° -

нако при этом следует иметь в виду, что точка минимума такой

s щ

О некоторых других методах минимизации

параболы "на отрезке [v—т, v-\-h] может не совпадать с точкой ми нимума параболы на всей числовой оси.

Другой вариант метода парабол описан в {2 0 1 ].

§12. О НЕКОТОРЫХ ДРУГИХ МЕТОДАХ МИНИМИЗАЦИИ

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

Здесь мы остановимся на одном методе поиска глобального минимума функций, основанном на информационно-статистическом подходе [212], [213]. Для некоторых достаточно широких классовфункций (подробное статистическое описание этих классов см. в работе [2 1 2 ]) удается построить оценки апостериорной вероятности расположения глобального минимума на основе уже проведенных испытаний, заключающихся в вычислении значений минимизируе мой функции в определенных точках ио, щ , ..., ц* из отрезка [а, Ь]. На основе этих оценок затем можно получить оценку максимума

информации о расположении точки минимума и указать простое правило выбора следующей точки ии+\. Отсылая читателя за под робностями к работам [212], [213], здесь ограничимся лишь опи санием самого метода.

Пусть требуется минимизировать функцию J (и)	на	отрезке
[а, Ь]. Процесс поиска минимума начинается с двух	точек	и0= а ,
Ui = b, и вычисления величины

\J Ы — J (цр)1

“1 — “q

После чего полагается

f гДх при А1 > 0 ,

1 1 при Ах = 0,

где г — const> .'1 представляет собой параметр алгоритма, выбирае мый вычислителем. В качестве следующей точки m берется точка

U2 = Y (u i + “ о)	J j u J — J (ц„)
U2 = Y (u i + “ о)	2т1
Предположим, что точки «о, Щ,	“fe (6 ^ 2 ) уже известны.

Произведя при необходимости перенумерацию этих точек, можно считать, что а = и й< .и i < ... <.Uk-\<.Uh— b. Далее определяются величины

МИНИМИЗАЦИЯ

ФУНКЦИИ

о д н о й ПЕРЕМЕННОЙ

\Гл 1

Ак =

шах

\ J ( u S) - J ( l l s - l ) \

l<s<fc

Us — U S- 1

ПРИ ДА>

°>

[

1 . при ЛА=

0 .

Затем составляется функция

Rk is) =* Щ (и, -

Из-,) + —

s l- - - (Us-l)|2-- 2 [J (и5) + J

(и^

)]

.Uj . j

целочисленного аргумента s,

простым

перебором

значе

ний Rk (s) определяется

тот

номер

s =

sA,

для

которого

Rk (sk) =

шах Я* (s). Если

— us _ i < 6 ,

где

е >

0 — заданная

точность,

l<s<fe

то процесс поиска прекращается и точка uSft принимается в качестве искомой точки минимума. Если же и5д,— «Sfc- i > е , то полагаем

ый+1 = — (Us*	Us*->) —	J (USft)	7	(a sk - i )
ый+1 = — (Us*	Us*->) —	2mk
		2mk
Из определения mfe, очевидно, следует		nSfe_ i < u ft+I < u Sfc.			Теперь ос
тается перенумеровать точки	и0, uv . . .	, uk, Uk+i	в	порядке	возраста

ния и перейти к определению следующей точки ин-\-2 аналогичным образом. Метод поиска минимума описан.

В качестве иллюстрации приведем результаты применения опи санного метода для отыскания минимума функции

/ (и) = sin и -}- sin		10
		-----'и -f- 1п и— 0,84«]+ 3
на отрезке 2 ,7 ^ и < 7 ,5	[213].	График	функции J (и)			приведен на
		рис. 6 , там же вертикальными
		штрихами на оси Ои отмечено рас
		положение		точек	щ	при	г = 2 ,
		е = 0,01;	группа из		14	точек, распо
		ложенных вблизи точки глобально
		го минимума, изображена черным
		прямоугольником.			Как видим, из
		28 точек, в		которых		вычислялись
		значения	функции		в	ходе поиска
		минимума, большая часть (21					точ
		ка) расположена вблизи точки гло
		бального	минимума.
С целью проверки	описанного метода			были	проведены		чис

ленные эксперименты на большом количестве задач минимизации при различных г > 1 , е > 0 [212]. В частности, была проведена ми

$ щ		О некоторых	других	методах минимизации	49
нимизация'2 0		функций, представляющих собой выборку из функций
вида
		J (и) = а0+ ^	( а £sin	-J- b{ cos
		i=i
где	\|а*\|^1,	\|6{ \| ^ 1,	14, коэффициенты а,, Ь{ и целое чис
ло	N представляют собой значения независимых равномерно				рас

пределенных случайных величин. При г = 2, е = 0 ,0 0 2 среднее число вычислений значений функции оказалось равным 29. При этом

лишь для одной из 2 0 функций был	найден локальный	минимум
вместо глобального. Поиск минимума	при г = 3, е = 0 ,0 0 2	для тех
же функций потребовал в среднем 40	вычислений значений функ

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

2 . Кратко остановимся на методах минимизации, когда на зна чения функции /(и ) в каждой точке и накладываются случайные ошибки или, как говорят, помехи. Такая ситуация, в частности, имеет место в том случае, когда значения функции J (и) получают ся в результате измерений какой-либо физической величины. При наличии помех многие рассмотренные выше методы непригодны для поиска минимума функции, и здесь целесообразно пользовать ся методом стохастической аппроксимации [45], [230].

Опишем один из вариантов этого метода. Наблюдаемые в экс

перименте значения J (и) в точке и обозначим	через z(u). Будем
предполагать, что наблюдения J (и) возможны	в любой фиксиро
ванной точке и, — о о < и < -(-о о , и не содержат	систематических

ошибок. Тогда для поиска минимума функции /(«) при — о о < ц < <-|-оо может быть использована следующая процедура Кифера— Вольфовица [45], [230]:

Мл+1 = ип — ап	г (и„ + с„) — z (ц„ — сп)			1, 2,	(D
Мл+1 = ип — ап		Сп		1, 2,	(D
		Сп
где последовательности	{ал}, {с„}	заданы и		удовлетворяют условиям
				оо
а „ > 0 , сп > О, П т ап = П тс„ = О,			= + о о ,
Л -» о о	П -* о о			п—1
		Л = 1		п—1	(2)
					(2)
Например, можно взять а п — — ,		сп = - i - ,		п — 1 , 2 , . . . .	При доста-
	п	п и

точно широких предположениях относительно функции J (и) и вероят

<<< < Предыдущая 1 2 3 45 / 385 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ