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

58

М И Н И М И З А Ц И Я

Ф У Н К Ц И И

МНОГИ Х ПЕРЕМЕННЫ Х

[ Г л . 2

Очевидно,

сильно

выпуклая

функция /(«)

выпукла

и даже

строго выпукла. Примером сильно выпуклой

функции

является

J(u) = (и,

и ) = и 2,

(х — 1 ).

Т е о р е м а

4.

Для

того

чтобы Д ы )е С '(Д )

на

выпуклом

множестве U была сильно выпуклой

функцией,

необходимо и

достаточно, чтобы существовала такая константа ц > 0 ,

что

(J'(v) — /'(и ),

v — ы ) > р \v— и )2

при всех

и, v £ U .

(12)

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

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

Пусть

J {и) —

сильно выпуклая

функция

из

Cl (U).

В неравенстве

(11)

при

а = —

имеем

2

х

4

при всех

и, v 6

U.

(13)

К каждой квадратной скобке применим правое

неравенство

(9).

Получим

х \ и —

о|2< 2 ^ / ' (и), ^ ~ ) +

2 ^ ' (v ),

V —

и \

____

2

) ~

=

{J'{v) — J' (и),

V —

и)

при всех

и, v^ U . Остается

в

неравенстве

(12)

принять р,=х.

Д о с т а т о ч н о с т ь .

Пусть

/ (ц )е С ‘ (£/)

и

удовлетворяет

неравенству (12). Покажем,

что тогда J (и) — сильно выпукла,

при­

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

(11)

тогда

можно принять х = -^ -р . С помощью

формулы (5)

будем иметь

сU (и) 4 - (1

— a)J(v)~J (аи 4- (1 — а ) v)=

— a [ J

(и)— J

(о)] — [J iv4- а (и— v))— J (и)] =

1

1

= а J (У' (и4- t(u— v)), и — v)dt— а ^ (У' (о ~ (а(и—

v)), и—v)dt =

о

1

о

=

а ^ (У' (и 4- t {и —

и)) — J'

(v4- ta (и — и)),

о

(р + (ц — v)t) — (v +

ta{u — v))) - -

di-

>

<(1 — а)

> аЦ J

- * (l _ -” )2 -\u — v\2d t = у ц а (1

— a)|u — v |2

о

при всех

и, v^ U

и 0 < а < 1 .

А

§ /]

Постановка

задачи. Обозначения. Вспомогательные

сведения

59

Т е о р е м а

5.

Для того чтобы функция

7(м)<=С2(£/)

на

вы­

пуклом множестве U, имеющем внутренние точки, была

сильно

выпуклой, необходимо и достаточно, чтобы существовала

такая

константа р > 0 ,

что

{J"(u)l,

I) > р |£|2

при всех

u £ U

и

£ € Ет.

(14)

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

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

Пусть

J (и) —

сильно

выпукла

и

J ( u ) ^ C 2(U).

Пусть

сначала

« — внутренняя

точка

множества

U,

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

точка

из Ет. Тогда

£'=

и + г£ е£ /

при

всех достаточно малых е, |е|^ео. Из

форму­

лы (7) с учетом неравенства

(12)

имеем

е (J' (и -Ь eg) — J ’ {и),

|) = ег {J" (и +

0eg) g, g) >

е2ц 11 12,

0 <

0 <

1.

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

(7"(n)g, g) = lim (J" ( u + 0eg)

g, g)i^=p|g|2 при

всех

g e £ m. Если

и — граничная

е-*0

U, то существует

такая

после­

точка

