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

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 .

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

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

ограничены?

S 5]

Метод проекции

опорных функций

95

3. Пусть

точки

щ(1 = 0,

1, . . . , гп)

таковы,

что

векторы

щ— u0(i = 1, . 2, . . . , m)

линейно

независимы.

Образуем множество

m

m

S =

ЩЩ ПРИ всевозможных

щ > 0 ,

^ щ =

l j,

i= 0

i=0

т

т

ы0

— V aiUi при

>

0, V ос; = 1.

£=0

.

i= 0

Доказать, что если

точки и0, . . . ,

ит принадлежат некоторому вы­

пуклому множеству U, то симплекс 5с=Д.

Uc^Em тогда и только тогда, если равенство

(I, и— ы0) = 0 при всех

u ^ U может выполняться только при /=0,

т. е. выпуклое множе­

У к а з а н и е.

Доказать

существование точек

ии . . . ,

um^ U ,

Для которых

векторы и\— и0, . . . ,

ит— и0 линейно

независимы, и

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

5.

Выпуклое множество

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

да

и

только

тогда,

если

существует

вектор /=Ф0

такой, что

(/,

и— «0) = 0

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

т. е. множество U лежит в некоторой

гиперплоскости (точку и0 можем

считать принадлежащей

U).

U,

6. Пусть /(и) — выпуклая функция на выпуклом множестве

пусть (i+ e/ eU

при всех

е, 0 ^ е < Е 0. Доказать,

что J (и) имеет

производную по направлению 1\

d J

(и) __

J

{u +

&l) — J

(и)

dl

e-H-0

8

где

|/|= 1.

Доказать

[199],

что

d J (и)

sup

( с ,

I ) ,

dl

с £М( и)

где М (и )— множество всех опорных к

J

(и)

векторов в точке и.

7.

Найти все опорные векторы для функций: a) J (и) — \и— 1 1+

+ |и+1|,

и ^ Е г\ б)

/ (и1, и2) =

|и1— ы2|;— |и1 +

иа|;

в)

J{u) =

— шах {и2; и - f

2},

и £ Е г.

J(u }i ui) =

|и1 -f- иЧ I.

8.

Найти

все

опорные

векторы для

sup

96

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

[Гл. 2

9.

Описать метод проекции опорных функций для. задачи

нимизации функции

J

(а1, и2) = шах 112 -i- иЧ + u21 при 0 <

u‘ < 1 (i =

1, 2).

K|«l

10.

Как нужно доопределить функцию

J (и) =

1

в точке

1 +

е х>и

11. Пусть J

(и) определена, конечна и полунепрерывна

снизу

в каждой

точке

замкнутого ограниченного

множества U a E m.

Доказать,

что тогда /(гг) ограничена снизу на

U и достигает

на U

Возьмем

главную

линейную

часть этого приращения /„ (гг) =

s= (/ '(гг„),

и — гг„)

и определим

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

ип из

условия

/„(гг„) = тт / „(гг)

= ппп(/'(гг„), гг — гг„).

(1)

(ISC/

u £ U

min /„ (гг) — /„ (гг„)

/„ (гг„)

0.

и

Если

окажется,

что

/п(ггп) = 0 ,

то

с

учетом

(1)

имеем

(/'(ггп),

гг— ггп) ^ 0

при всех гге£/. Согласно

теореме 1.3 это озна­

чает, что ип удовлетворяет необходимому

условию

минимума.

В этом

случае итерации

прекращаются,

и

для выяснения

того,

будет ли ип точкой минимума /(гг) на U,

нужно дополнительно

исследовать поведение функции в окрестности этой точки. В

част­

98

М И Н И М И З А Ц И И Ф У Н К Ц И И МНОГИ Х

ПЕРЕМЕННЫХ

[ Г л . 2

жества U. По условию множество U ограничено, поэтому

оо.

Так как J

(un+i) = gn (ап) < g n (a) = - J (u„ +

а («„ — и,,)) при

всех а ,

0 < а < 1 ,

то, пользуясь неравенством (1*18)-

при v = un,

и = и п +

■+ а («л — ип),

получим

J («я) — J

(«*+0 >

— “ (/' («„), иа — «„) — у

L |ип— и„ |2 >

>я|Л>(«„) I---| - L D 2, 0 < а < 1 ,

п =

0, 1, ...

(5)

Отсюда

О < |/„(й„) I <

42- LD2 +

а

при всех

а, 0 < а ^ 1

и д = 0 ,

1,....

Так как /(«,,) не возрастает и

/(гг„) $ s / * > — оо, то

{/(ип)}

сходится и /(гг„)— /(un+i)-^0 при

«•-*-оо. Поэтому, переходя в предыдущем

неравенстве

к

пределу

при л-»-оо,

будем иметь

О < П т |J n(й„) |<

П т |/„ (йя) |<

-5- LD2

П-»оо

2

при всех а ,

0 < а < 1 .

Отсюда

при

ос->~-|-0

получим,

что предел

Нш J n (и„)

существует и равен

нулю.

П-+оа

Пусть теперь /(и)

выпукла на U и и*

— точка минимума J (и)

на U. Тогда с помощью неравенства

(1.9)

и условия (1)

получаем

О < ап =

J

(и„) — J

(и) <

(/' (и„), и„ — гг*) =

= — У„(гг*)< — 7„(гг„), /г =

0,

1, . . .

(6)

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

(1)— (3).

Так как

/ п (ип)-^-0

при п-*-оо, то

из

(6) имеем J (ип)—*-

/ (гг*)= / *,

т. е. {ип}

— минимизирующая

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

ность {ггп}->-гг*.

_

Докажем оценку (4). Так как /„(ггя)->-0

при_/г-»-оо, то

най­

дется

число гг0 > 1 ,. такое, что величина а

— *

^

■ будет

удов­

летворять неравенству 0 < а < Н

при всех

/ г> п 0.

Тогда максималь­

ное

значение функции а \J п (ип) ) ------у -

LD-

переменной а

при