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

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)