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

(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)