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

240 МЕТОДЫ М И Н И М И З А Ц И И В ФУНКЦ И ОНАЛЬНЫ Х ПРОСТРАНСТВАХ

[Гл.

в

Теоремы 1,4 служат основой многих теорем существования

решений экстремальных задач; примеры таких задач см.

ниже

в

функционалу J (и) в точке v ^ U , если J {и)

(v) -+- (/, u—v) при

всех

выпуклый и принадлежит Cl (U), где U — выпуклое

Если /(«)

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

согласно теореме 2.1.2 J (и)— I ( v ) ^ ( J ' ( v ) ,

и— и)

при всех u^U ,

т. е. l — J'(v ) — опорный функционал к J (и)

в точ­

ционал с ф 0, определенный на 5 , называется

разделяющим мно­

жества X и У, если существует действительное число а,

такое,

что

(с, х ) ^ а ^ (с,

у)

при всех

х ^ Х и г/еУ,

или,

иначе говоря

inf (с, х) >

a >sup

(с, у).

х € Х

y £ Y

либо s u p (c ,y )< a ,

то

говорят

о

Если

либо

inf (с, х ) > а ,

л-ex

ysY

(с, х) — а,

то функ-

строгом разделении этих множеств. Если inf

Поэтому u £ U

и

K U

+

b = J(v) — L\\v — w0|— 8(1 + L) + Ь =

=

J{v) — L |v — и + и — v01 — 8L < / (о) —

— Z-1|гг— v |+

L |и — о0|— L8 < J (ь) — L\\u — п||.

Таким'образом,

если х =

(|, и) 6 К,

то и 6 U и £ < / ( ц ) — L\\u — v\\v

т, е. х 6 X. Следовательно, К с : Х

и х0— внутренняя точка X .

Точка

x = ( J ( v ) ,

v) является

общей граничной точкой мно­

жеств X и У. В силу теоремы 5 существует разделяющий эти мно­

жества

функционал

с=^0: (с,

х) ^ (с, х ) = а ^

(с, у)

при всех'

х е Х , y^.Y.

Заметим,

что всякий

функционал с из сопряженного’

пространства

В х

представим в виде с = (vo, /о),

где vo —

действи­

тельное

число,

и результат

применения

с

к элементу х —

— (I, и)

можно записать в виде (с, х) =Vo£-|-t(A), «)• Поэтому усло­

