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

10

МИНИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

ГГл. 1

О п р е д е л е н и е 2.

Пусть

/(w )eQ *[a,

b] и

пусть

вычислены

значения /(«О в некоторых точках { а ,}е [о ,

b],

( £ =1,

п). Ска­

жем, что тройка точек а„, Ьп, ип, локализует точку минимума J (и)

на [а,

6] по точкам

{и,}

( £ =1,

п)_, если: 1) а„, Ьп, ип содержат­

ся среди точек а, Ь,

ии

ип\2)

/(».„) =тш п/(мг-); 3) ап< и п< .Ь п\

_

1<£<л

чек ии_..., ип (т. е. на интервале а п< и < Ь п имеется

лишь одна

точка и„, в которой вычислено значение функции).

На практике часто бывает, что мы заранее ограничены числом

точек {« 1, .... ы „}е[а , Ь], в которых можно вычислить

значение

дачи А и Б. Поясним это на примере п — 2.

Пусть / (ii)eQ *[0 , 1],

пусть минимум / (и)

на [0, 1]

достигается

в точке к * е [ 0, 1].

Возь­

мем точки их — -£-(1 — б), «2 = — (1 + 6 ), 0 < 6

< 0 , 1 и вычислим зна­

чения

/(ui), /(иг).

Может

оказаться,

что

J (щ) ^ '/ (« 2).

Тогда

и *е {0 ,

щ]. В задаче А в этом случае в качестве приближения к и*

естественно принять точку и* = и1 с уже вычисленным значением

J {иi) « / ( и * ) . При этом гарантированная точность есть

|и* —•«*1 <

-< -■ — , поскольку в худшем случае для некоторых

функций из

Q*[0, 1] может быть и * = 0.

В задаче Б в качестве приближения к

и* можем принять

и* = —

(1 + 6) — середину отрезка [0, и2], ибо

значение Т(ыг) здесь нам не требуется, и получим

лучшую гаран­

тированную точность

\и*•— и* j < ^ -(1 + 6), чем в

задаче А. Слу­

S 3]

Оптимальный пассивный

поиск в

задачах А

и Б

11

чай

J ( u 1) > J ( u 2) рассматривается

аналогично

и приводит

к

тем

же

оценкам |«* — и2* 1 для задач А и Б.

Заметим,

что для

зада­

чи А возможен более лучший выбор точек

иг =

и и2 =

~ ,

дающий гарантированную на классе Q*[0,

1] точность, равную

— ,

3

Упражнения.

1. Как нужно

доопределить

функцию

J(u ) =

=

1/а!

в

точке

и = 0,

чтобы

J (и) <=Q[0, 1]? Q[— 1,

1]? Q[— 1,

0]?

6

“Г *

2.

Как

нужно

доопределить

функцию

J (и) = I

’

^

I

точке и =

чтобы J {и) 6 Q [0,1]?

1—ч ~т А, « < 0 )

в

0,

Q[— 1,0]?

Q [—-1,1]?

Q[a, b]

при любых a, 6?

Рассмотреть случаи А = 0;

+ 1;

— 1.

3. Доказать, что функция J (и) строго' квазивыпукла на проме­

жутке £/= {и : а ^ и ^ .Ь }

тогда

и только

тогда,

когда

/ (а « +

+

(1— a)v ) ^ .m a x {J(u ); J (v)} при всех и, в е й

и всех а, 0 < а < 1 ,

причем равенство

может достигаться

лишь при J ( u ) = J ( v ) .

4.

Если Ji(u ),

/2(w )eQ [a, b], то будут ли принадлежать Q[a,

Ь]

следующие

функции:

J\ {u )+ h (u ),

Ji(u ) —J 2(u),

J i( u ) - J 2(u),

Ji{u )/J2(u)?

§ 3. ОПТИМАЛЬНЫЙ ПАССИВНЫЙ ПОИСК в ЗАДАЧАХ А И Б

О п р е д е л е н и е 1. Пусть /(w )eQ *[a, Ь].

Скажем, что на

от­

резке [а, b] задана пассивная стратегия Р п, если:

1) на [а,

Ь]

за ­

ранее задаются все п точек {и,}

( г = 1,

.... п),

и0= а ^ : и 1< :и 2<. ...

... < и п^ и п+1= Ь и вычисляются

значения

J (щ)

( i = l ,

...,

п);

2) путем сравнения величин /(«г)

