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

250

МЕТОДЫ

М И Н И М И З А Ц И И В

Ф У НКЦ И О НАЛ ЬНЫ Х ПРОСТРАНСТВАХ

[Гл. 6

б) а „

определяется

из

условия

J ( u n) —/(m„+i) ^e||«n— «„+il|2,

где Un+i имеет вид

(2), е — параметр алгоритма, е > 0 ;

в) а п можно выбирать,

как это указано в п. 1е).

Т е о р е м а

2. Пусть

функционал

J (и) определен на выпуклом

замкнутом

множестве

U

гильбертова

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

Я , J (и) 6 С1 (U),

inf J (и) = J* >

— оо,

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

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

ЛИЛ­

ЛЕЦ

'

L =

и, v 6 U.

шица I J' (и) — J' (и) |< L |и — v ||,

const > 0 ,

Пусть

и0— произвольная начальная точка

из

U

и последовательность {ип}

определена

по

формуле

(2)

с выбором

параметра

а п из условий

0 <

ех < а п <

■

L + 2е

Qi>-

•заданные положительные

числа,

0 < 8 1 < -

2

Тогда

L +

2в

j (ип) — j

(«Д+0 >

8II ип— ип+1|Р,

п =

0,

1, .. • , limIIип— wn+,II = 0

Д -*о о

{если Я = Я ,

то равенство lim||«„— Wn+i||= 0 равносильно П т У' (ип) = 0).

Д -»оо

Д -*э о

Если, кроме того, J (и) — выпуклый функционал, и множество

M^{uo) — {u :u ^ U ,

J (и) s£ZJ(и0)}

ограничено, то

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

ная точка будет точкой минимума J (и)

на U, причем в случае един­

ственности

точки

минимума к

ней слабо сходится вся последова-

тельность

{«„};

справедлива

оценка

Q

0<СУ(«„)— J* -С ——, С\ =

= co n st> 0 ,

п = 1, 2, ...

п

Если / («),

кроме того, сильно выпуклый функционал на U, то

{ип} сходится

к

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

точке минимума ы* по норме про-

Q

п = 1 , 2, ..., C2= c o n s t> 0 .

странства Я , причем \ип— ы*|р<——,

11

§ 2]

Некоторые методы минимизации функционалов

251

Un+ 1 = Р ц ( ип— а н

\ п = 0, 1,

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

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

со свойствами а пХ ) ,

00

а л -» 0 (п-^оо),

а г =

оо /например,

а п —

i=o

'■

п -4- 1 ) -

J(u )^ C '(U ) .

Метод условного

градиента

заключается

в

следую­

щем:

если Un

(п ^ О )

уже известно, то берем главную

линейную

часть

J n (u )s= (J'(u n),

и— и п )

приращения

J (и)— /(ип) =

( Г ( и п) ,

и— ип)-\-о(\\и— ып||) и определяем

вспомогательное

приближение-

йп^ .и из условия

J n Ы

=

min J n(u) или (/' (ип) , йп) =

min (5 (и„), и).

(3>

иеи

uEU

Затем

полагаем

[35, 36, 82,

93,

94,

97,

124, 154,

155,

179,

229]

un+i =

ип +

ап (ип — ип),

0 <

a n <

1,

(4>

а)

8п К )

=

min gn (а ), gn (а) = J ( u n + а (йп — ип)),

(5>

0 < а < 1

б)

J (un) — j

(un+i) > е а л I J n (un) 1,

0 <

а„ <

1, где

е —- параметр-

алгоритма;

0 -< е <

1;

в) если

|J' (и) — J' (о) ||< L I и — v | при

всех u ,v £ U ,

L =

— const >

0,

то

а п можно

определить

так:

а п — у„рл,

где

р„ =

= mi nl l ;

——

— J, ех < ; у л < —- — —, ех

и

е —.параметры

алго-

I

11«„-М 3 I

L

ритма,

2

(1 _е)

Заметим,

что приведенное здесь.

0 < е 1 •<------— -, 0 < е < 1.

описание

метода

условного

градиента сохраняется без

изменений

и в 5-пространствах.

Т е о р е м а

3.

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

замкнутое

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

пусть функционал

/ ( п ) е С 1(Д),

inf J(u) — J*^> — оо

и градиент

J'(ti) удовлетворяет

условию

u £ U

\\J'{u)— J'(v) ||^L||«— t>||

Липшица

при всех и, v<=U,

L = c o n s t> 0 .

Тогда

последовательность {w„},

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

условиям

(3) — (5),

существует

и

J n(u„) =

= (/'(мп),

йп— п„)->-0

г(/г->оо)

при любом

выборе u0^U .

Если,

кроме того,

/ (и) выпуклый функционал на

U,

то после­

0 < ая = / ( ия) - / * < - ^ 1 л = 1, 2,

(6)

п

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

начальное

приближение

u0^ U

выбрано произвольно. Пусть уже известно

и„ (п^О ). Так как

J n{u) = (Л (м„), и— ц„) линейный

(и тем более выпуклый)

непре­

Доказательство утверждения

