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

100

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

[ Г л . 2

где Г =

inf J (и), а В >■ 0 — некоторая константа, не зависящая от п.

иеи

• - min ( l ; - L - - — ),

0 < e i < V „ < 2(1~

e)-

(« = 0 , 1 , . . . ) , (Ю)

l

I

- UnP J

L

a e, Sj — заданные параметры алгоритма,

0<^е1 <

2 ^ ~ е^г 0<<в<<1.

Возможно,

или

Р„ =

К

I J п(Цп) 1

> ИЛИ

1J п(цп) |

<Р„ =

[ ^п (Цп) |

J

_

D 2

IUn — Un Р

\ и п — и п |а

где D — диаметр множества U. В

обоих

случаях

имеем

0 < P n —

~ -

< 1 ;

min | l;

■' ^

--'j <

Р„ < 1 (л =

0 , 1 , . . . ) .

( И )

Заметим, что

если ип= ип или / п (« л )= 0,

то ип — стационарная

ние поведения функции в_ окрестности

точки

В дальнейшем

будем предполагать, что ипф и п> J n(un) # 0 .

Из формулы (1.18) при v = и„, « =

«„4-1 имеем

J . K ) — J

(“п+1) >

a n\JnЮ |-------I ип— ип |2 =

= « J

J а (“я) I

2

I Jn (Ия) | )

Отсюда с учетом (10— 11)

получим

J(u n) — J (Ия+ i) > о л |/л (йя)|^1 —

>

ССПЕ I J n (йп) I >

> e 1e m

i n | l ; ^ ^ i | | 4 ( « n)| (« =

0 , 1 , . . . ) .

(12)

102

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

