Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 193

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

5 3.4.

ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

 

191

щий, что требование непрерывности,

присутствующее в формулировке

теоремы 1, существенно.

Пусть

 

 

 

 

 

 

 

 

 

/1 (*) =

\г 2х'х2,

если

х1> 0 ,

х2>

О,

 

оо.

 

если

я1< 0

или

 

х2<0;

 

 

О,

 

/2 (х) =

если

х1^

О, х2 ^

О,

 

если

ле1> 0

или

 

х2< О,

 

 

 

 

 

где х = (*’ , х2) е R2.

Обе функции

 

выпуклы, а их эффективные

множества пересекаются по полуоси х 1=

0, х2^

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

которой обе функции терпят разрыв. В частности,

 

(/ . +

 

о.

 

если

 

jc1 =

0,

 

х2>

 

О,

 

 

со,

если

х1ф 0

или

 

х2 < 0.

 

 

 

Имеем для у = (у1, f/2) <= R2

 

 

 

 

 

 

 

 

 

^(i/)={

I

если у'у2>1, у' <0, (/2<0.

в остальных точках;

 

 

 

 

 

если

у1

0,

 

у2^

 

О,

 

 

 

 

если

г/1< 0

илд

у2> 0;

itl + h)’ (</) =

{

°'

 

если

у2^ О,

 

 

 

 

 

если

у2>

0.

 

 

 

 

 

 

I

ОО

 

 

 

 

 

С другой стороны, функция

/*® /2

 

как

инфимальная конволюция

индикаторных функций равна индикаторной функции суммы эффек­

тивных

множеств функций

f{ и /2.

Сумма этих

множеств

состоит

из

всех

точек полуплоскости

у2

0,

за исключением точек

прямой

(/i

=

о,

т. е. она не совпадает с эффективным множеством

функции

+

Ы *. Аналогичные

примеры

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

в подтверждение

существенности условий

остальных теорем.

 

 

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

Д о к а з а т е л ь с т в о т е о р е м ы 1. Первое равен­ ство устанавливается прямой выкладкой:

(/i ® f2y (*’) = sup {<х‘ , дс) — inf (/, (дс — г) + f2(г))] =

хг

= sup {( А у) - fi (у) + (X*, г) - f2 (z)} = f] ( А + Г2(X*).

У» г

Далее, по неравенству Юнга — Фенхеля

П (*1) + Г г ( h ) > <х\ + 4 X ) -

<Х) - / 2(Х)

192

ГЛ. 3. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА

для любых а* е Х\ х\ <= Х\ х е

X. Поэтому

 

№ ) + а д > ( ^ + щ * ; + 4 ) -

Это

неравенство, в частности,

верно для всех х\ и х\

таких, что -т* -f а2= а*. Поэтому

 

Первая часть теоремы доказана.

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

dom(fi + f:)* = 0 .

Предположим теперь, что (/i + /2) *(**) = а0 < °° и функция /1 непрерывна в некоторой точке из domf2.

Тогда

dom(/! +

/2) Ф 0

и, значит,

(/1 + /2)* всюду боль­

ше —оо; в частности, — оо <

ао <

оо. Рассмотрим

мно­

жество

 

 

 

 

 

 

 

 

 

 

А =

{(а, х) s= R X

X |а<(х*,

х) — f2(x) — аэ).

 

Очевидно,

это

множество

выпукло. Покажем,

что

А П int(epi ft) =

0 .

(Множество

int(epi/i)

не

пусто в

силу

теоремы 1 из

§ 3.2.) Действительно,

если

(а, х ) е

е Л П

int (epi/ 1), то

 

 

 

 

 

 

 

т. е.

 

/, (а-) < а < (а*, х) — f2 (х) — аа,

 

 

 

 

 

 

 

 

 

 

 

 

аа < (а*, х) — f , (х) — /2 (л:) < (/, + f2y (а*) = а0.

По первой теореме отделимости (теорема 1 из §3.1) существует ненулевой линейный непрерывный функцио­ нал (р, y * ) e R X ^ * , разделяющий А и int (epi fi), г. е. такой, что

sup (pet + (у\ х) |(а, а) е= epi /,} <

< in f (Ра + (у\ х) |(а, х) е= А}. (1)

Ясно, что р ^ 0. Если р = 0, то из (1) следует, что у* разделяет множества dom/i и dom/2 (у* Ф 0, коль скоро р = 0). Последнее в силу первой теоремы отделимости невозможно, поскольку по условию (см. также теорему 1 из § 3.2) множества int(dom/i) и dom f2 пересекаются.

§ 3.4. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

193

Итак,

р < 0.

Разделив

обе

части неравенства

(1)

на |р |и положив х* — \р |-1 у*, получим

 

 

f \Ю = SUP { ( Х Ь

x

) ~ f i (х ) \ х

< ^

X ]

=

 

 

= sup ((х*,

х) — ct |(а, х) е

epi f,] ^

 

 

<

inf {(xj,

х) — а |(а,

л )е /1 ]

=

 

 

=

inf {(х^ — х*, х) +

/2 (х) |х е= dom f2) + а0 =

 

 

 

 

 

 

 

 

 

— ~f*2(x * ~

xi) +

ао-

Из этого

соотношения следует

неравенство

 

 

( П 0П )

(*‘) =

п

( х д + К

(** -

*1)< «о = (/. + f 2y

(*•).

 

доказывающее теорему.

Доказательства теоремы 2 мы не приводим; оно нам не понадобится.

Д о к а з а т е л ь с т в о т е о р е м ы 3. Как и в пред­ шествующем случае, первое соотношение тривиально следует из определений, второе вытекает из неравен­ ства Юнга — Фенхеля, и нам остается доказать нера­ венство

( Л Г ) ( * * Х ( /Л ) * ( Х * )

в предположении, что функция f непрерывна в некото­

рой точке, принадлежащей множеству ImA,

и что х* е

<= dom (/А)*.

а0 = (fA)* (х*). Поскольку

(dom f)fl

Положим

П (ImA) Ф 0 ,

функция /Л принимает конечные значе­

ния и, значит,

(fA)* всюду больше — оо; в

частности,

ао — конечное число. Рассмотрим в R X У линейное мно­ гообразие

М = {(а, у) <= R X У |3х<= X: а = (х‘ , х) — otj, у = Ах\.

Оно не пересекается с

внутренностью множества epi f,

так как иначе для некоторого г е ! было бы

f (Л*) < (*’ >х) — а3,

т. е.

 

ао < <**, х) -

f (Ах) < (/Л)* (х*) = а0.

7 А. Д. Иоффе, В. М. Тихомиров

194 ГЛ. 3. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА

По первой теореме отделимости множества М и epi /

можно разделить ненулевым линейным

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

(Р, J f l e R X r , т. е.

 

 

 

 

 

sup (Ра + (у\

у) |(а, у) <= epi /) <

 

у) |(а, у)<=М ).

 

<

inf (ра +

(у\

Как обычно,

убеждаемся,

что

р ^ О .

Если р =

0, то у*

не равен нулю и разделяет

множества

dom f

и 1шЛ

вопреки предположению о том, что int (domf) f) (Im А ) ф 0 . Итак, р < 0. Разделив обе части последнего неравенства

на |р |и положив г/* = |р |-1 г/*, получим

Г (ffo) < inf {<Уо> У) — а I (а>у) е

М ) =

 

 

 

= i n f [{у1, Ах) — {х\ jc) + o 0 |j c s Z ) .

Так как f* (у*) >

— оо

для

всех у*, отсюда следует, что

х* = А*у'0.

Иначе

 

 

inf (А ’у^ — х \ х ) =

 

inf «г/*,

Ах) — (х\

х)) =

— оо.

X

 

 

 

X

 

 

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

K e l m A ’ ,

х* = Л*г/д и

(Л*/*) (*’) ^

(z/q) ^

ао— (/Л)* {х*). Теорема доказана.

 

§3.5. Выпуклый анализ в конечномерных пространствах

3.5.1.Теорема Каратеодори. В конечномерных про­ странствах многие общие теоремы выпуклого анализа могут быть значительно усилены. В § 3.1 мы показали, что выпуклая оболочка множества совпадает с совокуп­ ностью всех выпуклых комбинаций точек этого мно­ жества (предложение 1 из § 3.1). Аналогичным образом были описаны выпуклые конусы, порождаемые множе­ ствами (предложение 3 из § 3.1). В конечномерных про­ странствах справедливы более сильные утверждения.

Т е о р е м а 1.

Пусть

А — непустое

подмножество

пространства R".

Тогда каждая отличная от нуля точка

х, принадлежащая выпуклому конусу К а ,

порожденному

множеством А, может быть представлена в виде

х — AjXj—

. . . —J—hrx r,

 

§ 3.5.

КОНЕЧНОМЕРНЫЙ ВЫПУКЛЫЙ АНАЛИЗ

195

где А,] > 0, .

А,г > 0, а

точки х ,^ А ,

ли­

нейно независимы. В частности, г ^

п.

Тогда

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

Пусть х е

Ка и х ф 0.

всилу предложений 1 и 3 из § 3.1

х— р,*! + . . . + ц а ,

где pi > 0, ... , pft > 0, а точки

хи ... , xh принадле­

жат множеству А. Предположим,

что векторы х и ... , Хи

линейно зависимы, т. е. существуют не равные одно­ временно нулю числа у], .... yh такие, что

