Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

90

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

[Гл. 2

Теперь

пусть

у — граничная точка X (рис.

15).

Тогда

сущест­

вует последовательность {ук}$=Х , ук -->у (k-^-oo). В силу

доказан­

ного существуют гиперплоскости

{ск, х)

— (ск, ук), J

|= 1, разделя­

ющие

множество

X и точки ук : (ск, х)

> (ск, ук)

при

всех х £ X.

Последовательность {сЛ} имеет хотя бы

одну

предельную точку с.

Это значит,

что некоторая подпоследовательность

скп -+-с (п ->-оо),

причем

|с| = 1. Так как (скп, х)

> { с кп,

ук/1) при х 6 X,

то при п ->-оо

отсюда получим (с, х) > (с, у) при всех

х £ Х . Следовательно,

гипер­

плоскость (с, х) — (с, у) = а разделяет X и у, более

того,

она

явля­

ется опорной к X в точке у 6 X

А

Т е о р е м а

5. Пусть А п В — два заданных выпуклых множест­

ва в Е п, не имеющие

общих точек.

Тогда

существует

гипер­

плоскость (с, х ) —а, разделяющая эти множества.

При этом

если

А \\В имеют общую граничную точку у, то а =

(с, у).

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

Возьмем

множество

Х = А — В.

По

определению х ^ Х тогда и только тогда, когда существуют

такие

а е Л

и Ь ^ В ,

что х = а— Ь. Нетрудно

видеть,

что

X — выпуклое

множество. В самом деле, пусть х* = я*— bi^X ,

а ^ А , b ^ B ( i = l , 2 ) .

Так как Л и В выпуклы, то

а -

аах + (1 — а) а 26 A,

b = a b x - f (1 — а) 62 6 В

при

всех а, Ог^аг^П.

А

тогда

х = а Х ] + ( 1 — а )х 2 = а— Ь ^ Х

при

всех

а,

O ^ a ^ l . Покажем, что х = 0

не является

внутренней точ­

кой X.

Для этого прежде всего заметим, что О еА

тогда и только

тогда,

когда А и В имеют общую точку ао. Если

бы 0 еА °,

то

существовал бы шар

|х|^б, целиком принадлежащий X, что воз­

можно, если только шар

|а — ао|=^б принадлежит

множествам А

и В.

Однако А и В не имеют общих внутренних

точек. Следова­

тельно,

0 не может быть внутренней точкой X.

S 5]

Метод

проекции

опорных

функций

91

Тогда

в силу теоремы 4

существует гиперплоскость (с,

х )= 0 ,

с ф О, разделяющая множество X и точку г/= 0.

Это значит,

что

(с, х ) ^ 0

при всех х ^ Х ,

или

(с,

а —Ь ) ^ 0,

или

(с, а ) ^ ( с ,

Ъ)

при

всех а ^ А ,

Ь ^ В . Гиперплоскость

(с, х ) = а ,

где

а — произвольное

число, удовлетворяющее

неравенству

inf

(с, а) > а > sup

(с, Ь),

разделяет

множества А и В.

Если у — общая граничная точка А

и В, то inf (с, а) = sup (с,

Ь) =

(с, у) = а.

А

-

Т е о р е м а

6. Пусть U — выпуклое

множество из Е т, имею­

щее внутренние точки (в частности, возможно

Uz=Em). Для

того

чтобы функция J(u ), определенная на U, имела

опорную

функ­

цию во всех внутренних точках

U, необходимо и достаточно,

чтобы

J (и) была выпуклой на U.

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

Необходимость

следует

из

теоремы

3.

Докажем

достаточность. Пусть J (и) выпукла на U, и пусть

v —

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

U. В т + 1-мерном про­

странстве

Em+i= E iX E m

переменных

a =( g ,

и1, ..., ит)' =

(£,

и)

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

А = {а — (g, и ) : и € U, g >

/ (и)}.

Покажем,

что А выпукло. В самом деле,

пусть

czi =