/n (wn)-vO

(п->оо) проводится

дословно так же, как в теореме

2.6.1. Если /(и) выпуклый функ­

ционал, то

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

/ (« * )= / *

следует из

теоремы

1.4, э т о т

факт, что {ип} — минимизирующая

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

является следствием неравенств (2.6.6).

В силу теоремы 1.2 множество U слабо

компактно,

поэтому

довательности {a„fe}. Но J (и)

слабо

полунепрерывен снизу, поэ­

тому

J* = lim J (ип) =

lim J («„

) > J (а*) > /*,

П -» оо

S 2]

Некоторые методы минимизации функционалов

253

5.

Метод сопряженных градиентов. Пусть

функционал J (и

£ С1(Я ).

Построим последовательность {ип}

по' правилам [35,

124,

166,

179,

190]

МцЦ-l

11ц

Ctt/iPm

f t

1» 2 ,

• • •,

Ро =

J ' («о),

Рп =

J' (ftn) — $пРп-1,

п =

1, 2,

. . . , .

где величины а п, (3„

выбираются из условий

ёп К )

=

min g n (а), g„ (а) == J

(и„ — арп),

а>0

(J'(un), J' (u„-i) — J' (и„))

ft € h ,

II/'(«л-0 II2

о ,

n

£

I z ,

а множества индексов /1,

/2

таковы,

что /iU^2 = {0,

1,

2, ...},

0е / 2.

На

практике

часто

принимают

/2= { 0 ,

щ, п2, ...},

где 0 < n i <

< п 2<

... — заданная

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

например

n u = ks,

s —

некоторое натуральное

число, k — 0,

1, 2........... Если

/2={< ?},

11=

= {1, 2,

...}, то этот метод превратится в метод скорейшего спуска.

Пусть U — выпуклое замкнутое множество в Я-пространстве

(или

в 5-пространстве), функционал J(u)<=C2(U). Пусть ип ( п ^ 0)

уже

известно. Тогда берем главную квадратичную часть

J n (и) = (/' (ип), и — un) + - L (J" (ип) (и — un) , u — un)

u £ U

Затем полагаем

Чп+1 = ип +

0 < а л < 1,

254

МЕТОДЫ

М И Н И М И З А Ц И И В

Ф У НКЦ И О НАЛ ЬНЫ Х

ПРОСТРАНСТВАХ

[ Г л . S

а)

а ,1 = 1 , п = О, 1, 2,

...

(здесь имеем дело с методом Ньютона

в его классическом виде);

б)

ёп Ю

= min g„ (a),

gn (а) = J (ип +

а (йп— гг,,));

0<а<1

в)

J {ип) — 7 (« n+i) ^ е а „ | /„(«„) |, где

е — параметр алгорит­

ма,

O C e C l,

а величина

а п выбирается

как

можно ближе

к 1,.

вается совершенно так же, как в теоремах

2.8.1— 2,

сходимость

варианта б)

см. в работе [82].

7.

Метод штрафных функционалов

[27, 35,

75, 155, 162, 1

на

заданном множестве

Ui банахова пространства

В

(возможно,

U i= B ) . Пусть

и =

{ и : и е и ъ g ( u ) < 0 } .

(7>

Заметим, что множества вида (7) охватывают такие множест­

ва как Ui = {и : u^.U\,

h ( u )= 0}, поскольку U0= { u : u ^ U u

g(u) =

=

h2(u)^Z0}. Если же

U0= {и: u ^ U ь g i ( u ) ^ 0 (г =

1,

2, ...,

s)}, та

8 (ц) = £

(“)]+»

гДе [&; (“)]+ =

max {£; (“); °}-

i=l

О п р е д е л е н и е 1. Функционалы Ph(u)

( k = l , 2,

...)

называ­

ются штрафом или штрафными функционалами для

ограничения

£(гг)г^0

на

множестве

U\,

если: 1) Ph (u) ^

0

при всех

гге^Л я

k = \ , 2,

...;

2)

Н тРй(гг )= 0

при гге£/,

П тРй(гг) = + о о

при гге(/ь

но и ф и .

k-*ao

k-*oo

Примеры

штрафных

функционалов:

Рк (“) =

4 U r ( “)]+.

p k(“) =■•

= Л ([ Я (“)]+)2. ^ * (« )=

- ± — еА^ и) и т.

п.,

где

Ak — некоторая

пос-

ледовательность, Ак > 0

(k =

1, 2, . . . ) ,

Ak

+

оо при

£ ->- оо

(ср.

С §2 .9).

Пусть на множестве Ui задан функционал /(гг), и пусть тре­

буется минимизировать

/(гг)

на множестве

U вида (7).

Заменим

/й(гг )= / (гг)+ Р й(гг), k = l , 2, ...,

на множестве Uь где Р й(гг)—

штраф для ограничения g (u )^ .0

на U\. При каждом k задача ми­

либо методом

(например, одним из вышеописанных методов). '

В прикладных задачах нужно стараться представить множе­

ство U в виде

(7) так, чтобы множество Ui, входящее в (7), имела