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

72

М И Н И М И З А Ц И Я

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

[Гл. 2

с меньшей

«кривизной»,

наоборот, cos а„ — cos а)г_ !> 0 ,

поэтому

линейные участки на «дне оврага». Если

«кривизна дна оврага»

на некоторых участках остает­

ся постоянной,

то

разность

cosan— cosa„_i

будет

близка

к

нулю,

и поиск

минимума

на

таких

участках

будет прово­

диться

с

почти

постоянным

шагом,

сформированным

с

учетом

величины

«кривизны»

при

выходе

на

рассматривае­

мый участок.

с

(7)

Параметр

в

равенстве

регулирует

чувствитель­

ны в работе [211].

Выражение (7) для

овражного шага удобнее

преобразовать

так:

hn+i = hncC05a’~C0san-i =

йЛ_ 1ссмв« -ео**я-з =

. . .

=

/г2сС05а*“ С05е\

откуда окончательно

hn+l = Kccosa", К =

h„c~cosa' = const> 0 ,

п =

2 , 3 , . . .

Другой способ ускорения сходимости градиентного метода за ­

ключается в выборе подходящей замены

переменных

u = g (Q

с тем, чтобы поверхности

уровня функции J(g(£,))

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

переменных £ были близки к сферам [251—253].

Упражнение. Опишите метод скорейшего спуска для

функций

J(u) из упражнений 1.15

и 1.16. Укажите явное выражение для an

из условия (2). Пользуясь теоремой 1, оцените скорость

сходи­

мости.

£ 3]

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

градиента

■73

ности (2.1) проектировать на множество U. В результате мы при­

дем к так называемому методу проекции градиента.

1.

Для точного описания этого метода нам понадобятся вс

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

О п р е д е л е н и е 1.

Проекцией

точки « е £ т на множество

UczEm называется

точка

P u ( u ) d U ,

удовлетворяющая

условию

|и — Рц (а) |= inf |и — о| = р (и,

U),

v£U

где р(и, U) — расстояние от точки и до множества U.

Если

u d U ,

го

очевидно, что Р и (и )= и .

Нетрудно

указать

множества U, когда проекция точки на это множество не сущест­

вует или определяется неединственным образом.

Т е о р е м а

1.

Если множество UczEm замкнуто и выпукло, то

ция Ри(и) на это множество.

Справедливы неравенства

(Ри(и)— и, v — P t/ («))> 0

при всех v£ U,

(1)

|Ри (и) — Ри (V) |<

I и — v I при всех и, v в Ет.

(2)

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

Рассмотрим

непрерывную

функцию

g(o) = |w— и\2 переменного v<=Em при произвольном

фиксирован­

ном tid E m. Нетрудно

проверить тождество

g ( a o + ( l — a)ie>) =

= ag-(o) + ( l — a ) g (w ) — a ( l — a)\v— w\z,

справедливое

при всех

v, ш е £ га и O ^ a ^ l .

Следовательно, g (o)

сильно

выпукла на

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

единственной точке

v, w d E m

и O ^ a ^ l .

Следовательно, g(v)

сильно

выпукла на

при всех

v d U , причем

равенство достигается

только

при v = v*.

точно, чтобы (g' (и*),

V—v * ) ^ 0

при

всех

v d U .

Поскольку

g ' (v ) = 2 ( v — и)

и v* = Pv (u), то

отсюда

сразу

получаем нера­

венство (1). Далее из

(1) имеем

(Ри (и) — и,

Ри (о) — Ри (и)) > О,

(Ра (v) —v, Ри (и) -

Ри (v)) > 0.

Сложив эти два неравенства, получим

0 3]

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

градиента

75

D — диаметр множества1

М (и0).

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

(и)

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

|ип— и* |2 <

2с 2

1

1 , 2 , . . .

(7)

--------•— ,

к ■е

п

Д о к а з а т е л ь с т в о . Прежде всего, если в (1)

принять и = ип—

— аЛУ' '(ип) и учесть (3),

то

получим

или

(ип+ 1 — ип -f

а J '

(«„),

и — «я+0 >

О,

( / ' («„),

И — H„+i) >

—

(«„•

■ил+1, и — w„+i)

при всех

«££/,

п = 1 , 2 , . . .

(8)

Заметим, что если при каком-либо п оказалось, что

ип= и п+и

то из (8) следует

(Г ( и п),

и— ип)^=0 при

всех

и<=£/, т. е. «„ —

стационарная точка I (и) на U,

которая в случае выпуклости функ­

ции будет точкой ее минимума на U.

Воспользуемся формулой (1.18)

при v= un, и = и п+ь Получим

J («п) — J («Я-и) >

(J' (ип) , ип— ц„+1) ----- —1

L\un — ил+112.

Отсюда с учетом условий (5) и неравенства

(8)

при

и = ип

получим

j (Un)

J (ил+1) ^

-------- I ип—

Ил+1 |2 ^

^ е |и „ — и п + 1 |2 > 0 ,

/г = 0,

1, 2, . . .

(9)

Как видим,

выбор

а п из

(5) здесь

гарантирует выполнение нера­

венства (4). Далее, из (9)

(или

(4)) следует,

что

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

ность {J(u n)}, убывает. Так как

J(u n) ^ J * > — оо,

то существует

lim /(«„), и, следовательно,

J(u n) —J (u n+i)-+-0(n-+oo). А тогда из

/I—>00

|ип— «п+1 |-И)(ц-*-оо).

(9) имеем

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

дополнительно удовлетворяет еще условию

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

ограничено. Ясно,

что {и „}& М (и 0)

и 7* = in f/(и). Поскольку

/ (и)

непрерывна, то

она

на

ограничен-

М(и„)

1 Ограниченность |7'(и)|

на М(и0) следует из ограниченности

множества

М(и0), условия Липшица для /'(и) и неравенств

IJ ' (и) |< |Г

(и) - Г

(и.) |+ IJ '

(«„) |<

L |и - иа |+ ' \ Г

(и0) |< LD +

|J ' (И#)|.‘

некоторой точке

и*е£/, причем J ( u * ) = J * .

Согласно

теореме

1.2

О <

ап = / («„) — J

(«*) < iJ ' («я). ип — «*) =

=

(J' («„). «п — Ид+l) — (^' («„), u* — u„+ i).

Отсюда с учетом (5) и неравенства (8) при u =

iC получим

О -С #л "С {J' (un) . ип— u/t+l)---------(“л — ип+1. и"— ип+\) -<

&П

< ( sup

I J ’ (u) |+

—

) |«Л — «Д+1 1=

cI un— ы„+ 1 1.

(10)

\M(«o)

el

J

Так как \un— un+\|-*-0(/i-»-oo),

to a n= J (u n) — /*->■0, т.

e. последо­

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

минимизирующая. А тогда

любая

предельная

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

{«„} является

точкой минимума

н в

{ип}-*-и*(и-*-оо). Из неравенств (9), (10)

имеем

а п — Q«+i >

а 2,п (и = 0,

1,

2, . . . ) .

Так как а „ > 0 (если

ап = 0,

то ип — точка

минимума),

то

отсюда

с помощью леммы 1.2

получим оценку (6).

Наконец, из

(6)

и тео­

ремы 1.6 следует оценка ( 7 ) . ^

В тех случаях,

когда константа Липшица L для J'(u)

неиз­

вестна,

при

выборе

а п вместо условия (5) следует использовать

условие

(4).

В этом

случае часто полагают an = a = c o n s t> 0

и на

/(«7l+i) < / (« „ ). Если оно нарушается,

то а

дробится до

тех пор,

пока не восстановится монотонность;

время

от времени

следует