Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

25.10.2023

Размер:

14.17 Mб

Скачать

☆

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

60	М И Н И М И З А Ц И Я Ф У Н К Ц И И М НОГИ Х ПЕРЕМЕННЫ Х	\Гл. 2
тельства	теорем 4 и 5, при выполнении (12) и (14)	с некоторой

константой |.i в неравенстве ( 1 1 ), по крайней мере, можно принять и = - j- . Если же достаточно гладкая функция сильно выпукла

с константой х в (11), то в (12), (14), по крайней мере, можно взять ц = х . Можно ставить вопрос о более точном определении этих констант:

X = х

inf

(ц) +

( 1

J (») — J (au +

(1 — ct) v)

( 11),

u,v£U

o(l — a)|u — o|a

0 < a < l

И =

1*1 =

inf

(j"(u)l,

(14);

ueu

ISi=i

и аналогично в (12). Из изложенного

ясно,

что

щ >

х для [любого

х из (11)

и хх;> -^ -

для

любого ц

из

(12),

(14),

частности,

х4 >

Ниже в

ряде случаев

от

градиента /'(и)

сильно

выпуклой

функции

будем

требовать

выполнения

условия

Липшица:

[/ '(« )— J'(v) |^L|u— п| при всех u, v^ U , L =

co n stX ). Как связа

на константа L с х и ц? Применяя к левой части

(12)

неравенство

Коши — Буняковского

используя

условие

Липшица

для

J'{u),

сразу

получим

в частности

А тогда

А ^ ц ^ х ^ х

при любом х > 0

из

( 1 1 ).

и* — точка

Т е о р е м а

6 . Если

минимума

сильно

выпуклой

функции J (и)

на выпуклом множестве U,

то

j и — ц*|2 <

—

[J (и) — /(«*)]

при всех

u^U,

(15)

где х > 0

— константа

из

(11).

Если,

кроме того,

(и) в С1 ((/),

то

р|ы —

«*| 2 < ( J' ( u ),

и — и"),

ц I и

и* |< |J' (и) |,

0 < J ( u ) — J ( a * ) <

—

\J'(u)\*

(16)

при всех

u st/ ,

где

ц > 0 — константа

из (12)

или

(14)

^в

силу

замечания к теореме 5 в оценке

(15)

можно взять х ==

Д о к а з а т е л ь с т в о .

Если

неравенстве

(13)

примем

v = u*

и учтем, что

J (и*)

то сразу придем к

(15).

§ П

Постановка

задачи.

Обозначения.

Вспомогательные сведения

Так как согласно теореме 3

в точке минимума

(/'(и *), и— и * ) ^ 0 ,

u ^ U , то из ( 1 2 )

при v — u* получим

pi I и — и* |2 < (/ '(« ),

и — и*) <

\J' (и) |•\и— и*\.

Первые два неравенства

(16) доказаны. Наконец, если

восполь

зуемся правым неравенством

(9) при v = u*, то

J {и) — J

(и*) <

( J 1 (и) ,

и — и*)

|J'

(и) |■|и — и* |

и отсюда с учетом уже

доказанной

оценки

р|«— « * |sg: (/'(«) |

получим третье неравенство

( 1 6 ) .^

Т е о р е м а

Если

J ( и ) — сильно

выпуклая

непрерывная

функция на замкнутом выпуклом множестве U (в частности, воз

можно,

U = E m),

то:

/ (и)

ограничена

снизу на U, т. е. inf J (и) =

= / * > ’— оо; 2 )

существует и притом

единственная

а£С/

точка

«*е£/,

такая, что

множество М (v) =

{ и : u^U , J ( u ) ^ J (v)}

ограничено при любом v^U .

U — ограниченное

Д о к а з а т е л ь с т в о .

Если

замкнутое

множество, то

утверждения

теоремы следуют

из

классического

анализа

[126].

Пусть

U — неограниченное

множество.

Возьмем

произвольную точку

В силу непрерывности /(и) для любого

е > 0 ,

в частности

при

е = х > 0 ,

найдется

такое

6 > 0 ,

что

|/(и)— 7 (о )| ^ х

при

всех

н е!/ ,

|и— о | ^ б . Следовательно,

J ( u ) ^ J ( v ) —х при всех И(=Н,

|и— о | ^ б . Пусть теперь

|и— у | > 6 .

Тогда величина

а0 = ----- ------< 4 ,

и при а = ао из

(11)

получим

1« — о)

а0J (и) > J (v + а 0 (и — v)) — (1 — а0) J

(v) + х а 0 (1 — а 0) \и— v \2.

Так как

а0|и — & |=

б, то

J ( v +

a0 (u — о)) — Т (и )„> — х

силу оп

ределения 6 , и

a0J (и) >

— х + а0J (и) +

ха0 (1 — а0) |и — v |2,

или

J (и) >

/ (v) +

X (1 — а0) I и — v I2 -----— =

J (v) —]

Оо

— %\и— ° | ( б + “^ ^ + х | « — а |2

при всех

и 6 U,

|и — v |>

6 . Далее воспользуемся неравенством

l“ - ' ’ l ( e + T	) <	T l“ ~ ” l*+ T	(	8 +	' j ) ‘>
вытекающим из очевидного неравенства 2 1аЪ \|<				а2 + Ь2.		Будем иметь
J ( u ) > J ( v )	+	f \ u - v \ 2- f ( b	+	±	- y	(17)

62		М И Н И М И З А Ц И Я			Ф У Н К Ц И И М НОГИ Х ПЕРЕМЕННЫХ					[ Г л . 2
при всех		и 6	U,	\|и — и\|	б. На самом		деле	это	неравенство	верно
при	всех	и £ U,		ибо
для	точек u £U,			\|и — и\| < 6 также		имеем		7 (« )> / (у)— x > J ( v ) - {-
+ у	х62— у		х ( б + у J		> J (о) +	у	х >	и12 —	х(6+ Т ) 2-
	Из оценки (17) тогда				следует,	что

при всех

u £ U ,

т.

е.

J (и)

ограничена

снизу

на U.

из

(17)

имеем

(и)

оо

при

|ц|-»оо,

и £U . Тогда

для

любого числа

Л > 0 ,

частности

при

А = 17 (у) |,

найдется

такое

О,

что

J (и) >

|J (и) | при всех u £ U , |и— v\i>B. Отсюда ясно,

что

J * = i n f J ( « ) =

inf

7 («) < 7 (ц ).

«6£/

|и—ч|<В

Так

как

пересечение

множества

U и шара |и—

есть

замкнутое ограниченное (и даже выпуклое)

множество, то непре

рывная функция J (и) на этом пересечении достигает своей ниж

ней грани

некоторой

точке

и*,

причем

/(и*) = 7 * .

Единствен

ность такой точки ы* следует из строгой

выпуклости

J (и) и тео

ремы 1 .

Ограниченность множества M(v) =

{и : u^U , J (и)

(о )}

при

любом v ^ U вытекает из неравенства (17):

|и —

при

всех и еМ (v). ±

По

поводу

других свойств

выпуклых

функций и выпуклых

множеств см. также § 3, 4. Здесь мы докажем еще

две

леммы,

полезные в дальнейшем.

Л е м м а

1. Пусть

U — выпуклое

множество

Ет, J (и

е С ‘ (£У)

и J'(u)

удовлетворяет условию Липшица: |J'(u )—J'(v)

^ Ь\и— v\ при всех и, ае£/, L = const>0. Тогда

7 (v) — J (и) >

(J' (v),

v — и )----- — \v— и |2

при всех и,

v £ U .

( 18)

Д о к а з а т е л ь с т в о .

Положим

формуле

(5)

h =

v — и.

По

лучим

7 (v) — 7 (и) =- J

(/' (и -f a (v — и)),

v — u.)da — (J'(v),

v — и) +

S П

Постановка

задачи. Обозначения. Вспомогательные

сведения

+ | (J' {и +

а (у — и)) — J'

(v),

v -— и) da.

Поскольку

(J1 (и + а (v — и)) — J' (о),

v — и) >

— |J' (и + а (v — и)) —

— J'(v)\-\v — и \ > — L { 1 — a ) \ v -

«|2,

0 < а < 1 ,

то

(v) — J (и) > (/' (v),

v — и) — L |а — и |2 J (1 — a)da =

(J’ (v),

v — u )----- {- L \ v — u|2. A

Л е м м а 2.

Пусть

имеется

последовательность

{ап},

п = О,

1 ,

2 ..........

такая,

что

ап > О,

ап— <зп+1 >

Ла£

при

всех

п > -п 0 > О

(А = const> 0). Тогда

| |

а п< ^ ~ °—— при всех п^>па.

Ап

Д о к а з а т е л ь с т в о .

С учетом условия

леммы

имеем

1_________ } _

~ ak + l

а/г

a k + l

a k

akak + l

a k + l

при всех k > п 0. Просуммируем это неравенство

по k от п0 до п — 1

и получим

—----------— >Л(/г — /г0), откуда

—

> Л ( / г — п0),

или

ап

ап0

ап

а п< ---------------- при всех п >

/г0.

Однако ----- ------ <

п°~*~

при

А (п — п0)

п — па

/г> па,

следовательно, а Л<

п°

1 , п > пй.

Ап

Упражнения.

1. Доказать, что пересечение

любого

числа

вы

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

выпукло.		2,..., р)
2. Пусть функции /{(«)(/= 1,		2,..., р)	выпуклы	на множест-
ве 1 U. Доказать,		р	atJi (и) выпукла на U
ве 1 U. Доказать,	что функция J	(и) = £	atJi (и) выпукла на U
при любых aj'1^ 0 .		£—1.
при любых aj'1^ 0 .
3. Привести	пример двух выпуклых		функций,	произведение

которых невыпукло. При каких условиях произведение двух выпук-

1 Во всех упражнениях этого параграфа предполагается, что V — выпук лое множество в Е т.

64	М И Н И М И З А Ц И Я	Ф У Н К Ц И Й МНОГИ Х ПЕРЕМЕННЫ Х					[ Г л . 2
лых функций выпукло? Достаточно ли для						этого положительности
сомножителей?
4.	Пусть функции J a		(и) выпуклы		на	U при всех	а е Л , где
А — некоторое заданное			множество		•индексов. Доказать, что
функция / (и) — sup Ja («)		ВЫПуКЛЭ НЭ U.
	аеА
5. Функция /(и) выпукла на U тогда и только тогда, если
функция g (t) = J {u-\-t (v— и))				одной	переменной t, O s ^ f^ l, яв
ляется выпуклой при любых и,				y et/ .	Если	J (и) сильно выпукла,
то g(t)	сильно выпукла.	Доказать.
6.	Если J (и) выпукла на U,			то
		II		П
	J (Е а‘и<) <ЕaiJ №
при любых		£=1		£=1
при любых			П
			П
	а: > 0 ,		£ а	г = 1 ,	u.€t/,

£=1

где п — произвольное натуральное число. Доказать.

7.	Доказать, что J (и)				выпукла на	U тогда		и только			тогда,
когда	множество		А = { а — (и1....... ит, 1) — (и, £)					: и е У ,		£ ^ / (и )}
выпукло в пространстве Ет +ь								U необходимо и
8.	Для выпуклости			функции / ( « ) e C ‘ (t/)			на
достаточно,		чтобы	J (и )—J(v) ^ (J'{v),			и— v)	при		всех	и,	y et/ .
Доказать (см. теорему 2).						на U достаточно,
9.	Для	выпуклости		/ (a )e C 2{t/)							чтобы
(/"(ц)\|, 1)^=0 при всех				wet/ и всех £ е £ т . Доказать (ср. теоре
му 5).							1, 2,.... п)
10.	Доказать,		что если		функции /, («) (i =					выпуклы
на U, то множество t/ ]= {« :« e t/ ,							«=1,		2, ..,	п}	выпук
ло (fli — заданные числа).					на U, то множество М(и) =					{и : u^U ,
11.	Если	I(и)	выпукла
J ( u ) ^ . J ( v ) }		выпукло при любом y et/ . Доказать. Верно ли обрат
ное утверждение?

12. Функция J(u ), заданная на выпуклом множестве U, назы

вается	квазивыпуклой, если / ( < х у + ( 1 —	а) и) ^ m a x { / ( и ) ; / ( у ) }
при всех и, y et/ и а, 0 ^ а ^ 1 . Всякая		ли	выпуклая	функция
квазивыпукла и наоборот? Доказать, что J (и)			квазивыпукла на U
тогда	и только тогда, когда множество	М ( у )	= {« : wet/,	J (и

</ ( у )} выпукло при всех yet/ .

13.Функция /(«), заданная на выпуклом множестве U, назы вается равномерно выпуклой, если существует непрерывная строго возрастающая функция у (t), 0 ^ t < + °o, у (0 )= 0 , такая, что

J (аи + (1 — а) у) < а/ (и) + (1 — а) J (у) — а (1 — а) у ( |и — у |)

S 2]				Градиентный метод			65
при всех и, v&.U,			OegCa^l. Доказать,			что если J (и) равномерно
выпукла на замкнутом выпуклом множестве U, то все утвержде
ния теоремы 7 сохраняют силу.
14. Доказать,			что J (и) —au2 + bu + c,			и ^ Е х — сильно	выпукла
при любом а > 0 .
15.	Пусть	J	(и) — — (Аи,		и) — (6, и), где Л — заданная сим-
метрическая матрица				порядка	mXm, b — заданный вектор из Ет.
Доказать, что: а)			если	(Л\|,	при всех g e £ m, то 7(и )		выпукла
на £„,;	б) если А — положительно определена, то J (и) сильно вы
пукла	на £,„,	причем в качестве константы % из неравенства (11)
можно	взять	х =		где	Xi — наименьшее собственное число

матрицы Л. Вывести формулы J ' (и) = А и —b и J"(u) —А.

16.Пусть J (и) = |Аи—b |2, где Л — заданная матрица поря

пХт ,	Ь — заданный вектор из Е п. Доказать, что J(u)			выпукла
на Е т.		Если Л *Л — невырождена, то /(«)	сильно выпукла на Ет
(здесь		Л* — транспонированная матрица).	Найти / '(«),	J"(u).
		§ 2. ГРАДИЕНТНЫЙ МЕТОД
Пусть дана функция /(«) е С 1 (£ т ). Как известно [126], в точ
ке и,	в	которой 1 '{и ) Ф 0, направление наибыстрейшего		возраста

ния функции совпадает с направлением градиента J'(u) в этой


точке,	а направление наибыстрейшего убывания — с				направле
нием	антиградиента — /'(и). Это следует из формулы				(1.2)	и не
равенства		Коши — Буияковского:	— \|/'(м) \|\h\^	(/'(и),		h) ^
^ ]£ (« ) \|\|/г 1, если учесть, что правое			неравенство	превращается

в равенство только при h = aJ'(u ), левое—только при h = — aJ'(u), a = co n st^ 0 . Это свойство градиента может быть положено в основу итерационного метода минимизации функции, известного

под названием градиентного метода [3, 19,									27, 35, 46, 75, 79, 82,
109,'135,	149,	155,	161,	164,	170,	177,	188,	193,		229,	230,	235,	239,
251— 253, 260]		и др.
Этот метод предполагает выбор некоторой начальной точки «о-
Общих правил выбора и0 нет; в тех случаях,									когда имеется априор
ная информация об области					расположения				искомой точки				мини

мума, точку « о стараются выбрать в этой области. Имея и0, далее строят последовательность {ип} по правилу

url+x ^ u n — a nJ'{un),	ап — const > 0	{п =	0, 1 , 2 , . . . ) .
Если Е { и п) Ф 0 , то можно подобрать такое a n> 0 ,			( 1)
Если Е { и п) Ф 0 , то можно подобрать такое a n> 0 ,			чтобы /(wn+1) <
< / (« „ ). В самом деле,	из формулы (1.2)	следует
J [ип+х) — J (ип)		0{0-п)	< 0
J [ип+х) — J (ип)			< 0

&/1

3 Ф. п. Васильев

ьб

М И Н И М И З А Ц И Я Ф У Н К Ц И И МНОГИ Х ПЕРЕМЕННЫ Х

[ Г а . 2

при всех-достаточно малых а Л> 0 . Если J'(un) = 0, то ип — стацио нарная точка, и в этом случае процесс (1) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки ип для выяснения того, достигается ли в точке а минимум /(гг) или нет.

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

= min £,*(«),	g n( a ) = J ( u n — aJ' (ип)).		(2>
а^О
Отсюда сразу имеем J {ио)	{u\)	(и2) ^ ...
Возникают вопросы. Возможен ли выбор а п из условия			(2) ?
Будет ли lim J («„) — J* — inf J (ы)?		Для получения положитель-
	«££ш

ного ответа на эти вопросы на функцию /(п) е С ! (£,„) приходится

накладывать дополнительные,		довольно		жесткие ограничения.
Т е о р е м а	1. Пусть функция
J	(и) 6 С1 (Em),	inf	J (и) =	J* > — оо,

иградиент У (и) удовлетворяет условию Липшица: |/'(«)— Л (у) |<.

^.Ь\и— о|, L = const>0. Пусть w0 — произвольная фиксированная начальная точка, и последовательность {«„} получена из условий

(1), (2). Тогда lim /'(u n)= 0 .

rwoo	выпукла и множество М(и0) = {и :
Если, кроме того, J (и)	выпукла и множество М(и0) = {и :
J ( u ) ^ J { u 0)} ограничено, то	последовательность {«„} является

минимизирующей и любая ее предельная точка будет точкой ми

нимума J (и) на Ет,	причем в случае единственности точки мини
мума к ней сходится	вся	последовательность		{«„}. Справедлива
оценка
0 < 7 (u „ ) — J* < 2 D * L - — ( п = 1, 2 , . . . ) ,					(3)
,		П
где D = sup \|и — v \|— диаметр множества М (и0).
ы.абАЦыо)		сильно выпукла на Ет, то
Если J(u), кроме того,		сильно выпукла на Ет, то
О	J («„) — J -С !У (“о)		J I Яп>
K ~ u * \| 2 < —		[J(ua) — r ] ( T	( Л - 0 ,	1 , . . . ) ,	(4)
	V-

где q — l -----

— , 0 < q < 1, p = co n st> 0 из теоремы 1.4.

# 2] Градиентный метод 67

Д о к а з а т е л ь с т в о .

Если

при

некотором

п ^ О окажется

J'(u n) — 0, то из условий

(1),

(2)

формально получаем ип — ип+ 1—

, и утверждение теоремы lim/'(wn) = 0

становится

тривиаль-

П - > оо

( п = 0,

ным.

Поэтому

будем

считать

]'{ип) Ф 0

...).

Так как

J (u n+l) = g n(a n) ^ g n ( a ) = J ( u n—а Г ( и п))

при

всех

то

из

неравенства (1.18)

при v = un, и = и п— а Г ( и п)

имеем

J (и„) — J («„+i) >

J (ип) — J (a„—

aJ' (ип)) >

^ 1 —

|/' («„) |2

при всех а > 0

и всех п — 0,

2, . . . . Следовательно:

J (и„) — J

(un+1) >

шах а ( 1 -----a )\ J'

(un) I2 =

a^O

= - ^ | / ' K ) l 2 >

(n =

1 , . . . ) .

(5)

Таким

образом,

последовательность

{J («„)}

стррго

убывает.

Но

J (ип) ></*>-— оо,

поэтому

существует

lim J { u n),

/(«„) —

— J(un+i) - * 0 при я -> оо. Из оценки

(5)

л-freo

тогда

имеем lim J' (ип) =

f W o o

Пусть теперь

/(и) -выпукла, и множество М(ио)

ограничено.

Поскольку М(и0),

кроме

того,

замкнуто в

силу

непрерывности

/ (и)

(и даже выпукло), то I(и)

достигает своей нижней грани на

М (п0),

а стало

быть,

на

Ет,

хотя

бы

одной

точке

М {и0)

: J ( u * ) = J * .

Тогда

с помощью

неравенства

(1.9)

имеем

0 <

Ю - / ( О < (/ '(« „ ),

uK- u * ) < D \ J ' ( u a)\

(п = 0 , 1 , . . . ) .

(6 )

Так

как J' (ип)-*-0,

то

отсюда

следует

'lim J

(un) = J

(и*) =

J*,

т.

е.'

последовательность

{ип}

является

П —> э о

Так как

(ял} 6

минимизирующей.

6 М (и0), то последовательность {пл} имеет хотя бы одну предельную

точку v* = lim	. Но J (и)	непрерывна,		поэтому Г		= lim J (ил.) =
k~> oo						/г—* оо
=«/ (к*). Если J («) достигает своего минимума в единственной точке
«*, то lim ип =	и".
П —* о о
Для доказательства оценки			(3) обозначим ал =			/ («,,)— /*.	Из
неравенств (5),	(6) следует	— сл+1>		1/'.(«„) \|2, a„< D \| / ' (ил)\|,
а тогда
			(п =	0,	1,2, ...)•
Так как an> 0	(если ап= 0,	то	ип — точка		минимума), то с		по
мощью леммы 1.2 отсюда получаем оценку (3).
3*					,

68	М И Н И М И З А Ц И Я Ф У Н К Ц И И М Н О ГИ Х ПЕРЕМЕННЫХ	[Га . 2
Наконец, пусть J(u ) сильно выпукла, и по-прежнему		J (и) 6
£ С1(£ m),	J ' (и) удовлетворяет условию Липшица. Согласно	теоре

ме 1.7 тогда сохраняют силу все предыдущие рассуждения. Докажем

оценки (4).

Из теоремы

1.6 имеем 0

•< —

I /' (и ) I2.

Отсюда и

из оценки

(5)

вытекает

ап— а^-н >

ап, или

ап+\ < ( - ~ ) а п = Я ^ п (П = 0,

Следовательно,

ап < а 0<7" (п = 0, 1, . . . ) — первая

из оценок

(4) полу

чена. Вторая оценка (4)

непосредственно следует из

первой

и нера

венства

(1.15).

Остается

заметить,

что

0 < < 7 = 1

Л .

1, ибо

р. < L (см. замечание к теореме 1.5). А

Для

функций /(ы) е С 1 (£,„)

описанный

метод

скорейшего

спуска при т = 2 имеет простой геометрический смысл:

оказывает

ся, точка ип+1, определяемая условиями

(1),

(2),

лежит

на луче

и ( а ) = и п— aJ'(u n) (а ^ О )

в точке

его

касания

линии

уровня

Гп+1 = {м : /(и)

= / (« n+i)}.

Это вытекает из следующих двух факто

ров: 1) градиент функции в фиксированной точке v всегда перпен

дикулярен линии уровня Г (о) = {и : J (и) = J (v)}		в точке v. В самом
деле, если u — u{t) некоторое параметрическое		уравнение линии
уровня Г(и), то J ( u ( t ) ) = / ( о ) = co n st. Поэтому
=	и ( 0 ) = о ,
at

т. е. градиент в каждой точке Г (и) перпендикулярен касательному направлению к Г (о) в этой точке; 2) направление J' (ип) является касательным к линии уровня Гп+ь что в силу предыдущего равно сильно равенству (J'(un), J'(un+1 ))= 0 . Последнее следует из усло вия (2) и формулы (1.4)

g'a (« л )		=	— W (“ л ). J' («л-н)) = 0	при а п> 0.
Из рис. 7,	8	видно, что чем ближе линия уровня /(■«)= const
к окружности,	тем		быстрее сходится метод	скорейшего спуска.

Р и с. 7

Р и с. 8

§ 2}	Градиентный метод	69
	В тех случаях, когда поверхности уровня сильно вытянуты, то
этот метод может сходиться очень медленно. Приемы		ускорения

сходимости в таких случаях будут обсуждены ниже, в п. 4.

2. Известны и другие способы выбора величины а„ в формуле

(1). Простейшим	из них является выбор		an = cc= const. При этом
на каждом шаге	проверяется	условие	монотонности: J (ип+1) <
< J ( u n). Если оно нарушается,		то а дробится до тех пор, пока не

восстановится монотонность; время от времени полезно пробовать увеличить а с сохранением монотонности.

В тех случаях,			когда заранее известна величина,				J* =	inf J (и),
								и£Ет
то в равенстве (1)			можно взять		a n= [ J ( u n) — /*]\|/'(ггп) )-2—это
абсцисса точки пересечения прямой / = /*						и касательной к кривой'
J= g n {a )	в точке		(£ п (0),'0)	плоскости (/,		а ). Еще	два	способа
выбора	а„	можно	получить	из	методов, описанных		в §	3, 5	при
U= Em.					а п выбран, то итерации
3. Если		способ определения						(1)	про

должают до выполнения тех или иных критериев окончания счета.

На практике часто	используются критерии	\|ип+1— «п \| ^ е, или
\|/(«n+i) — /(ыэт)\| ^ е ,	или \|/'(ып)\|<Св и другие;	возможны сочета

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

Следует заметить также, что вблизи точки минимума градиент J ' (ип) близок к нулю, и метод (1) становится слишком чувстви тельным к выбору а п, отыскание более точных приближений точки

минимума и*	затрудняется, так как расстояние				\|ип— и* \| пере
стает уменьшаться.		Поэтому вблизи		точки	и* целесообразно
использование	других,	более	тонких методов, опирающихся на
квадратичную	аппроксимацию		функции	в окрестности каждого
приближения	(см. § 7,	8).

4. Как уже отмечалось, метод скорейшего спуска и другие , варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функции J (и) сильно вытянуты и функ ция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к рез кому изменению значений функции — эта группа переменных характеризует «склон оврага», а по остальным переменным, за дающим направление «дна оврага», функция меняется незначи тельно (на рис. 9 изображены линии уровня «овражной» функции двух переменных). Если точка лежит на «склоне оврага», то на правление спуска из этой точки будет почти перпендикулярным к

направлению	«дна оврага», и в результате приближения {ип},
получаемые	градиентным методом, будут поочередно находиться
то на одном,	то на другом «склоне оврага». Если «склоны оврага»

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

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