вие разделимости множеств X и У перепишется в виде vog+i(^o,

^ v 0J (v) +

(lQ,

v) ^ v0ii+

(k, и) при всех (£, m) g JC и (if, u )^ Y , или

vo{^—

(/о,

и— и) ^ v 0[r|—J(v)]

при всех « e f/ ,

т)^/(ы )

и ^

^ •J(v)— L\\u—v\\. Эти

неравенства

совпадают с

(2.5.5),

и

даль­

Т е о р е м а

8. Пусть

U — выпуклое множество банахова про­

странства В,

имеющее

внутренние точки (возможно U— B), и

J {и) имеет

опорный функционал во

всех

внутренних точках мно­

жества V.

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

Как и в предыдущей теореме, введем

банахово пространство

В \= Е \ Х В элементов х — (£, и)

с нормой

IUIIb, = |i| +11«11в- В

этом

пространстве

рассмотрим

множество

X = { x = i ( i ,

и) : u^.U,

Очевидно, X — выпуклое множест­

во в В\. Покажем, что X имеет внутреннюю точку. По условию

/(«) ограничен в окрестности некоторой

внутренней точки v0, по­

этому существуют такие постоянные А и

5 > 0 , что J (и) ^.А для

всех u^.U,

||и— Оо11^б. Так как v0 внутренняя точка множества U>

то можем

считать, что шар ||и— ооН^'б целиком принадлежит U„

Покажем, что тогда точка

х0= ('|0, &о),

где |0=.4-|-6,

является

внутренней для X. Для этого достаточно показать, что шар

К =-{.r:||x — x0|B l< 6 }

принадлежит X. Пусть

(£, и) ^ К ,

т. е.

. II* — * 0lk =

l i — iol +

Ци— у01 К б-

§ П

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

243

Отсюда

||и— ио11<'6, £о— & < !< ;£ о + б . Поэтому

б=

Л > / (« )

для всех

« из

\\и— г>о11^б. Таким образом,

если

х = (£,

ы)е/<С, то

u ^ U , а

т. е. х е ^ ,

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

/(с=К п хо— внутрен­

няя точка X.

_

Возьмем произвольную

внутреннюю точку

о е У . Точка

х =

,=-(/(и), п) является граничной для X. В силу теоремы 5 суще-

ствует функционал с = (v0,

lo) ФО, разделяющий

множество

X и

точку х : (с, х) ^

(с, х) или (с, х— х) = v o (£ —/ (о )) +

(10, и— о) ^ 0

при

риантом этой теоремы.

_

Т е о р е м а 9. Пусть' U— {и : w e [Л,

g i(u )^ .0, i = 1, 2, ..., s},

где Ui — заданное выпуклое множество

из банахова пространства

В, функционалы gi(u), i =

1, 2, ..., s, определены и выпуклы на t/j.

Пусть

множество Ui удовлетворяет следующему условию регуляр­

ности:

для любого вектора

l ^ E s, 1Ф 0 существует элемент n e t/ ь

Я* = (Xi, . . . , Я5) 6 E s, Я > 0, такой, что пара

(ы*,

Я*) образует сед­

ловую

точку

функционала Ь(и,

Я) ==/(ы)-}-(Я,'

g(u))

в области

UiXAi,

Ai =

{Я : Я е £ 8, Я ^ О } в

следующем

смысле:

Ь (и *, Я) ^

^ L ( u * ,

Я *)^ 1L(u, Я*> при всех w et/ь Я еЛ ь

244

МЕТОДЫ М И Н И М И З А Ц И И В ФУНКЦ И ОНАЛЬНЫ Х ПРОСТРАНСТВАХ [ Г л . 5

пуклом множестве U гильбертова пространства, называется сильна

выпуклым,

если существует такая постоянная х > 0 , что

J

(аи +

(1 — а) и) -< a J (и) + (1 — а)J(v ) — иа (1 — а) |и ■— v |2

Т е о р е м а

10. Пусть U —

замкнутое

выпуклое

множество

гильбертова пространства

Я

(в

частности,

возможно

Я = Я ) , а

/ ( « ) — сильно

выпуклый

непрерывный функционал

на

И. Тогда:

1) J (и) ограничен снизу на

U:

inf J(u) = J * > — оо;

2)

существу-

U E .U

няя грань J (и) на U:

/ (« * )= / * ;

3) множество

M(v) — { u :u ^ U ,

J ( u ) ^ . J ( v ) } выпукло,

замкнуто

и ограничено

при любом u g U.

ловию ||«—Ри(и)\\ — р(и,

U),

где р (и, 0) = inf ||«— п||— расстояние

от точки и до множества

U.

V C .U

Очевидно, если ие1/, то

Рц\(и)— и. Теорема 2.3Л и ее дока­

§ П

Вспомогательные

сведения

245

1

4. Пусть J (и) =

| /(ы(0) dt, где /(«)— непрерывная функция на

о

но может быть раз­

Ei. а) Доказать, что J (и) непрерывен в С[0, 1],

рывным в Ь2[0, 1];

б)

Доказать,

что

если

|/(«+/г)—f(u) |^

^С(|гг| |/i| +

|A|2)

при всех и, h ^ E i (С = const ^ 0 ) ,

то

J (и) не­

прерывен в L2[О, II].

в) Если /(«) полунепрерывна снизу,

то будет

ли /(и) полунепрерывным

снизу

в

С[0,

1]? 1 2[0,

1]?

г) Доказать,,

что если f ( u ) ^ C l (Ei)

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

Е и то /(«), дифференцируемый функционал в L2[0,

1]. д) Дока­

зать, что если f(u)

выпукла [сильно выпукла] в Ей то J (и) выпук­

лый

[сильно

выпуклый]

в L2[0,

1].

Следует ли

из выпуклости

[сильной выпуклости] J (и)

выпуклость [сильная выпуклость] f(u)>

е) Доказать, что если /(«)

выпукла и удовлетворяет условию п. б),,

то J (и) достигает своей нижней грани на множестве U из упраж­

нения

3.

и2,

и11, ...)

