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

ТП— 1

т—1

„2*

f c = f l

k=n

k=n

1 — q*n

->-0

(7)

при т > / г —»-оо. Таким образом, последовательность {«„}

фундамен­

тальна и поэтому

сходится

к некоторой точке «*. В силу

замкну­

тости множества

U точка

« *e t/ .

Переходя к пределу

в

(7) при

т-*-оо, получим

| и * -и я | < 4

S

? к

(Я = 0 , 1 , . . . ) .

L

л—j

k — n

на U. Так как J{u )j= C 2(U),

то /'(«„)-► /'(«*), J" (u n) - + J " (и*) при

п~+оо. Поэтому переходя к пределу в

(4) при л—►-оо,

будем

иметь

(/'(и *), и— «*)^ г 0 при

всех

u ^ U . В

силу теоремы

1.3 и

выпук­

лости J (и) это означает,

что и* есть точка минимума J (и) на U-Jl

Как видно из оценки и

как подтверждает практика,

метод

Возьмем функцию

при

|и |<

б,

J (и) = — и2 + 2 1и I — — б

w

2

1 '

4

при |и |> б,

u(zE lt

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

положительное

число,

0 < 6 < 1 . Не­

трудно убедиться в том, что

Z (« )e C 2(£ i)

и

J " ( u ) ^ 1, так что

J (и) сильно выпуклая функция.

Эта

функция

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

минимума на Е i .b точке ы *= 0 . В

качестве начального приближе­

ния возьмем

«о = б . Применяя

метод

Ньютона,

получим последо­

вательность

Г K _ i)

( л =

1, 2 , . . . ) ,

«„ = «„ _ ,------ = ( - 1 ) " 2

J

(“n-l)

которая расходится, хотя начальное приближение

отличается от

«* = 0 на малое число б.

§ 8}

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

111

J п f a ) — ( J ' fa n ) > ^

^ п ) '1 “ ( J fa n ) f a

^н)> ^

^ п )

приращения J (и)— / (« „ )= / „ (« )+о(|ы — ип \2)

и определим

вспо­

могательное приближение йп из условия:

J n(un) =

m in Jnfa).

(8)

и

Сразу заметим, что J п (ип) <

J n (ы„) =

0.

Далее полагаем

Ц-п-\-\— ип -f- а„ (ип

tin),

(9)

где а„ выбирается из условий

J fa n )

fa n “Т &п fa n

^/1))

|J п fa n ) I»

6

^ п

^ »

( 1^)

е — некоторое фиксированное число, 0 < е < 1 . Если

ип не являет­

ся точкой минимума / (и)

на U, то при некоторых

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

на функцию J (и)

можно

доказать

возможность выбора >йп, а„,

ип+\ из условий (8— 10)

(см. ниже теорему 2),

причем для ускорег

ния поиска минимума желательно выбирать а п как

можно

ближе

к 1. Метод

(8— 10)

—

естественное обобщение

одного

из вариан­

тов метода

условного

градиента

(см.

(6.1-—2), (6.8)).

В

методе

рем а „= 1

и

проверяем

условие (10).

Если оно .выполнено,

то

оставляем

ап= 1 ; если

же

(10)

при а „= 1

нарушается,

то

производим

дробление ап до

тех

пор

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

(10)

не

выполнится,

стараясь остановиться

на

значении

а„, как

можно

близком к

1.

При некоторых ограничениях на функцию J (и) ука­

112

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

[Гл. 2

Таким

образом, метод (8— 10) ненамного сложнее

метода

квадратичной функции /и(«)

на U метод

(8— 10) можно с успехом

применять для минимизации достаточно гладких функций.

Т е о р е м а

2.

Пусть U —

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

/ (ы )е С 2(П ),

ц|||2< (/ "(и )| , .|)<М |||а

при всех

и всех

u<=U, и пусть

||/"(«)—/"(o)J|^L|u— п|

при всех u, vt=U, где ц,

М, L — положительные константы. Пусть ei — некоторое число,

0 < е 1< — — (1 — б).

Тогда на отрезке

e ^ a ^ l

при

каждом

п существуют числа а„,

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

(10)

и среди них найдется максималь­

ное. Подставляя

это максимальное а п в

(9) для любого

началь­

которой:

1)

{ J (ип)}

монотонно

убывает

и

стремится

к

/* = inf/(u) (n-voo); 2)

существует

такой

номер

/г0=/г0(е),

что

<7 =

—

1«п„+1 — ып„| < 1,

и

а п =

I,

un+i = un

при всех

п ^ щ ,

т. е. метод (8— 10)

с номера

п — п0 превращается

в метод Ньютона, и, следовательно,

будет

верна оценка

(2)

при

всех п ^ п 0.

Д о к а з а т е л ь с т в о . По условию (У"(ц)£,

g)^|i|£|2

ПРИ всех

и ^ e £ m, p ,= co n st> 0 . Следовательно,

J (и)

—

сильно выпук­

лая функция

и в силу

теоремы

1.7 ограничена

снизу на

U и до­

ку

J n (и) = 7 " (ип),

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

также

сильно

выпукла_на U

и

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

нижней грани

в

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

точке

«пе У .

Может случиться,

что ип= и п. Тогда

и* = ип= ип. В самом деле,

применив теорему 1.3 к функции /«(и),

имеем

(/п(ип),

и — ип) > 0 ,

или

(J ' (и-п) + J" («л) («„ — ип),

и — ип) >

О,

и 6 и.

Если ип= и п, то

отсюда следует,

что

(J'(un), и— ип)^ 0,_ и < = и .

В силу теоремы 1.3 и выпуклости / (и)

заключаем,

что и*_==ип= ип,

и задача решена.

Поэтому ниже будем считать,

что ипФ и п, и,

следовательно, /п (м п )< ^ п (« п )= 0

при всех

п = 0,

1, 2, . . .

. Пока­

жем, что на отрезке E i ^ a ^ l

существуют

числа

ап, удовлетво­

ряющие условиям

(10).