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

ТП— 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).

114

М И Н И М И З А Ц И Я Ф У Н К Ц И И

М Н О ГИ Х

ПЕРЕМЕННЫ Х

Гл. 2

— У(ц„)] =

0.

Из

(14)

теперь

имеем

1

(«„) |— 0,

а

из

(13)—

\и

— ип|— О (п —> оо).

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

существует

такой

номер

п0 =

п0(е),

что

-----\un-— ия | < 1 — е

при

всех

п>/г0.

Из

(11)

с

учетом

н*

для

J" (и) и

оценки

(13)

для

всех

а,

условия Липшица

<

а < 1,

тогда имеем

j

Ю

— J («а) >

—

а3£

-т

а I J a (и„) I------—

I ип— ипI3 >

>

IJ,, (М п)

I

1 — -^-'1 Й„ — йпI ^

>

ае I J n (й„) |

при

всех /г>/г0. Это означает,

что (10)

выполнено при

всех

а„,

Ч < % < 1

и,

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

максимальное

среди

таких

ап

есть

an =

1

при всех

п >

п0.

А тогда

согласно

(9)

Un+i =

un,

J n (un+1) =

J n (ип) =

min>„ (и),

u £ U

■

т.

e.

начиная

с

номера п =

п0,

рассматриваемый метод

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

в

метод

Ньютона

с

начальным

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

и„0,

таким,

что

q =

—

|и„0+1— w„01< 1.

Поэтому

оценка

(2)

будет

верна

при всех

п > п0. А

Существуют и другие способы выбора

а п в

(9),

например, в

работах [81], [82] ап предлагается

искать

из

условия

минимума

функции J {ип+ а (и п— ы„))

переменной а при 0 - ^ а ^ 1 .

О методе

Ньютона см. также в работах [4, 19, 27,

35,

46, 75,

81, 82,

97,

130,

152,

155, 170,

1.93, 235] и др.

Un+1 = Un — (J" (мл))-> J' (и„),

п = 0, 1, . . . ,

на каждом шаге которого требуется

обращать

матрицу J"(u n).

Возникает вопрос, нельзя ли построить методы

минимизации,

обладающие высокой скоростью сходимости, как

метод Ньютона,

un+i = ип— а пДГ1J' (и„),

п =

0,

,

(15)

где а пфО

скалярный

множитель,

Ап —

квадратная

матрица

m-ного порядка, такая, что \\Ап— J"(u n) ||-й) (п-+ оо).

Следуя (86], опишем один из способов выбора матрицы Ап и

величины

а п в процессе

(15). Зафиксируем какую-либо

последо­

вательность векторов

Го,

гь ..., гп, ... ,' обладающую

свойствами:

1) |г'тг| —

при п-*-оо;

2)

существует

число у > 0 , такое,

что опре­

rn

гп—1

rn—m+1

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

неравенству

Ап^ у

при

всех

п = т — 1,

т ,...

В остальном

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

произвольна.

Например,

можно взять

r0 =

^o®i>

■••, гт—1 =

A.m_i ет,

гт— Хте1л . . . , г2т—i =

:

^ 2 т—1 £т ,

Г2 т =

^2те1> ■■■ I

rn =

e i+l>

••• ,

где 6 j=

(0,

. . . ,

0, 1,

0, . . . ,

0 ) — единичный

вектор

по

оси

Ои},

i —‘ остаток

от

деления

целого

числа

п

на

целое

число

т, О ^ г^ / п — 1,

последовательность Хп->0

при п-*-оо,

Хп> 0 при

всех п— 0,

1, .. .

Пусть последовательность {г„} с указанными свойствами уже

выбрана. Тогда матрица Ап в соотношении

(15) при каждом фик­

сированном п ^ т — 1

определяется из системы линейных алгебраи­

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

;

- J' (Un—i ~Ь Гп—/)

J' (Un—j),

/ =

0, 1, . . .

,

т —

1.

матрица Ап невырождена,

( 16)

Если полученная

при этом

то нахо­

дят ДГ1 и при выполнении условия

(ДГ‘ J' (ип), J'

(«п) ) > 0

присту­

п аю т^

выбору

величины

ап в

(15).

Для

этого

вначале полагают

ап =

“ я. где

аП= min

( У ( и п ) , Un

U g ) “| ^

• и„ — и„

An

J' (Цп)>

\ип—Й„|3 J

=

const > 0 ,

и проверяют справедливость

неравенства

J(u n+1) — J(Un)<C еа„ (Д (ы„),

ип — ип),

0 < е < - ^ -

(17)

§ 9]

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

119

В качестве штрафной функции множества (2)

могут служить,

например, следующие функции:

Рц (и) =

k [g («)]+, Р„ (и) =

k ([g (u)]+)2,

Pk («■) = 4 -

ekg(u\ Pk (и) = (1 +

[g («)]+)* -

1

k

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

на Ет при фиксированном /е>0,

а нужно лишь

позаботиться о том, чтобы с ростом k

эта

задача

решалась все

точнее и точнее.

А

именно

обычно

берут ка_кую-либо функцию

е —е (6 )> 0 при & > 0 , е(£)-И ) при k-+oo

и с

помощью того или

иного метода минимизации определяют точку Uih такую, чтобы

Л =

inf. J k (и) <

J k (uk) <

4

-г e (k),

k >

0.

(3)

uSEm

Т е о р е м а

1. Пусть функции /(u),

g(u)

определены

и непре­

рывны на Ет,

i n f / ( w) > — оо,

пусть

U =

{и : g(u) ^ 0 } .

Пусть

т

Pk(u) ==Qh(g(u))

штрафная функция

множества U

имеет

вид

определена,

непрерывна

и

неотрицательна

при

всех

g;

2) Q k(g)> 0,

монотонно

возрастает

по

g и 1 im Qk (g) =

-j- ос при

g > 0 ; 3)

если g ^ O , то

Qk(g)-+0

(Jk-*-+oo) равномерно

относи­

тельно gs^O. Пусть {Uk}

определены из условий (3)

при некоторых

е(/г) > 0 , г(/г)-+0

при k->-+ оо.

Тогда: 1)

Нгп / (uk) <

J" — inf / (и), l i m g ( « ft) < 0 ;

2)

если

мно-

£-->оо

« £ £ /

£ — >4~°°

бы одну предельную

жество {иА} при k

+ оо будет

иметь

хотя

точку и*,

то

и* — точка

минимума

J (и) на U\ 3) если

множество

Ue — {u :g (и) ■< 6}

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

бы

при

одном

6 =

60]> 0 , то

lim J (uk) — Г ,

р (uk, U) =

inf \uk — и |->-0

(6-»-оо) и любая предель-

£ - * о о

и £ ( /

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

на U,

а в

ная точка {uk} при /г -> +

о о

случае единственности точки минимума \uk — и* |-»- О

[k

оо).

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

Пусть

{&,„} — какая-либо гминимизирующая

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

J {и)

на

U, т.

е.

ьт6 U

и J {vm) ->•Г (т

оо).

Возьмем

произвольное е > 0 .

Тогда

найдутся

такие

числа

/«о > 0 ,

k 0>

0, что J

( o j

<

/* +

е, е (k) <

е,

Pk (om) = Qk (g (vm)) <

г

при всех

т >

т0 и &>&„.

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

с

учетом (3)

получаем