5. В пространстве /2 последовательностей и— (и1,

\ип \<

— , п = \ ,

2,

...}

(«гильбертов

кирпич»

[88],

стр. 490). До­

казать,

га

замкнуто,

ограничено и компактно в /2;

что 1) U выпукло,

2)

U не имеет внутренних точек в /2;

3) не существует функциона­

ла,

разделяющего U и точку и = ( и \

..., ип, ...) ,

\ип |<С-^-, п = 1,2,...

6.

Доказать,

что

в точке

и = ( и \ ..., ип,

...),

для

которой

I ып I =

—- хотя бы при одном

1, можно провести опорный функ-

П

ционал ко множеству U из упражнения 5.

7.

Пусть Р — линейное нормированное пространство всех мно­

гочленов на отрезке [0,

1] с нормой

и (t) |=

max |и (t)

П

П

Положим

^ (w) — £ ] 1 а;1 для и (t) — ^

aLtJ 6 Р.

o<t<\

£=0

1=0

Показать, что J (и) — выпуклый функционал, однако не является

непрерывным на Р.

( У к а з а н и е. Рассмотреть последовательность

un (t)— tn— tn+x.)

Будет ли J (и) полунепрерывным снизу на Р?

8.

Доказать, что функционал /(гг) = ||гг||

дифференцируем в-

LP[0,

1] I(1 <Ср <С

оо)

всюду,

кроме и = 0, и найти / '(«).

Будет ли

J(u)

дифференцируем в Li[0,

1]? С[0,

1]?

9.

Доказать,

что

функционал

/(и) = ||ц|| в

Я-пространстве

дифференцируем во всех точках и ф 0. Найти J'(u).

10. Пусть А — оператор из примера 1. Доказать, что если А —

положительный

оператор

(т.

е. (Аи, и) ^ 0

при

всех и ^ Н ), то

функционал J (и) —

(Аи, и) — (Ь, и)

из примера 1 выпуклый, и

задачи минимизации J (и) на Н и решения уравнения А и = Ь экви­

валентны.

11. Пусть А — оператор из примера

1. Доказать, что если А —

сильно

положительный

оператор (т.

е.

(Аи, и)^у\\и\\2 при всех

л е Я ,

Y = c o n s t> 0 ), то

функционал

J

{и) — - i - (Аи, и) — (Ь, и) из

примера 1 сильно выпуклый и в Н достигает своей нижней грани

на единственном элементе ц*, являющемся единственным решением

уравнения Аи— Ь (это

обстоятельство лежит в основе метода Рит-

ца решения уравнений

А и = Ь ).

12.

Доказать, что

в рефлексивном ^-пространстве

||с||=

= т а х

(с, и) при всех

c e S * .

Ци|1<1

Пусть I ( и ) — выпуклый функционал на выпуклом

13.

откры­

ке У;

2) J ( и )

непрерывен в точке

у ; 3) J

( и )

ограничен

в окрест­

ности

точки

у ; 4) J (и) ограничен

сверху

в

окрестности

точки у

(см. [73]).

задан

конечный выпуклый функционал

/(«), то

в каждой точке

v ^ U

он имеет опорный функционал и,

следовательно, слабо полу­

непрерывен снизу. Доказать ([46], стр. 104— 107).

16.

Слабо полунепрерывный снизу функционал J{u ), удовлет­

воряющий условию ТТгтГ J (и) = -]-оо,

в рефлексивном S -прост-

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

([46], стр. 119). Доказать.

17.

Доказать, что /(а) = ||ы— «0И на любом выпуклом замкну­

том множестве U рефлексивного S -пространства

достигает своей

нижней грани (теорема существования

проекции «о на U или эле­

мента

наилучшего приближения к заданному элементу и0^ В ) .

18.

Пусть U — множество из S -пространства

с непустой внут­

ренностью, и пусть для некоторого функционала

c e S * известно,

что <(с, м ) = 0 при всех u^U . Доказать,

что тогда с = 0 .

S 2 называется линейное пространство S =

S i X S o упорядоченных

пар х — (х\, х2), у = ( у ь £/г) •••, где x ^ .y ^ B i

(j— 1, 2) с правилами

§ 2}

Некоторые методы

минимизации функционалов

247

ах 2). Доказать, что если

