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

62

М И Н И М И З А Ц И Я

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

[ Г л . 2

при всех

и 6

U,

|и — и|

б. На самом

деле

это

неравенство

верно

при

всех

и £ U,

ибо

для

точек u £U,

|и — и| < 6 также

имеем

7 (« )> / (у)— x > J ( v ) - {-

+ у

х62— у

х ( б + у J

> J (о) +

у

х >

и12 —

х(6+ Т ) 2-

Из оценки (17) тогда

следует,

что

при всех

u £ U ,

т.

е.

J (и)

ограничена

снизу

на U.

Далее

из

(17)

имеем

J

(и)

+

оо

при

|ц|-»оо,

и £U . Тогда

для

любого числа

Л > 0 ,

в

частности

при

А = 17 (у) |,

найдется

такое

О,

что

J (и) >

|J (и) | при всех u £ U , |и— v\i>B. Отсюда ясно,

что

J * = i n f J ( « ) =

inf

7 («) < 7 (ц ).

«6£/

|и—ч|<В

Так

как

пересечение

множества

U и шара |и—

есть

замкнутое ограниченное (и даже выпуклое)

множество, то непре­

рывная функция J (и) на этом пересечении достигает своей ниж­

ней грани

в

некоторой

точке

и*,

причем

/(и*) = 7 * .

Единствен­

ность такой точки ы* следует из строгой

выпуклости

J (и) и тео­

ремы 1 .

Ограниченность множества M(v) =

{и : u^U , J (и)

(о )}

при

любом v ^ U вытекает из неравенства (17):

|и —

о

при

всех и еМ (v). ±

По

поводу

других свойств

выпуклых

функций и выпуклых

множеств см. также § 3, 4. Здесь мы докажем еще

две

леммы,

полезные в дальнейшем.

Л е м м а

1. Пусть

U — выпуклое

множество

в

Ет, J (и

е С ‘ (£У)

и J'(u)

удовлетворяет условию Липшица: |J'(u )—J'(v)

^ Ь\и— v\ при всех и, ае£/, L = const>0. Тогда

7 (v) — J (и) >

(J' (v),

v — и )----- — \v— и |2

при всех и,

v £ U .

2

( 18)

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

Положим

в

формуле

(5)

h =

v — и.

По­

лучим

1

7 (v) — 7 (и) =- J

(/' (и -f a (v — и)),

v — u.)da — (J'(v),

v — и) +

S П

Постановка

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

сведения

63

+ | (J' {и +

а (у — и)) — J'

(v),

v -— и) da.

Поскольку

о

(J1 (и + а (v — и)) — J' (о),

v — и) >

— |J' (и + а (v — и)) —

— J'(v)\-\v — и \ > — L { 1 — a ) \ v -

«|2,

0 < а < 1 ,

то

1

J

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

v — и) — L |а — и |2 J (1 — a)da =

о

=

(J’ (v),

v — u )----- {- L \ v — u|2. A

Л е м м а 2.

Пусть

имеется

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

{ап},

п = О,

1 ,

2 ..........

такая,

что

ап > О,

ап— <зп+1 >

Ла£

при

всех

п > -п 0 > О

(А = const> 0). Тогда

| |

а п< ^ ~ °—— при всех п^>па.

Ап

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

С учетом условия

леммы

имеем

1_________ } _

_

~ ak + l

^

д

а/г

a k + l

a k

akak + l

a k + l

при всех k > п 0. Просуммируем это неравенство

по k от п0 до п — 1

и получим

—----------— >Л(/г — /г0), откуда

—

> Л ( / г — п0),

или

ап

ап0

ап

а п< ---------------- при всех п >

/г0.

Однако ----- ------ <

п°~*~

при

А (п — п0)

п — па

п

/г> па,

следовательно, а Л<

п°

1 , п > пй.

А

Ап

Упражнения.

1. Доказать, что пересечение

любого

числа

вы­

выпукло.

2,..., р)

2. Пусть функции /{(«)(/= 1,

выпуклы

на множест-

ве 1 U. Доказать,

р

atJi (и) выпукла на U

что функция J

(и) = £

при любых aj'1^ 0 .

£—1.

3. Привести

пример двух выпуклых

функций,

произведение

64

М И Н И М И З А Ц И Я

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

[ Г л . 2

лых функций выпукло? Достаточно ли для

этого положительности

сомножителей?

4.

Пусть функции J a

(и) выпуклы

на

U при всех

а е Л , где

А — некоторое заданное

множество

•индексов. Доказать, что

функция / (и) — sup Ja («)

ВЫПуКЛЭ НЭ U.

аеА

5. Функция /(и) выпукла на U тогда и только тогда, если

функция g (t) = J {u-\-t (v— и))

одной

переменной t, O s ^ f^ l, яв­

ляется выпуклой при любых и,

y et/ .

Если

J (и) сильно выпукла,

то g(t)

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

Доказать.

6.

Если J (и) выпукла на U,

то

II

П

J (Е а‘и<) <ЕaiJ №

при любых

£=1

£=1

П

а: > 0 ,

£ а

г = 1 ,

u.€t/,

7.

Доказать, что J (и)

выпукла на

U тогда

и только

тогда,

когда

множество

А = { а — (и1....... ит, 1) — (и, £)

: и е У ,

£ ^ / (и )}

выпукло в пространстве Ет +ь

U необходимо и

8.

Для выпуклости

функции / ( « ) e C ‘ (t/)

на

достаточно,

чтобы

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

и— v)

при

всех

и,

y et/ .

Доказать (см. теорему 2).

на U достаточно,

9.

Для

выпуклости

/ (a )e C 2{t/)

чтобы

(/"(ц)|, 1)^=0 при всех

wet/ и всех £ е £ т . Доказать (ср. теоре­

му 5).

1, 2,.... п)

10.

Доказать,

что если

функции /, («) (i =

выпуклы

на U, то множество t/ ]= {« :« e t/ ,

«=1,

2, ..,

п}

выпук­

ло (fli — заданные числа).

на U, то множество М(и) =

{и : u^U ,

11.

Если

I(и)

выпукла

J ( u ) ^ . J ( v ) }

выпукло при любом y et/ . Доказать. Верно ли обрат­

ное утверждение?

вается

квазивыпуклой, если / ( < х у + ( 1 —

а) и) ^ m a x { / ( и ) ; / ( у ) }

при всех и, y et/ и а, 0 ^ а ^ 1 . Всякая

ли

выпуклая

функция

квазивыпукла и наоборот? Доказать, что J (и)

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

тогда

и только тогда, когда множество

М ( у )

= {« : wet/,

J (и

S 2]

Градиентный метод

65

при всех и, v&.U,

OegCa^l. Доказать,

что если J (и) равномерно

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

ния теоремы 7 сохраняют силу.

14. Доказать,

что J (и) —au2 + bu + c,

и ^ Е х — сильно

выпукла

при любом а > 0 .

15.

Пусть

J

(и) — — (Аи,

и) — (6, и), где Л — заданная сим-

метрическая матрица

порядка

mXm, b — заданный вектор из Ет.

Доказать, что: а)

если

(Л|,

при всех g e £ m, то 7(и )

выпукла

на £„,;

б) если А — положительно определена, то J (и) сильно вы­

пукла

на £,„,

причем в качестве константы % из неравенства (11)

можно

взять

х =

где

Xi — наименьшее собственное число

пХт ,

Ь — заданный вектор из Е п. Доказать, что J(u)

выпукла

на Е т.

Если Л *Л — невырождена, то /(«)

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

(здесь

Л* — транспонированная матрица).

Найти / '(«),

J"(u).

§ 2. ГРАДИЕНТНЫЙ МЕТОД

Пусть дана функция /(«) е С 1 (£ т ). Как известно [126], в точ­

ке и,

в

которой 1 '{и ) Ф 0, направление наибыстрейшего

возраста­

точке,

а направление наибыстрейшего убывания — с

направле­

нием

антиградиента — /'(и). Это следует из формулы

(1.2)

и не­

равенства

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

— |/'(м) |\h\^

(/'(и),

h) ^

^ ]£ (« ) ||/г 1, если учесть, что правое

неравенство

превращается

под названием градиентного метода [3, 19,

27, 35, 46, 75, 79, 82,

109,'135,

149,

155,

161,

164,

170,

177,

188,

193,

229,

230,

235,

239,

251— 253, 260]

и др.

Этот метод предполагает выбор некоторой начальной точки «о-

Общих правил выбора и0 нет; в тех случаях,

когда имеется априор­

ная информация об области

расположения

искомой точки

мини­

url+x ^ u n — a nJ'{un),

ап — const > 0

{п =

0, 1 , 2 , . . . ) .

Если Е { и п) Ф 0 , то можно подобрать такое a n> 0 ,

( 1)

чтобы /(wn+1) <

< / (« „ ). В самом деле,

из формулы (1.2)

следует

J [ип+х) — J (ип)

0{0-п)

< 0

ьб

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

[ Г а . 2

= min £,*(«),

g n( a ) = J ( u n — aJ' (ип)).

(2>

а^О

Отсюда сразу имеем J {ио)

{u\)

(и2) ^ ...

Возникают вопросы. Возможен ли выбор а п из условия

(2) ?

Будет ли lim J («„) — J* — inf J (ы)?

Для получения положитель-

«££ш

накладывать дополнительные,

довольно

жесткие ограничения.

Т е о р е м а

1. Пусть функция

J

(и) 6 С1 (Em),

inf

J (и) =

J* > — оо,

rwoo

выпукла и множество М(и0) = {и :

Если, кроме того, J (и)

J ( u ) ^ J { u 0)} ограничено, то

последовательность {«„} является

нимума J (и) на Ет,

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

мума к ней сходится

вся

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

{«„}. Справедлива

оценка

0 < 7 (u „ ) — J* < 2 D * L - — ( п = 1, 2 , . . . ) ,

(3)

,

П

где D = sup |и — v |— диаметр множества М (и0).

ы.абАЦыо)

сильно выпукла на Ет, то

Если J(u), кроме того,

О

J («„) — J -С !У (“о)

J I Яп>

K ~ u * | 2 < —

[J(ua) — r ] ( T

( Л - 0 ,

1 , . . . ) ,

(4)

V-

где q — l -----

— , 0 < q < 1, p = co n st> 0 из теоремы 1.4.