(gb

а 2 —(£2, М г)еЛ. Из выпуклости U имеем ащ + (1— a )u 2^ U

при всех

O ^ a ^ l . Из выпуклости J (и) следует:

J

(сшх + (1 — a) ы2) <

a J (их) - f

(1 — a)

J (ы2) <

< a g x +

(1 — a) g2,

0 < а < 1 .

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

a a i + ( l — а ) а 2^ А при

всех

a,

О ^ аг-П .

Выпук­

лость А доказана. Точка a — (J(v),

и),

очевидно,

граничная для А.

Тогда в силу теоремы 4

существует

гиперплоскость

(с,

а) = а =

= (с, а), с =

(vo,

1о)ф0,

опорная

к множеству А в точке а.

Это

значит, что

(с, а — а) =

v0 [g — J (о)] + (/„, u — v ) > 0

при всех

а =

(g, и) 6 А,

ttef/, g !^ / (и).

при u = v

(4)

т. е. при

всех

В

частности,

имеем

v„[g—

при всех g^=/(n), что возможно только при Vo^O.

Покажем,

что v0> 0 . Если бы vo = 0,

то из (4)

имели бы (/0, и— v ) ^ 0

при всех

u^U . Но v — внутренняя точка

множества U, и послед­

92

М И Н И М И З А Ц И Я

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

[Гл. 2

и всех

В частности, при £ = / (гг)

отсюда вытекает

J (и) — J (v) >

^----— , и — v'j при всех и 6 U.

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

вектор I =

------—

является

опорным

к

J (и) в точ-

ке V. ±

На примере функции

J (и) =

— У 1 — и1

мы уже

убедились,

что для существования опорной функции в граничных

точках мно­

жества

U выпуклости J (и) на U недостаточно.

Здесь

справедлива

Т е о р е м а

7. Пусть U — выпуклое множество из Ет, имеющее

ходимо и достаточно, чтобы J (и)

была

выпуклой

на U и для

всякой граничной точки а е У

существовала

постоянная L = L ( v ) ^ О,

такая, что J (и)

(и )— L(v) |и— v | при всех « е (/ .

J (и) во

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

Н е о б х о д и м о с т ь .

Пусть

всех

точка v ^ U

имеет

опорный

вектор l{v). Тогда /(гг) —J ( v ) ^

^ ( l ( v ) ,

и— v) ^

— |/(и)||гг— и| при

всех

u ^ U

(в

частности, в

граничных точках U) и остается

принять

L(v) =

\l(v)|.

Выпук­

лость /(гг) следует из теоремы 3.

выпукла на U и для каж ­

Докажем достаточность. Пусть /(гг)

дой

граничной

точки v

множества

U

существует

постоянная

L = L {v),

такая,

что / (гг)^ / (и )— Т|гг— v\

при всех ггеС/. Сущест­

вование опорных функций во внутренних точках

U следует из тео­

ремы

6.

Пусть

v — граничная

точка

U.

В

пространстве Em+i

переменных а= (\ , гг1, ..., гг”) =

гг)

рассмотрим два

множества:

А =

{а = (е, гг): гг 6 U,

£ <

J

(v) — L |гг — v |}

и

B = { b = a , u ) :u e U , l > J { u ) ) .

Покажем,

что А выпукло. Пусть

#1 — (Eii

^i)>

=

(Ег>

€ •'4>

пусть

0 < а < 1 .

В силу выпуклости U тогда

агг1+ ( 1 — а) гг26 U, a

из

<

/ (v) — L |uc— v \ (i =

1, 2)

имеем

° l i + (1 — a ) %2 < J ( v ) — L (а. /«1 — v\ + (1 — а) |гг2 — v |) <

< / (o ) — £|агг1 + (1 — а)гг2— г»|И

Следовательно, а а 1 + (1 — а) гг2 6 А

при

всех

а,

О •< а •< 1.

Анало­

гично доказывается выпуклость В.

Далее, множества

А и В не имеют общих внутренних точек,

ибо

если

(!, и )^ А , то

координата

| ^ / ( о )— А|гг— и|^/(гг) при

94

М И Н И М И З А Ц И Я

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

[Гл. 2

Как известно

из классического анализа, для непрерывности

J (и)

в точке u ^ U

необходимо и достаточно, чтобы

lim J

(uk) — lim / (uk) = J (и)

ft^

ft-»00

для любой последовательности {«/ Jet/ , Щс+и(k-^oo) .

Т е о р е м а

8.

Пусть J (и) выпуклая функция на

выпуклом

множестве U.

Если в точке у е (7 функция J (и) имеет

опорную

того, J (и) ограничена

сверху в некоторой окрестности точки о, то

она непрерывна в точке v.

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

Пусть {«/J

— произвольная

последо­

вательность, такая,

что

« set/

(/е = 0,

1, ... ) и uh-+v (/е-э-оо)*-.

Так

как J(u k)J^sJ{v) +•(/,

«ft— о), то.

Иш J

(uk) > J ( v ) .

Далее,

по

ус-

k - * o o

ловию

существует

постоянная б > 0 , что

J(u)^ZC

для всех

« et/ ,

Jи— v |<;5. Поэтому с учетом в'ыпуклости /(«)

имеем

J ( “ k) = « М 0 — a )v + a ^ v — -^-(о — « * )^ <

<

(1 — a) J

(о)--- аJ

----- — (v — «й)^

(1 — a ) J (и) -f а С

для всех а,

0 < а < 1 ,

и всех номеров /г,

лишь

бы

— \v — мл| < б .

(X

Отсюда

1 im J (uk) <

(1 — а) J

(v) -j- аС при

всех

а,

0 < а <

1.

Сле-

довательно,

здесь

можно

положить

а -ь -| -0 ,

тогда

получим

lim J («*) <

J(v).

Из

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

функции

сверху

и

снизу

k —*x >

вытекает ее непрерывность. ^

Упражнения.

1.

Если «о — внутренняя точка

выпуклого мно­

жества

U и v — произвольная

точка

из

замыкания U, то

точки

«а = о + а(ы0— v)

при всех

а,

0 < а < ;1 ,

будут внутренними точками

U. Доказать.

У к а з а н и е .

Если шар

|и— ы0| ^ б

принадлежит U,

то

шар

|«— «а|<^.аб также е1/.

2.

Доказать,

что если А и В — два выпуклых замкнутых м

жества, не имеющие

общих точек, и хотя бы одно из них' ограни­

чено, то существует

гиперплоскость

(/, х) = « ,

строго

разделяю­

щая их, т. е.

(/, й)^< а < а + & ^ (/, а)

при всех а е Л ,

и неко­

тором е > 0 .

Верно ли это утверждение, если

оба множества не-

ограничены?