В\

и В 2 — банаховы

пространства, та

В = В \ Х В 2 также банахово с нормой ||x |= ||x iIIb , +1М1в3,

и сопря­

женное к В пространство В * представимо в виде В =

В\ х

В2.

20.

Теорема Мазура

гласит ([127], стр.

173):

если последо

тельность щ,

« 2 ...... «в,

в линейном нормированном

(в частности,

в

банаховом)

пространстве В слабо сходится к элементу и, то для

всякого е > 0

найдется такая выпуклая комбинация

п

п

п

£

щщ ^сс; >

0, ^

ссг = 1) элементов {«,}, что ||и— ^ а ;П;||<8.

<=i

г=1

t= 1

ции J (и) на

U,

понимая

под этим следующие вопросы: 1) найти

J* = inf J

(и);

2)

указать последовательность {un} ^ U , для которой

U&U

J*,

или же,

если это

возможно,

найти точку

u *^ U ,

lim J(u n) =

—>00

такую, что / (« *)= / * .

Описание

наиболее

известных

и часто

применяемых

методов

пространствах.

1.

Градиентный

метод

(случай Я = Я ) .

Предполагается,

что

/ (и )е С ‘ (Я ).

Строится последовательность {ип}

по правилу ([3,

27,

35,

46,

47,

57,

59,

75,

82,

102,

111,

135,

147,

148,

155,

161,

164,

171,

193,

229, 244,

255]):

«п+1 =

un—a nJ'(un), числа

ап> 0 ,

п = 0,

1, ...

(1)

Если ]'{ип) Ф 0,

то можно

подобрать

а „ > 0 ,

что / (« „ + ])< / (« „ ).

Это следует из (1.1). Если

при

каком-либо

п ^ О

J'(un) — 0, то

нужно провести дополнительное исследование поведения J (и) в ок­

рестности

ип для

выяснения

того, будет ли

и„

точкой минимума

J (и)

на Я .

В частности,

если J (и)

выпуклый функционал,

то необ­

П , л = 1 - 2 ,

где D = sup

|и — у |— диаметр множества М(и0).

u,v£M(ua)

Если / («),

кроме того, сильно выпуклый функционал на Я , то-

ранства Я ,

причем

0 < / ( и п)

J

[J (ио)

J ]уп> II ип

и ||2

< — [J Ы —

=

где <7 = 1 —

0 < < 7 <

1, а р ]> 0

константа

из теоремы 2.1 .4 -

Доказательство этой теоремы полностью

аналогично доказа­

тельству теоремы 2.2.1.

В

частности,

вывод (2.2.5— 6 ) остается та­

оценки (2 .2 .6 ) здесь нужно использовать выпуклость,

замкнутость,

и ограниченность множества M(uo) и сослаться на

теорему 1.4.

довательности {tin} следует из слабой компактности М (и0)

(см.

теорему 1.2). Пусть Unk~+v* слабо в Я .

Тогда равенство J ( v * ) = J *

вытекает из слабой полунепрерывности J (и)

(см.

теорему

1.3) и

соотношений

J* =

lim J (ип) =

lim J (ип ) > J

(о*)

J*.

Все

осталь-

П -> оо

k -* o o

полностью

со­

ные рассуждения из доказательства теоремы 2 .2 .1

храняют силу и здесь.

параметр а п

Сходимость градиентного

метода,

когда

из

(1)

выбирается согласно п. б), следует из теоремы 2

при Я = Я

(см.

ниже).

(случай 1]ф Н ).

2 . Метод проекции градиента

Предполагает­

ся,

что /(м )еС *(£/).

Строится последовательность

{ип} по прави­

лу

([9,

10,

31,

35,

75,

97,

124,

135,

155,

158,

159,

171,

179,

189,

193,

244, 255, 267])

*

ип+ 1 =

Ри (ип— a nJ' («„)), числа а п>

0,

п =

О,

1, . . . ,

(2>

тирования точки

ип— otnJ'(Un) на множество U.

а п в (2):

Перечислим

некоторые способы выбора параметра

а)

если

||/'(«)— J'{v) ||^L||u— v\\ при всех и, v<=U, L = con s

> 0 , то ссп может быть выбрано так.ж е, как в пункте 1

б);