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

Как известно [56], числа Фибоначчи определяются так:

F n+2=

= / 7n+i+^n,

(/ i= l, 2,

...);

/7i = / 72 = 1 .

Нетрудно

показать,

что

F „ =

1 +

/ 5

1

— / 5

. / 5 .

Перейдем к описанию

плана

Фибоначчи Фп

(n^sl).

Пусть

J( « )e Q * [a ,

b\. При п— 1

план Ф\ прост:

берем «1

__

а

Ь

и вы­

числяем значение 1(щ ). Полагая

и[ = и1,

определим

точку

мини­

мума и* с погрешностью

К

— « ! | <

Ъ— а

6 — а

2

Пусть теперь п > 2 . Тогда план Ф„

начинается

с

выбора

двух

точек

«х = аЧ-----—— (6 — а),

и2 =

а + — п+1

(Ь — а) =

а +

Ь— их,

Рп+2

F n+2

расположенных на отрезке [а,

6]

симметрично,

и

вычисления значе­

ний

JijUj), J

(и2).

Если J

(%) < J (и2),

то

полагаем

а 2 =

а,

Ь2 = и2,

и 2 =

и1\ если же J (их)^> J

(и2), то а 2 =

ult

b2 — b,

и2 — и2. В резуль­

тате

получаем отрезок

[а2,

Ь2]

длины

р

(Ъ— а),

Ь2— а 2 = b — и1 = и2— а — —

Fn+2

содержащий

точку и*

и точку и2,

а 2< ы 2 < 6 2,

в

которой

J (и2) = min{J (их), J {и2)}.

Заметим, что

точка и2 совпадает с

одной

из точек '

щ =

а 2+

/ —

(р2 — а 2) =

а2 +

Гп+2

{b — а) (при J (их) <

J

(и2))

г Л+1

31ЛИ

ul = a 2+

F"~1■- {b, — а2) = а 2 +

^,1~1 - (6 — а) =

ГП+Х

* Л +2

= а2 +

Ъг — «2

(при J Ы

> 7 (и2)).

Далее на отрезке [а2, 62] выбираем следующую

точку и3 =

а 2-f b2—

— и2,

вычисляем 7 ( а 3)

и сравнением величин 7

(и2),

J

(us) находим

новый

отрезок [а3,

63]

и т.

д. (рис.

2).

В

общем случае,

пусть точ­

22

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

\ГЛ. 1

ки

иъ

. . .

, ик (2 <

k < п)

уже

выбраны,

пусть

найден

отрезок

[ak,

bk\ длины

bk- a k = - ^ s - ( b - a ) ,

Рп+2

содержащий

точку и* и точку ик,

ак < ик •< Ьк,

с

вычисленным

зна­

чением

J

(ик) =

min J (U[),

причем

точка ик

совпадает с

одной

из

точек

= а* +

г n - f t + 8

(& * - * * ) = a* +

“ /7 + 2

(6 — a)

ИЛИ

“* = e* +

Фк — ak) = a* +

"4 ”—

- (6 — a) =

— uk.

Если

то на

отрезке

[ak, bk]

выбираем

следующую

точку:

uk+\=

ak +

Ьк — ик,

симметричную

с ик на этом отрезке и

совпада­

ющую

с одной из точек и'к, ик, отличной от ик.

Вычислим

значение

J (ик+ О

и сравним с

J{u k). Пусть для

определенности ик =

ик <^ ик=

= Uk+ 1

(случай Uk+i = u'k<

Uft = uk рассматривается

аналогично). Тог­

да при

J

(Uk) <

/ (Uk+i)

полагаем

ак+1 — ak,

bk+] = ик+и

uk+\ = ик.

Если же

J (ик) >

J (uk+i),

то ak+l =

ик,

bk+l =

bk,

ик+1 = ик+и В

ре­

зультате

получаем отрезок

[a^+i,

Ьк+1]

длины

bk+1 — ak+1 =

- 4

fe— Ф — a),

•»/2+2

содержащий точки и* и «*+1, afc+i <

•< bk+u

с известным

значе­

нием J(u k+ i)= min J (u£),

причем

точка ик+1

совпадает с

одной из

«ft+1 — Oft-fi

~

— (frft+i ~~ ak+i) — Oft+iЧ— тг~~ (b— а)

ИЛИ

* H -fc + S

*

Л + 2

«ft+1 =

Oft-j-i +

-

■(6ft+i — Oft+i) =

Г Л - f t + 2

— Oft+1 H—

г П +2

(b — a) =

aft+i +

bk+i — «ft+i,

и T. Д,

Если k = п, то процесс заканчиваем и

полагаем «^ =

«„

с

вы­

численным значением J

(ип) = m in /(«,).

Заметим,

что

при

/е = /г

длина отрезка

[ап, Ьп]

1<1<Л

равна

Ьп — а п =

F3

{ Ь - а )

2(6 — а)

Fп+ъ

гFЛ + 2

’

И ТОЧКИ

'

I

, и

\

,

6—а

ип = ап + —- ± — (Ь — а) = а п +

—

------,

* п+г

* * л + а

"

I

/**«

/*

ч

.

&—a

Цд =

ал + —р * ■-

(Ь — о) =

оя +

— ------

- '" л + 2

*

Л + 2

совпадают и делят отрезок [ап,

6„] пополам.

Таким

образом,

прини­

мая «л = ыя =

«„ = «п, мы допускаем

погрешность

,

»

* ___

Ь —а

|и — « л | < — -------

* л+2

независимо от выбора функции J (и) в Q* [а,

Ь].

Нетрудно видеть,

что

для функции J (и) =

и £ Q* [а, Ь]

план Фп дает

погрешность в опре­

делении и* — а, в точности

равную

ь ~ а. _

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

F n + 2

б£(Ф я, b — а) = -^г— - (« > 1).

Л + 2

План Фибоначчи Ф„ полностью описан [56],

[230].

Отметим одно замечательное свойство плана Ф„: применение

плана Фл_б+ 1

к отрезку

[afe, Ьи], полученному

в

результате

пер­

должению плана Ф„ на этом отрезке [а;г, &ft],

Этот факт

вытекает из того,

что первые

две точки плана

Фя-/г-н

совпадают

с точками и*, и*,

или, что то

же самое, с точками uk,

«ft+i пла­

на Фп-

.

•

§ 6]

Оптимальный последовательный поиск для задачи

А

25

Таким

образом, стратегии Р п,

начинающиеся

с

выбора

двух

точек «ь и2,

a ^ .u i< u 2s^b,

где

заведомо

неоптимальны.

Аналогичные

рассуждения

показывают, что стратегии Р п с выбо­

ром точки

и2> и 2 также

не могут быть оптимальными.

Пусть

теперь

В худшем случае точка и* может на­

ходиться на отрезке [а, и{\ длиной

их—

— а = ——— (b — а),

Рп+г

*

(РП, ь - а ) > 6„А- 2 (Фп—2, Щ — а) —

Гп

Гп

=

=

Ь р -

= ЪКа(Ф п, Ь - а ) .

Таким

образом,

стратегии

Р п,

начинающиеся

с

двух

точек

U\, и2,

a^.Ui<Zu2^ .b,

где

,

заведомо

неоптимальны.

Ана­

логично

доказывается

неоптимальность

стратегии

Рп в случае

ы2 < “ 2.

Остается рассмотреть случай % = и*,

и2 = и2, когда первые

две

точки

стратегии Рп и

плана

Фп

совпадают,

и

сравнение

величин

J(u*),

J (и2) приведет к

отрезку

[а2,

Ь*2\,

содержащему

точки

и* и

« 2 с J

(и2) — min { J (и*),

J (и2)}. На поиск и*

на

этом отрезке в

на­

шем распоряжении остается

вычисление

значений функции

еще в

п — 1

(п > 2) точках,

включая точку и2.

Продолжением плана Ф„ на

отрезке

[а2,

Ь*2\ является план Ф»_1

на

этом

отрезке,

являющийся

единственной оптимальной последовательной

стратегией по

предполо­

жению индукции. Поэтому любое

отклонение

стратегии

Рп на [а2,

Ь2] от Фп приведет лишь к увеличению

гарантированной

погрешно­

сти:

8 А (Ря, b - а) > бА_! (Фп- и Ъ\ - а2) = 6

${Фп,Ь — а)

при Рп Ф Фп. Таким образом,

среди

стратегий Рп,

начинающихся с

выбора двух

точек их, и2£ [а, й] (s =

2),

наилучшей

является

план

Фибоначчи -Фп. В частности,

при /1 =

2

наилучшим будет план Ф2.

26

МИНИМИЗАЦИЯ

ФУНКЦИИ

одной

ПЕРЕМЕННОЙ

[Л'1. J

Наконец, перейдем к рассмотрению последовательных

стратегий

Рп,

начинающихся с выбора s

точек

ult и2........... us 6

[а,

b],

2 <

s

<

< п . В этом

случае,

сравнивая

значения

J

(tij),

, J (us) ,

мы

най­

дем отрезок

[as, 6S], содержащий точки «*

и us, a s<^us <^bs

с

вы­

численным

значением J (us) — min J (u {).

Согласно следствию 3.1 при

I < L < S

на классе Q* [а, b]

будем

любых, даже самых наилучших действиях

иметь bs — a s > — ■

,

где т = - у

при четном s,

т =

--- ~ ■■ при

нечетном s ( / n > l ) . В

то же самое время,

оказывается,. первые s ша­

гов

плана Фп приводят к

отрезку

[a*. b*s]

меньшей длины

as =

Fn-

(b — a) <

< b s

т +

1

Это вытекает из

следующих неравенств:

2Fn+2 >

(s +

1) F n s +з

при

s =

2т + 1,

3 <

s <

п,

( 1)

2Fn+2 >

(s +

2) F„_s.l3

при

s =

2in,

4 <

s <

n.

(2)

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

неравенства

(1)

при s = 3 и

(2)

при

s = 4

легко

установить с помощью индукции по п.

При всех s ^ 4 ,

оказывает­

ся,

верно более сильное неравенство (2),

вытекающее из монотон­

ного убывания

(s + 2 )

F„_s+3 при возрастании s

от s = 4 до s = ti:

(s +

2) F„_s+з =

(s +

2) Fn- s+2 +

(s + 2) Fn_ s+l >

(S + 2) F n- s + 2 + Fn—s_|_2 = (s + 3) F n- s +2.

При поиске точки u* на отрезке [as, bs] можно вычислить зна­

чения функции еще в п—s + 1

точках Зтого отрезка, включая точку

ds. Если даже точка й$ на [as,

bs] расположена очень удачно и до­

пускает применение оптимального

(в силу индукции) плана Ф п- з + i

на отрезке (as, bs] с участием точки й 3,

мы сможем получить лишь

бп.(Р„, b — a ) > bn-s+i (Фп- s+ь bs— a s) =

bs—as

>

bs ~

a s

Fn-s+3

Fn-,s+з

b — a = б*(Ф „, b — a).

/2+2

Таким образом, случай 2 <^s<Cn также

рассмотрен.

Ь — а

,

. Ь— а

п

. 6 — а

. „

— ------ <

8 <

— ------ ИЛИ

F n+l <

----------<

F n+2.

г п+*

* п+1

Е

точку и* минимума функции / (u )eQ *[a ,

Ь] с заданной точностью

s > 0 ,

произведя л наблюдений

значений

/(«),

не

превышает

e F п+2-

§

7. ОПТИМАЛЬНЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

ДЛЯ ЗАДАЧИ Б

Т е о р е м а 1. Для

задачи Б наименьшая возможная гаранти­

рованная на классе Q*[a, Ъ\погрешность равна

6„ (Ь— а) =

-b~ a- 1

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

2Fя+1

стратегии Р п при п~>\ не

существует.

Д о к а з а т е л ь с т в о . П р и л = 1

независимо

от

выбора

точки

их6 [а, Ь] (и даже не вычисляя

значения

J (их)) можем

положить

*

a -j- Ь

. *

* I

-

Ь — а

b — а

^

Ui = -----1—

с погрешностью |и — щ \- < ----------=

-----------. Очевидно,

2

2

2F2

любой

другой выбор «1

может

привести

лишь,

к большей

погреш­

ности. Теперь покажем,

что для

любого в,

0

<

е <

&~

а- , '

и

лк>

2Fn+1

бого л > 1 можно построить последовательный план Фл ,

для

кото­

рого

Ь — а

Ь — а

<

I 8.

< ? п (Фп, Ь — а)

2Еп+1

2Ел+1

План Фл будем строить следующим образом. На

отрезке [а, Ь] сна­

чала реализуем описанный при решении

задачи А фибоначчиев

план

Фп- 1 =

Фп—1 и получим'отрезок

[ал- ь

bn- i]

длины

28

МИНИМИЗАЦИЯ

ФУНКЦИИ

о д н о й

ПЕРЕМЕННОЙ

[,Гл. Т

После этого положим ип = un- i +

е, вычислим значение

J (ип)

и оп­

ределим

точку ип следующим образом:

— (an- i

+ ип), если

J (un_,) < J

(ип),

ип =

- у («л-1

+ Ьп~0, если J

(u„-i) >

J («„).

Принимая

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

и*, допустим

погрешность

■ип |< ип — «п-1

Ь— а . е

2F,л+г

Таким образом;

план Ф „,

гарантирующий погрешность,

как

угодно

близкую

к ——

-а-, построен при всех

п >

2 (рис. 3).

2F,п+1

(в-а))

Р и

с.

3

Далее докажем, что

б)? (b — а) =

inf бп (Р„,

Ь— а) =

ь ~ а . При всех я — 1, 2, . . .

,

рп

2Fn+l

а также убедимся в том,

что б„ (Рп, Ь— а) >

—— — для любой пос-

Рп при

2F„+1

ледовательной

стратегии

всех я > 2 . Как

было показано

выше, при п =

1 имеем 6f (b — а) =

—— —. При я =

2, очевидно,

6 l(P 2,

Ь - a )

=

Ъ— а

2Fs

4

для любой стратегии Р 2.

С другой стороны,

для любого е > 0

мож'

но указать стратегикГФг,

для которой

§ 7]

Оптимальный

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

поиск

для задачи Б

29

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

б! (b -

а) =

inf б! (Р2, b -

а)

=

2Fs

рг

причем нижняя грань

здесь

не

достигается.

Сделаем

индуктивное-

предположение:

пусть

6fc>

-

a

)

=

-

|

-

=

^ -

<

8

b ~

а )

^ k + i

для любой последовательной

стратегии Pk

при всех

k =

2,

3,

. . . „

га— 1, (га >

3),

и докажем, что тогда

б * ( й _ а ) ь = - А = ^ - < б Б ( Рл1 ь _ а)

ЛгП+1

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

Возьмем

произвольную

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

стратегию

Р п.

(га^ З). Согласно определению

4.1 стратегии

Р п вначале

выбира­

ются точки щ,

и2, ....

us^ [a, b],

(l s^s^ra) .

Как и в задаче А, не-

умаляя общности, можем считать, что

2 ^ 's ^ ra

(см.

доказатель­

ство теоремы 6.1).

Сначала рассмотрим случай s = 2 < r a ,

когда стратегия

Рп начи­

нается с выбора двух точек а <

их< м2 •< Ь.

Начальные точки пла­

на Фп- i на [га,

b] обозначим через

га| = а-Ь

Fn~1— (b — а),

и2 — а-\------ ^ — (Ь — а).

Бп+1

Fn+i

Возможно

их •< га* или га± >

щ.

Пусть

сначала

и1 <га*.

Тогда

в худ­

шем случае

«*€[га.,

Ь\,

причем

для

поиска га'

на

[ralt Ь]

можно-

вычислить значение

функции еще

в га —

1

точках

этого

отрезка,,

& —

^ ь — и\ _ Ь— а

2Fп

2Fп

2Fn+i

для

любых стратегий Pnt

начинающихся с выбора двух

точек rals.

ы2,

га < гах< ! га2^ Ь\ где

Аналогичные рассуждения

показы­