довательность внутренних точек {«,г}е (У , что ип-*-и(п-*-оо).

Для

внутренних точек по доказанному выполняется (J"(un)l, g)

2

при

всех 1<^Ет. Пользуясь

непрерывностью

отсюда

при

а в Ет не выпукла

(например,

1(и\

и2) =

(и1)2— (и2) 2 при ц2 = 0 ) .

Д о с т а т о ч н о с т ь .

Пусть

/( « ) е С 2 (У )

и

удовлетворяет

условию

(14).

Отсюда

с

помощью

формулы

(7)

при h = v—и

имеем

(J'(v) — / '(« ),

v — и) = (J" (и + 0 (v — u))(v — u),

v — « )>

> р | и — v\2

при всех

и, v^ U . Тогда

согласно теореме 4 J (и) сильно выпукла,

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

(11)

можно принять

и =

— .

Заметим, что при

доказательстве

достаточности

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

внутренних

точек

U не использовалось.

З а м е ч а н и е .

Полезно

уяснить связь между

константами

к и р, из неравенств

(11),

(12)

и

(14).

Как

видно из

доказа­

60

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

\Гл. 2

тельства

теорем 4 и 5, при выполнении (12) и (14)

с некоторой

X = х

=

inf

^

(ц) +

( 1

J (») — J (au +

(1 — ct) v)

в

( 11),

u,v£U

o(l — a)|u — o|a

0 < a < l

И =

1*1 =

inf

(j"(u)l,

l)

в

(14);

ueu

ISi=i

и аналогично в (12). Из изложенного

ясно,

что

щ >

х для [любого

х из (11)

и хх;> -^ -

для

любого ц

из

(12),

(14),

в

частности,

х4 >

2

2

Ниже в

ряде случаев

от

градиента /'(и)

сильно

выпуклой

функции

будем

требовать

выполнения

условия

Липшица:

[/ '(« )— J'(v) |^L|u— п| при всех u, v^ U , L =

co n stX ). Как связа­

на константа L с х и ц? Применяя к левой части

(12)

неравенство

Коши — Буняковского

и

используя

условие

Липшица

для

J'{u),

сразу

получим

в частности

А тогда

А ^ ц ^ х ^ х

при любом х > 0

из

( 1 1 ).

и* — точка

Т е о р е м а

6 . Если

минимума

сильно

выпуклой

функции J (и)

на выпуклом множестве U,

то

j и — ц*|2 <

—

[J (и) — /(«*)]

при всех

u^U,

(15)

где х > 0

— константа

из

(11).

Если,

кроме того,

J

(и) в С1 ((/),

то

р|ы —

«*| 2 < ( J' ( u ),

и — и"),

ц I и

и* |< |J' (и) |,

0 < J ( u ) — J ( a * ) <

—

\J'(u)\*

(16)

К

при всех

u st/ ,

где

ц > 0 — константа

из (12)

или

(14)

^в

силу

замечания к теореме 5 в оценке

(15)

можно взять х ==

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

Если

в

неравенстве

(13)

примем

v = u*

и учтем, что

J (и*)

то сразу придем к

(15).

§ П

Постановка

задачи.

Обозначения.

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

61

Так как согласно теореме 3

в точке минимума

(/'(и *), и— и * ) ^ 0 ,

u ^ U , то из ( 1 2 )

при v — u* получим

pi I и — и* |2 < (/ '(« ),

и — и*) <

\J' (и) |•\и— и*\.

Первые два неравенства

(16) доказаны. Наконец, если

восполь­

зуемся правым неравенством

(9) при v = u*, то

J {и) — J

(и*) <

( J 1 (и) ,

и — и*)

<

|J'

(и) |■|и — и* |

и отсюда с учетом уже

доказанной

оценки

р|«— « * |sg: (/'(«) |

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

( 1 6 ) .^

Т е о р е м а

7.

Если

J ( и ) — сильно

выпуклая

непрерывная

функция на замкнутом выпуклом множестве U (в частности, воз­

можно,

U = E m),

то:

1)

/ (и)

ограничена

снизу на U, т. е. inf J (и) =

= / * > ’— оо; 2 )

существует и притом

единственная

а£С/

точка

«*е£/,

такая, что

3)

множество М (v) =

{ и : u^U , J ( u ) ^ J (v)}

ограничено при любом v^U .

U — ограниченное

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

Если

замкнутое

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

утверждения

теоремы следуют

из

классического

анализа

[126].

Пусть

U — неограниченное

множество.

Возьмем

произвольную точку

В силу непрерывности /(и) для любого

е > 0 ,

в частности

при

е = х > 0 ,

найдется

такое

6 > 0 ,

что

|/(и)— 7 (о )| ^ х

при

всех

н е!/ ,

|и— о | ^ б . Следовательно,

J ( u ) ^ J ( v ) —х при всех И(=Н,

|и— о | ^ б . Пусть теперь

|и— у | > 6 .

Тогда величина

а0 = ----- ------< 4 ,

и при а = ао из

(11)

получим

1« — о)

а0J (и) > J (v + а 0 (и — v)) — (1 — а0) J

(v) + х а 0 (1 — а 0) \и— v \2.

Так как

а0|и — & |=

б, то

J ( v +

a0 (u — о)) — Т (и )„> — х

в

силу оп­

ределения 6 , и

a0J (и) >

— х + а0J (и) +

ха0 (1 — а0) |и — v |2,

или

J (и) >

/ (v) +

X (1 — а0) I и — v I2 -----— =

J (v) —]

Оо

— %\и— ° | ( б + “^ ^ + х | « — а |2

при всех

и 6 U,

|и — v |>

6 . Далее воспользуемся неравенством

l“ - ' ’ l ( e + T

) <

T l“ ~ ” l*+ T

(

8 +

' j ) ‘>

вытекающим из очевидного неравенства 2 1аЪ |<

а2 + Ь2.

Будем иметь

J ( u ) > J ( v )

+

f \ u - v \ 2- f ( b

+

±

- y

(17)