Yi*i + ••• + Y A = 0.

Без ограничения общности можно считать, что среди чисел уь •••> Уи есть положительные (в противном слу­ чае мы заменим их на противоположные). Обозначим

через & множество тех индексов г,

1 ^

i

k,

при кото­

рых у< > 0,

и положим

 

 

 

 

 

 

Р =

min — .

 

 

 

 

 

 

i^sr Уi

 

 

 

 

Пусть, далее,

 

 

 

 

 

 

Р; =

Р, — РУ<-

 

 

 

 

Тогда все числа р ' неотрицательны

и

по

крайней

мере одно из них равно нулю. С другой стороны,

ft

k

ft

ft

 

 

 

2 u fo = 2 и л — P 2 У Л = 2 ИЛ= * .

i = 1

i = 1

i = I

1 = 1

 

 

 

Таким образом, мы представили х в виде суммы не бо­ лее k — 1 ненулевых слагаемых.

Повторив проделанную процедуру необходимое (но всегда конечное!) число раз, получим в конце концов

требуемый результат. Теорема доказана.

С л е д с т в и е

1 (теорема Каратеодори). Пусть

A cz R™.

Тогда каждая точка множества сопуЛ есть вы­

пуклая

комбинация не

более

п 1

различных точек

множества А.

Рассмотрим

в

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

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

R X

R n множество В = {1} X Л,

т. е. совокупность точек

вида

(1, х), где х ^ А . Очевидно, conv В =

{1} X (conv Л).

7*

Смотрите также файлы