( £ =1, ..., п) определяются точ­

ка uk,

в которой J (uk) = min J («г), и

отрезок

uh+i],

содер-

жащий

точку и* минимума J (и)

на [a,

Ь] (таким

образом,

точки

12

МИНИМИЗАЦИЯ ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ

[Гл. 1

вете на эти вопросы будем различать задачи А и Б.

1.

Начнем с задачи А.

Пусть для некоторой функции / (ы

e Q *[a , b] с помощью пассивной

стратегии Р „ = { « £}

(i— 1,

...,

п)

среди точек

{« ,}е [« , Ь] выбрана точка uk, J (uk) = m in / («£)

и от-

резок [«ft_i,

«ft+i], содержащий точку и*

минимума /(«)

на [а,

Ь].

В задаче А в качестве приближения к и*

принимаем точку

и* =

uk,

допуская при этом погрешность

I и ” — и п I < т а х { “ *+1 ~

ы«> «ft — « ft - i} .

Очевидно любой другой выбор

и* с вычисленным

J

(«*)

для

резков [«,--1, «i+i]

( i = l , 2, ..., п) и погрешность \и* — «*| будет как

угодно

близкой

к шах{«,-+1— «,-, «£— «£_ 1}

(например, если

шах {«,+1— щ, iii— «i_i} =

«,+1— щ, то можно взять

— « -!- «i+i— 8 при « ^ « i+i— 8,

J g («) —

Щ-\) (и — ui+1 - f e)

при

« >

«i+i— e,

-J- («t+1 ~

где e

достаточно

малое

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

число).

И поскольку

^ Q*[a, b] и в

качестве гарантированной на Q*(a, 6]

точности в оп­

ределении и*

с помощью стратегии Р п должны взять максималь­

ную из возможных погрешностей;

шах ш ах{ « £+1 — «,, u£ — uC- i } =

max {«£+, — и£) =

L„ (Р , Ь — а).

Величина

Ln (Рп, Ь — а) от

/ (« )e Q * [a , b] не

зависит и ха­

рактеризует стратегию Р п на классе функций Q *[a, Ь].

Теперь естественно считать,

что пассивная стратегия Р п луч­

ше другой пассивной стратегии

РП, если

Ln(Pn>b — a)

<^L„(Pn, Ь— а).

§ 3]

Оптимальный пассивный поиск в задачах А и Б

13

■ О п р е д е л е н и е 2.

Пассивную

стратегию

Рп

назовем

опти­

мальной для задачи А, если Ln (Ь— а) = Ln {Рп>Ь— а).

Т е о р е м а

1. Для

задачи А при всех

1

оптимальная пас­

сивная стратегия существует, единственна и имеет вид

°п = Jt»i = а

■ Ь— а . .

уП

I

,

I

1 , •••

а + 1

Д о к а з а т е л ь с т в о . Прежде всего,

очевидно Ln(Pn, Ь— а) =

_= ь

а д дя

любой другой

пассивной

стратегии P n= W i} : я =

п

1

— < « n ^ « 7i+i = Ь всегда

отрезок [ии,

i= « o ^ « i< U 2<

найдется

■Wft+i] длины Uft+i— uk >

°

• и®°

в

противном

случае

сумма

длин всех отрезков [«i,

щ+{\

(f = 0,

1,

...,

п) будет меньше длины

отрезка [а, b]. Следовательно,

Ln (Р„, Ъ — а) =

шах {«i+i — и£} >

Ь ~ а

О<£<п

п

+ 1

для любой пассивной стратегии Р ц,

причем равенство здесь дости­

гается только при Рп = Рп. А

стратегии

P n= W i}

для некоторой функции / (u )eQ *[a,

Ь] найден

отрезок [Uh-u иь+ij,

содержащий точку и* минимума J (и)

на [а, Ь].

В задаче Б значение J (и*) нас не интересует, поэтому в качестве

приближения к и*

можем

взять и* = — (ы*—i +

Uk+\),

допуская

при этом

погрешность \и* —

— uk-\)

(любой другой

выбор и*

может

привести

к увеличению погрешности

при соот­

выбора стратегии Р п и функции / (n )eQ *[a, Ь].

Для любой фик­

сированной пассивной стратегии Р п= { щ }

нетрудно указать функ­

цию / (« )e Q *[a ,

b), для которой отрезок [«й_ ь

содержащий

точку «*,

будет

совпадать с любым из наперед

взятых отрезков

[Ы{-ь Щ+1]

( i = l ,

ti), и погрешность lu

— ипI

будет как угодно

•близкой к

— («£+1 — tii—i) (см., например,

функцию J&(u) из п. 1).

16

МИНИМИЗАЦИЯ

ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ

[Л/1. /

Из теорем 2— 3 непосредственно вытекает

С л е д с т в и е 1.

Для

любой пассивной стратегии Р п= { щ }

на

отрезке [а, Ь] существует

функция 7 (u )e Q *[a ,

b], такая,

что

для

тройки

точек ап, Ьп,

ип,

локализующей точку минимума J (и) на

[а, 6] по точкам щ,

ип,

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

Ь п - а п > ± = ± - = 2 1 * ( Ь - а ) ,

т-\- 1

где т — - j- для четных п, т = -п ~ 1 для нечетных п (п >

1).

Как видим, при решении задачи Б с помощью пассивных стра­

тегий предпочтительнее брать четное число п — 2т, поскольку

l L + i (b -

а) = Lfm (b — а) = .

?

2(/л+ 1)

О п р е д е л е н и е 1. Пусть / («)eQ *[fl,

Ь]. Скажем,

что на от­

резке [а,

Ь] задана последовательная стратегия Рп, если:

1) задано'

правило

выбора

первых

нескольких

точек и\, и2, ...,

us^ [a, b

( l ^ s ^ n ) ,

из которых определяются три точки as, bs,

й3, локали­

зующие точку

минимума

/(«) на [а,

b]

(см. определение 2.2);

2) если

l^ s < ;n , то по известному правилу на отрезке [cs, 6S] вы­

бирается

несколько точек

«s+i> •••> ии i(l ^.s<C.k^.n) и среди точек.

us, us+1, ...,

Uk определяется тройка аь,

bh, йь, локализующая точку

минимума;

если k< in , то на [a?,, 6/J по некоторому правилу выби­

тройка От, Ьт, йт и т.

д. Этот процесс продолжается до тех пор,,

пока не будет выбрана

последняя п-я точка и определена соответ­

ствующая тройка

а п, Ьп,

йп, локализующая точку, ы*

минимума

/ (и)

на [а,

Ь]; 3)

имеется

правило, по которому одна

из точек,

ы* £

[а п, 6Л]

принимается в качестве приближения для и*.

§

*\

Последовательный

поиск

1Г

Очевидно: [а, Ь] =э [as, 6S]

[ak, bk\=э . . .

[ап, bn],

J (ип) =

=

min J

(ut) an<C.un<C.bn, an<iu* <

и на интервале а „ < и < 6

l<i<n

нет точек с вычисленным

значением

функции.

Отсюда

кроме

довательных стратегий

Р п, согласно которым в

задаче А

прини­

мается ип = ип, а в

задаче Б — и* = — [ап +

Ьп], ибо

любой:

ной стратегии, будем называть последовательным поиском.

^

Указанный выше способ выбора и *

в задаче А приводит к

погрешности |«*— « *| < т а х {& „ — ы’ , и*— а„},

причём для

любой

фиксированной последовательной стратегии

Р п нетрудно

указать,

функцию J(u )^ Q *[a, b], для которой эта

погрешность будет как

угодно близкой к

таах{Ьп-— и*п, и\ — ап).

Для

выбранной страте­

гии Р п в качестве точности, гарантированной

на классе

Q*[a, b]„

естественно теперь взять число

Ьп (Р„, Ь— а) =

sup m ax{bn — u„, ип* — ап}.

О п р е д е л е н и е 2. Последовательную стратегию Рп

назовем:

оптимальной для задачи А, если

Ьп (Рп,

Ъ - а ) =

inf б £(Рп, Ь - а )

=

б £ ( Ь - а ) ,

Рп

Стратегию

Рп

назовем s-оптимальной, если

Ьп(Р „,Ь —

< 6 л (b — а )+ е ,

е > 0 .

Для

задачи

Б аналогично определяются

погрешности

1“* — < l <

Y ( 6n~ an)’

Ьп(Рп,Ь — а) =

=

sup

-\-(Ьп — а п),

6п(Ь — а) = inf6^(P„, b — а),

J&Q'[а,Ь\

2

■ Рп

понятия оптимальной и s-оптимальной стратегий.

Допустим, что мы построили какую-либо

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