книги из ГПНТБ / Балакришнан, А. Введение в теорию оптимизации в гильбертовом пространстве

Выпуклые множества в гильбертовых пространствах

8Ö

Т е о р е м а 2.9. (Фаркаш.) Пусть А обозначает (тУ^п)- матрицу с вещественными элементами, а у — векторстолбец из евклидова пространства Еп, для которого

[г/, лг]^0,		если	А х ^ О		(2.18)
(неравенство А х ^ О	означает,		что все компоненты век­
тора Ах неотрицательны). Тогда у имеет вид
	У = А ' г
для некоторого г е	Е,п,	0.
Д о к а з а т е л ь с т в о .		Прежде чем приступать			к до­
казательству, заметим, что если у — A*z, z е				Em, z ^ 0,
то условие (2.18) автоматически выполняется.				Для	каж­

дого m > 0 обозначим через Рт конус векторов из Ет с неотрицательными компонентами. Обозначим через С выпуклое множество

{ А * х : X е P J .

Потом мы докажем, что множество С замкнуто, а пока примем это на веру.

Предположим, что у не принадлежит С. Обозначим

через уо проекцию	вектора у на С. Тогда			в силу тео­
ремы 1.2 для каждого 2 ^ 0
[ у — Уо, Уо		А " г ] > 0,
или
[Уа — У, У ь \ < [ У ъ — У ’ А * г ] .
Другими словами,	для каждого z е		Рт
[Уо -	У> Уо] <	[А {Уо -	У), 4	(2.19)

Перебирая по очереди векторы 2 , у которых все ком­ поненты, кроме оДной, равны нулю, получаем, что все компоненты вектора А{у0 — у) неотрицательны:

А{у0 — У ) > 0-

Но тогда в силу (2.18)

[У,Уо — у]>0-

(2.20)

С другой стороны, полагая в неравенстве (2.19) 2 = 0, получаем [г/0 — у, г/0] ^ 0. Так как мы предположили,

90

Глава 2

что у не принадлежит С, то [г/0 — у, у0 — у]> 0, откуда

0 > {уа — У, г/0] > \Уа ~ У, У],

что противоречит неравенству (2.20). Итак, у е С. Докажем теперь замкнутость множества С. Положим

у = lim A'zn, zn <=Pm.

Если последовательность {zn} содержит ограниченную подпоследовательность, то доказательство легко закон­ чить. Поэтому предположим, что

І1 II —> ОО.

Пространство Еп допускает ортогональное разложение Еп= множество значений оператора Л* +

+ (нуль-пространство оператора А),

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

y — A'q-\-x, Ах = 0.

Но из равенства Ах = 0 следует, что

0 = [у, X]= [A’q, х] + [х, х] = [х, х],

откуда х = 0 и, значит, A'q — у. Воспользуемся ортого­ нальным разложением

Ет= (нуль-пространство оператора Л’) +

+(множество значений оператора А)

изапишем

у= А'Ах0

для некоторого х0 из Еп.

Обозначим через Q мнолеество значений оператора А. Покажем, что

А Axq s А Рт .

Предположим, что Q пересекается с внутренностью ко­ нуса Рт, т. е. существует такой вектор и > 0, что при некотором X

Ах = V.

Выпуклые	множества в гильбертовых пространствах	91
Тогда	[у, х] = lim [z„, Ах] = lim [z„, v],
оо >

что невозможно, поскольку ||z„||—>оо.

Итак, Q не пересекается с внутренностью конуса Рт. Но тогда по теореме 2.2 найдется ненулевой вектор ѵ, для которого

sup [v, q] < inf [v, р].

Отсюда сразу следует, что о е Р я и [u, Q] = 0, т. е.

v<=Pm[\QL.

Рассмотрим сначала крайний случай

Qf]Pm = {0},

(2.21)

где Ѳ— нулевой вектор. Предположим, что Qx не пере­ секается с внутренностью конуса Рт. Тогда, как и раньше, можно найти ненулевой вектор р е Рт, для которого [р, Q-1] = 0, т. е. p ^ Q [ \ P m, что противо­ речит (2.21). Поэтому найдется вектор p e Q 1, все ком­ поненты которого положительны. Тогда все компоненты вектора Ах0 + Мр при достаточно большом N также положительны. Поскольку Qx совпадает с нуль-про­ странством оператора А \ имеем

А'*{Ах0) = А* {Ах0+ Np),

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

нетрудно: для этого достаточно скомбинировать крайние случаи. Обозначим через р+ вектор из РтП Q с наи­

большим числом положительных компонент (пусть их k). Для удобства запишем (изменив, если необходимо, порядок компонент)

Pk		®ft <	P k е
Р+ = Ѳт -й				P fo
где 0m_Ä— нулевой	вектор в Em_k,			а	Ѳ4 — нулевой
вектор в Ek. Отсюда,	в частности,		следует,		что каждый
вектор из Q1 должен иметь вид
Г в,		am—k ^	Ет—ь.
. Пт—ft. 1

92 Глава 2

Тогда для любого ѵ из Pk

. ®m—k е (Q1)1 = Q-
V	( 2.22)
Далее,
]Лх0, Р+] = Um [zn, р ] = lim[z„, р+],
П
где
{%n)k
Ѳт—k .

(через (z„)fe обозначен вектор, образованный первыми k компонентами вектора zn).

Таким образом, последовательность {||z„||} ограни­ чена: беря ее сходящуюся подпоследовательность, получаем

[Ах0, р+] = [20, р+],

где zQимеет вид

z

20 = . ®m—k , z<=Pk.

Согласно (2.22),

{Ax0)k = z<=Pk,

где (Ax0)k — вектор, образованный первыми /г компо­ нентами вектора Ах0. Зададим преобразование Т, ото­ бражающее Q в Em- k, формулой

T(q) = (q)m-k, q ^ Q ,

где (q)m-k — вектор, образованный последними m — k компонентами вектора q. Тогда Т (Q) — линейное под­ пространство в Em-k и

т (Q ) П P m - k — ® m -k -

Поэтому;- как и в случае (2.21), в Em- k должен найтись такой положительный вектор pm_ft > Ѳ,„_А, что pOT_ft s

^(T(Q))'l . Тогда вектор

[Ѳ*

. P m—k .

Выпуклые множества в гильбертовых пространствах

93

принадлежит Q1 и, следовательно, для достаточно

больших N

А* {Ах0+ Nr) — А* {Ах0),

Теорема, наконец, доказана.

Дифференциальные игры

По сути дела дифференциальная игра — это игра,

исход которой определяется поведением некоторой упра­ вляемой динамической системы. Например, в игре двух

лиц могут участвовать „преследователь“		и	„пресле­
дуемый“, а также динамическая система,		описываемая
уравнением	. .
x(t) = F (t, X(t), и (t), ü (t)),	X(t)	En,

причем начальное условие x(0) считается заданным.

Преследователь должен выбрать управление u(t),				изме­
римое по Лебегу		и удовлетворяющее заданным		ограг
ничениям. Здесь		мы будем предполагать, что u (t) ^ K u
почти всюду,	Ки — замкнутое		ограниченное множество
в евклидовом	пространстве		Е,п. Все такие управления

мы будем в дальнейшем называть просто допустимыми. Аналогично преследуемый может выбирать управле­ ния v{t), которые тоже должны быть измеримыми по Лебегу и должны удовлетворять ограничёнию ѵ(t) е Кѵ почти всюду, Ка— замкнутое ограниченное множество в евклидовом пространстве Ер. Эти управления мы тоже

будем называть допустимыми.

Считается, что игру можно завершить за время Т,

если независимо от того, какое управление выбрал преследуемый, у преследователя всегда найдется соот­ ветствующее управление, для которого Иях (Г) |KJd, где я — оператор проектирования из Еп на Ek, а с?—фикси­

рованная неотрицательная	постоянная. Очевидно, что
в общем случае время Т	должно зависеть от началь­

ного состояния х(0). Как легко видеть, для того чтобы

можно было .завершить игру за время Т,	необходимо,
чтобы		(2.23)
sup inf Ипх{Т) II	.
О(-). «.{■)		.. т-

94 Глава 2

Действительно, поскольку игра может быть завершена в этом случае независимо от выбора допустимого упра­ вления о(-). ПРИ любом фиксированном ѵ( - ) должно выполняться неравенство

inf II яд: (Г) II ^ .d , «(■>

а отсюда следует условие (2.23). Заметим, что условие (2.23) к тому же будет и достаточным, если для лю­ бого ѵ( ■) найдется такое (допустимое) управление и( •), что

II яхи(Т) || = inf Кял (Г) II. «(■)

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

Линейные игры с выпуклыми ограничениями

Рассмотрим линейную задачу, т. е. задачу, в которой определяющая динамическая система линейна. Положим

X (t) — Ах (t) -f Ви (t) + Сѵ (t),

где для простоты матрицы А, В и С считаются по­ стоянными. Тогда, естественно,

г

ях(Т) = яФ (Т) х(0) -f я J* Ф (Т — s) Bu(s) ds +

о	г
	+ я J Ф (Т — s) Сѵ (s) ds,
	о

и мы будем пользоваться обозначением ял (Т) = Z {Т, и (•), V(•), л (0)).

Выше через Ф(/) мы обозначили матрицу фундамен­ тальных решений линейного уравнения, выписанного

	Выпуклые множества в	гильбертовых		пространствах	95
в начале раздела,
	Ф (0 = АФ (/),		Ф (0) =	/,
где I — единичная матрица.
Предположим также,		что множества Ки и К0 вы­
пуклы.	Обозначим через	множество
^ц —	| я ФJ (Т — s) Bu(s)ds: и (t) е Ка почти всюду | .
Аналогично положим
П» =	|л J Ф(Т — s)Cv (s) ds:		и ( t ) ^ K D почти всюду j .

Оба множества ограничены и выпуклы. Более того, они замкнуты. Действительно, пусть

г

г/„= я ] Ф(Т — s)ßun(s)ds,

о

а так как множество Ди ограничено, то можно выбрать последовательность {«„( •)}, слабо сходящуюся в L2{О, Г) к некоторому элементу, скажем и0. Ясно, что и0(і) также принадлежит Ки почти всюду и

т

у0= lim уп = п j Ф (Т — s) Ви0(s)ds.

о

Аналогично можно убедиться в замкнутости множе­ ства Обозначим через fu(•) и /0 (•) опорные функ­ ционалы множеств Q„ и Q0 соответственно. Теперь мы подготовлены к тому, чтобы сформулировать необхо­ димые и достаточные условия возможности завершения игры за время Т.

Т е о р е м а		2.10. Для	того чтобы можно было завер­
шить игру	к	моменту	Т,	начиная из состояния *(0)
в нулевой	момент времени,			необходимо и достаточно,

96

Глава 2

чтобы для любого единичного вектора e e £ j выполня­ лось неравенство

fv( e ) - f u ( - e ) < d - [ e , яФ (Т) х (0)].

(2.24)

Д о к а з а т е л ь с т в о . Прежде чем приступить к фор­ мальному доказательству, исследуем, что может дать условие завершимости. Пусть е—произвольный единич­ ный вектор из Ek. Рассмотрим

sup inf [е,	яд:(Г)] =
о(-) «(•)		г
= sup inf		е, яФ (Т) л:(О)-)- я f Ф {Т —■s) Ви (s) ds +
»(•)	«(•) L	о
		т
		+ я J Ф (Т — s) Cv (s) ds .

о

Эта функция платежа удовлетворяет условиям тео­ ремы 2.7 и следствия 2.3. Поэтому никакого сомнения в возможности перестановки операций inf и sup нет. Обозначим цену такой игры через q (е, Т). Заметим, что

inf [е, у] = - f u i - e ) ,

»s a «
и условие (2.24) можно переписать в виде
q{e, T ) ^ d .	(2.25)

Перейдем теперь непосредственно к доказательству.

Необходимость. Предположим, что игру можно завер­ шить за время Т, но при этом условие (2.24) не выпол­ няется. Это значит, что для некоторого единичного вектора е

q{e, Т)> d.

Выберем вектор ѵ0(-) так, чтобы

гг

	fv (в) = е,	я j	Ф (Т — s) Cv0(s) ds .
		о
(Это	всегда возможно		в силу компактности множе­
ства	Естественно,	что соответствующая функция и0(*)

Выпуклые множества в гильбертовых пространствах

97

не обязательно единственна.) Тогда

т

d < ' е, яФ (Г) X (0) -j- я J Ф (Т — s) Сѵ0 (s ) ds +

о

г

+ я J Ф (Т — s) Ви (s) ds

при любом допустимом управлении «(•), а это противоречит утверждению о том, что игру можно завер­ шить за время Т. Заметим, что пока мы не пользо­ вались теоремой отделимости.

Достаточность. Докажем теперь, что условие (2.24) достаточно для того, чтобы игру можно было завер­

шить за время	Т. Предположим, что это не так. Тогда
преследуемый	имеет	возможность выбрать допустимое
управление и0( - ) так,		чтобы множество
	т	т

яФ(Г) X (0) + л j<£>(T—s)Cv0(s) ds-{-n J Ф (T—s) Ви (s) ds

о о

ни при каком допустимом управлении и ( •) не пере­ секалось с областью перехвата S (d), представляющей собой шар радиуса d с центром в начале координат пространства Ek. Тогда с шаром S(d) не пересекается

и замкнутое выпуклое множество

т

,	лФ (?)*(()) + п J	Ф(Г — s)Cü0(s)ds-f Qu.
	о

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

inf е, яФ (Г) X (0) + я I Ф (T — s) Сѵ0 (s ) ds + «(•)

+ я I Ф (T — s)Bu (s) ds > sup [e,y] = d,

y<^S(d)

откуда q(e, T)>d, что противоречит условию (2.24).

4 Зак. 751

98	Глава	2
Положим теперь
d (Т) = sup q (е,	Т),	e<=Ek, ||е ||= 1 ,

и покажем, что d (Г)—непрерывная функция времени Т при Г ^ О . Для этого удобно ввести обозначение

Q(I (Т) = I я J Ф (T—s) Би (s)ds; и (s) Ки почти всюду|,

а опорный функционал этого множества обозначить через fu(-, Т). Аналогично введем обозначения QV(T)

и М - ,	Т).
Центральным для нас сейчас является непрерывность
функционала f u(e, Т)		по Т при любом фиксированном е.
Она следует из того,		что для любого г/е£2ц(Г + А)
г+д
y = n j	Ф ( Г + А — s) Bu(s) ds =
о		о
т

= п I Ф(Г — s)Bu(A + s)ds + я I Ф(Т—s)Bu(A-\-s)ds,

о - д

где первое слагаемое принадлежит QU(T), а второе по­ рядка А (мы будем обозначать это как О(А)). В самом деле,

QB(Z’+A)=QIICO+

+ I п J Ф(Т-\- s)Bu(s) ds\ и (s) <= Ки почти всюду j ,

и потому	fu(e, T + A ) - f u(e, Т) | =	О(А).
I
Аналогичное	утверждение справедливо	и для /„ (•, Т).
Пусть теперь
	d{T + A) = q(eA, Т + А),
Тогда	d(T) = q(e0, Г).
d ( T + A ) - d ( T ) ^ q ( e A>T + A ) - q ( e A, Т) =
=	[еА, я (Ф (Т + А) - Ф (Т)) s (0)] +
+ (Ыед. Т +	А)—/о{еА, T))-(fu( - e A, T + A ) - f a( - e A,T))