[Г а. 2

а множества индексов 1ц /2 таковы, что /iU^2 = {0, 1, 2, . . . } ,

0е / 2.

/ i — 0 ,

/2= {0, 1,

2, . . . },

то Рп= 0 при всех п, и метод превратится

в уже

известный

нам

метод скорейшего

спуска.

Если

/2 = {0},

/i = {l,

2, . . . }, то получим обычный, классический вариант метода

сопряженных градиентов. Если /2= { 0 , s,

2s, 3s, . . . },

то

придем к

так называемому s -шаговому методу скорейшего спуска

(на прак­

для которых Р« = 0, называют моментами обновления метода.

Оче­

видно, что J (ий)

(« 1)

(ип)^ -. ■.

Оказывается,

метод

сопрялсенных градиентов сходится,

вооб­

тов предложена и исследована в работе [190]1; обзор

других схем

и модификаций, обсуждение практического опыта

применения

градиентов. (1) — (4). Для этого сначала докалсем

некоторые свой­

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

получаемых

по формулам (1)-— (4).

Л е м м а

1. Пусть

J ( u ) ^ C l (E,„).

Тогда

при любом

выборе

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

/2,

лишь бы /1U/2 =

{0,

1,

2, . . . }, Of=/2,

по­

следовательности {пп}, {Рп} удовлетворяют соотношениям

(J'(un+l) ,p n) = О,

(J'(u n) ,p n) = \J’ (un)\z

(п =

0, 1, . . . )

(5)

и

|р„Г =

1^(«„)|2 +

Рл|рп-.|2 > | Д (и л)|2 (Л =

1,2, . . . ) .

(6)

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

Соотношения

(6)

являются

простым

как /?о = Д («о), то второе из

равенств

(5)

при

п = 0

очевидно, а

1 Следует заметить, что в [190]

выражение для

|3П дано с точностью до зна­

ка. Это проще всего обнаружить проверкой условия

[Арп, Рп-0 = 0 , имеющего

место для квадратичных функций^

(см. ниже

лемму

2);

эта же

ошибка по­

вторена в работе [35].

S 7]

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

103

равенство

—

J'(u 0) ) —0

следует

из того, что

g '(a 0) = 0 при ао> 0

и

g'Q(ct-0) > 0 при а0 = 0 и формулы

(1.4).

"Пусть равенства

(5)

имеют место при некотором п^О . Пока­

жем, что тогда

(5)

верно и для

п + 1.

В самом деле, если

а „ > 0 ,

то согласно (3)

ё'пК ) =

~

(J>(ип — апРп), Рп) =

— (J' (Ы/Н-l). р„) = о.

Если же а„ = 0,

то ип+1 = и„ и

0 < g'n (0) =

— ( j’ («„), р„) =

— (/' (иа),

J' (ип) — P„pn_l) =

=

— |

(«„) I2 =

— |/' (un+i) |2 < О,

следовательно, /' («„+]) =

0 и ( J ' (ип+1), рп) = 0. Наконец,

(J ' (Un+l)i p n + l) — { J ' (Un+l), j ' (Цл+1)

Рл+lPn) = |J '

( Lin + 1)|2- A

J(u) = ± ( A u ,u ) - { b ,u ) ,

(7)

J' (и) = Аи — Ь.

(8)

и только тогда,

когда / '(«*) = А и * —Ь — 0.

Для минимизации функции (7) применим метод сопряженных

градиентов.

Так как

8п («) =

J

(«л — арл) =

-j-

а 2 (Лрп, Рп) — a (J' («„), р„) + J Ю ,

■

то min g n (а)

достигается

при .

а>0

а = а п

( J (Цд), Рп)

I г Ы I2 > 0 , п = 0, 1,

О)

( Арп ,Рп)

■ (Арп, Рп)

J' (un) — J' (Un+l) = а пАрп, П = 0, 1, . . .

(10)

(J'

(«„),. J' (u„_i) — J' {и,,)) =

а „ _ 1

(/' («„), Лр„_1) ,

IJ'

( « л - 1) I2 =

=

(J7 («л—0> Pn—l)

— (Д (Цп—l)

Д

{Цп)г Pn—l)

-

ал_1 (Лр„_ь р„_0

(/г =

1, 2, ...)•

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

(Л (ип) ,

Дрл-х)

п =

1,2,

( П )

№ л -1 , P n -l)

Как

видим,

для

функции

(7)

‘ метод

(1) — (4)

при /2 =

{0},

(/Г1= {1, 2, ...} совпадает

с

методом

сопряженных

градиентов,

описанным, например, в работе [9].

Л е м м а

2. Если /2 =

{0},

/i =

{l, 2,

...}, то

для

последова­

тельностей {tin}, {Рп}, получаемых по

формулам

(1),

(2),

(9),

(11),

справедливы соотношения

(J' («(). Pi) =

0

(I >

/),

(Д («О, Д («0) = 0

(t

/),

(Pi. APj) =

0

(iф j),

i, j =

0, 1, 2, . . .

(12)

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

проведем по индукции. Имеем (Д(«х), р0) =

=

(Д(«х), Д (« о)) =

0

в силу

(5) ;

И Р х . Ро) =

(Pi. АРо) =

(Д Ы — PiPo. АРо) =

0

в

силу

(11).

Предположим,

что

равенства

(12) доказаны

для ^всех

I,

/ < «

при некотором « >

1

и покажем, что (12) тогда

будут верны

при всех i, / < « - 1 - 1 .

Для

этого достаточно доказать,

что

Сначала убедимся в том,

что (Д («„+i), р;) = 0. При W — п

это сле­

дует из (5), а при

с учетом (10) и предположения

индукции

будем иметь

(J' («л+l),

Л («о)) = (Л (fi/l+l)i Ро) = 0.

Наконец,

с учетом (2), (10) и

предположения индукции при'всех i,

0 -< i < п

имеем

(Лр„+ь р£) = (р„+ь Лрг) = (Л («л+0 — pn+ip„, Лр(.) =

=

(Л («л+i), Лр,) =

—

(Л («„+]), Л («г) — Л («г+i)) = 0,

а,-

106

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

ПЕРЕМЕННЫ Х

[Гл. 2

Далее докажем оценку

vL|p„|2<

|/'(«„) |2, у =

*

,

п = 0, 1, . . .

(15)

L (1 + L-p, 2)

По теореме 1.4

(/' (ип) —

р |

|2, а

так как

ип— ип-\ — — an_i/?„_i, то с

учетом

соотношений

(5),

(6)

имеем

ра2_, |рп- 1 12

< а;г_ , (/' (и„_i),

p„_i)

=

a„_i |/' (u„_i)

|2,

или

to | I J' (un) I L I ип — un_i 1 ^ - 1

J' (un) I Lo.n-i I Pn-i I

_

L,

\J' (un) |

I Ря I

* т// \(Л

^

,

,9

'

|X

.

, 9

U

(“n-l)|S

p-a,,,! I

I2

I Pn-l I

или

| M lP n - l| < — \J'{Un)\.

V-

Подставим это неравенство в

(6)

и получим

I РпI2=

I J' (un) Is +

Рд I Рп-: I2<

(1 +

|J' («„) Г,

что равносильно

(15).

Теперь нетрудно доказать оценки (13).

С

учетом

неравенства

(15) и (14)

имеем ап— ап+1 >

cz ^ 1

—

Ц'(«„)|2 при любых а > 0 .

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

2v

J

ап — ап+1 >

max а ( 1 —

|J' (ы„) |2 =

\J'.(u„)\2

(п — 0,

1, . . . ) .

Но |J' (un) I2 >

\хап (см. теорему

1.6),

поэтому

ап — an+i >

^ ~ -аП,

илиап+1 < ^ 1 -----y ^ ^ an = qa,„

(л = 0 , 1 , . . . ) . Отсюда

имеем а п <

(л =

0,

1, . ■•)• Вторая из оценок

(13)

немедленно следует из

первой оценки и

неравенства

(1.15) при u =

un.

Остается заметить,

что 0 < < 7 < 1 ,

ибо р < L (см. замечание к теореме 1.5). ^

4.

В

заключение

заметим,

что

для'

минимизации гладк

функции J (и)

на замкнутом

выпуклом

множестве

1]ф Е т можно

ип+\ = Ри(ип— a-nPn) (n = 0 ,

1; .. . ), где

рп определяется согласно

(2), (4), величина ап> 0

выбирается

из условия

монотонности

J(u n)^J(u-n+\)■ Этот метод позволяет

за конечное

число шагов

S «]

Метод Ньютона

107

Упражнения. 1. Показать, что точка ип, полученная методом

сопряженных градиентов для функции

(7)

при / г = {0 },

есть точка

минимума J (и) на гиперплоскости, проходящей через

точку

и0 и

натянутой

на векторы {/'(«й)}

(&= 0,

1, . . . ,

п— 1).

Опираясь на

лемму

2, выяснить

геометрический

смысл

метода

сопряженных

градиентов [19].

2.

Описать

метод

сопряженных

градиентов

для

функц

J(u ) =

\Au—b |2

из упражнения 1.16.

§

8. МЕТОД НЬЮТОНА

1.

Пусть функция / (u )^ C 2(U) , где

U — заданное

множес

в Ет, в частности, может быть

U = E m. Для

решения

задачи

ми­

нимизации J (и) на

U можно использовать метод Ньютона, заклю­

чающийся

в

следующем

[155].

Пусть

взято

некоторое

начальное

приближение u0^.U. Если уже

известно

n-е

приближение ип-, то

приращение функции J ( u ) ^ C 2(U)

в точке ип можно

представить

в виде

J ( и )

— J

= ( J ’ ( « „ ) , и — ип) +

Y

(J" ( и „ )

(и — и„),

и — ип) +

+ о(\и — ип\у.

Возьмем квадратичную часть этого приращения:

J n (u) =

(J'(u n), и — ип) + ~^(J"(un)(u — ип),

и — ип).

Следующее

приближение

1

определяем

из

условия

минимума

J n{u)

на JJ:

J п (un+i) =

min J n (и).

(1)

u&U

В

случае,

когда

и =

Еф

в точке

минимума

J n (u)

на U

произ­

водная

j'n (и) = J' (ип) + J" (ип) (и—tun)

обращается в

нуль,

т.

е.

f n (un+l) = J' (ип) + J" (ип) («п+1 — ип) = 0.

Если

матрица

J" уип)

не­

вырождена,

то

отсюда

будем

иметь

ип+\ =

ип— [J" (un)]~l J ' (ип),

п — 0,

1 , . . . .

Как

видим,

в

случае U = Em описанный

итера­

Будем

предполагать,

что

имеется

некоторый эффективный

алгоритм

для решения

задачи (1)

при каждом п = 0, 1, 2,....

В случае

£ / = £ т таким

алгоритмом может служить метод сопря­

женных градиентов, описанный

в предыдущем параграфе, а- так:

108

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

же различные другие методы (см., например, [19]) решения систем

линейных

алгебраических уравнений

J'{u n) + J" (u n) (un+i—un) = 0 .

В случае

U=^=Em при решении задачи

(1) можно воспользоваться

одним из методов, описанных в предыдущих параграфах.

Нужно заметить, что задача (1)

в общем случае может ока­

Т е о р е м а

1.

Пусть

J (u ) ^ C 2(U)

на

выпуклом замкнутом

множестве

U ^ E m,

пусть

р|£|2<

(/ "(« )ё,

£)

при всех

и

u^ U , и

\\J"(и )— /"(и) ||<^L|u— v\

при

всех

и,

v^ U ,

где р, L —

некоторые положительные константы. Тогда

задача

(1)

разреши­

ма при всех п — 0,

1, ... Кроме того, если

начальное

приближение

Ыо выбрано так,

что q = —

[

— Ио|<1,

то имеет место следующая

Iх

оценка скорости сходимости метода Ньютона:

оо

K - « * K - f - £ < 7 24

где и — точка минимума J

(и) на U.

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

По условию

(/"(«)£,

|)^ р | ё|2 при всех

u e t i и

p = co n st> 0 .

Отсюда и

из теоремы

1.5 вытекает,

что функция J (и) сильно выпукла на U, и, следовательно, соглас­

но теореме 1.7 ограничена снизу на U

и достигает своей нижней

грани

в

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

точке

u *^ U .

Далее,

поскольку

J п (и) =

J" (ип),

то

функция J n (u)

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

достигает своей

нижней

грани

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

точке

un+i^ U .

Таким образом, задача (1) всегда имеет и

притом

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

решение. Применив теорему 1.3 к

функции J n (u),

получим

(J'n{un+X), и — ип+1 ) > 0 ,

u £ U ,

п = 0,

1 , . . .

(3)

Так как

J n(u) =

J'(u n) + J''(u„)(u — ип),

то (3)

перепишется в виде

(J' (ип) + J" (u n) (un+i — un),

и — ип+{) > 0,

u £ U ,

п =

0 , 1 , . . . .

(4)