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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 185

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§

*\

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

поиск

 

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] к увеличению погрешности

Поиск минимума, осуществляемый с помощью последователь- ,

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

^

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

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

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

 

причём для

любой

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

Р п нетрудно

 

указать,

функцию 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-оптимальной стратегий.

 

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

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

оптимальную (или е-оптимальную) стратегию Р п для минимиза­ ции функций из класса Q*[a, 6]. Пусть теперь на каком-то другом отрезке [с, d\ нам. нужно минимизировать функцию из Q*[c, d\. Возникает вопрос: нельзя ли стратегию Рп для отрезка [а, Ь] ис~

18

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

ПЕРЕМЕННОЙ

[Гл. 1

пользовать

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

(или е-оптимальной)

стра­

тегии поиска минимума на отрезке [с, d]? Для ответа на

этот воп­

рос возьмем линейное преобразование v = —— — (и — а) +

с, пере­

водящее отрезок [а, Ь] в [с, d], и каждой функции C (o )e Q *[c,d ] поставим в соответствие функцию

J ( u) = G ( - ^ ( a - a ) + c ) € Q* [a , &] .

Очевидно, при этом между классами функций Q*[a, b] и Q*{c, d] будет установлено взаимно-однозначное соответствие. Теперь ес­ тественно принять следующее

О п р е д е л е н и е 3. Применением стратегии Р п к отрезку [с, d] для минимизации функции G (o )e Q *[c, d] будем называть после­ довательный выбор точек

°i = \ ~ e (“i — °) + с 6 [ с. <*]'»' (i = l >2..........n)

по тем же правилам и в той же последовательности, по которым выбираются точки и ^ [ а , b\ ( t = l , 2, п) с соответствующими номерами при применении стратегии Рп для минимизации функ­

ции J(u ) = G ^ — — (и — а) +

на отрезке

[а, Ь\.

После принятия такого определения имеет смысл говорить о

стратегиях Р п безотносительно

к отрезку, на

котором ищется ми­

нимум строго квазив.ыпуклой функции. Нетрудно видеть, что для любой стратегии Р п и любого числа а > 0 имеют место равенства

бп(Рп, a (6 — а)) = ад„ (Рп, Ь — а), 6* (а (6 — а)) = а б п {Ь — а).

Аналогичным свойством однородности по переменной Ь— а

обла­

дают также величины 8п(Рп,Ь — а), 8п{Ь — а) для задачи

Б: чем

меньше длина отрезка, тем лучше гарантированная точность в оп­ ределении точки минимума с помощью одной и той же страте­ гии Р п.

Естественно распространить определение 3 и на пассивные стратегии. Тогда величины

Ln {Рп>b — а), Ьп {Ь — а), Ьъп {Рп, Ь - а ), £ ( Ь - а )

будут обладать упомянутым выше свойством однородности по переменной b— а.

§ 5. МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ

Простейшим примером последовательной стратегии является метод деления отрезка пополам [230]. Суть этого метода проста.

§ 5]

Метод деления отрезка пополам

1&

Пусть / (M )eQ :t[a, b], а «* — точка минимума J (и) на [а, Ь].

Возь­

мем точки

 

 

% = — (а + b — б), и2 = — (а -Ь b -{- б) = а -\-Ь — иг,

 

где 6 =

const, 0 < б < 6 — а. Величина б может характеризовать по­

грешность измерений величины и и ограничена снизу возможно­ стями измерительного прибора. Точки щ, и2 расположены симмет­ рично на отрезке [а, Ь], при ма­

лых б делят

[а, Ь] почти попо­

Ли)

 

 

л а м — отсюда

название '

метода.

 

 

 

Далее,

вычисляем

и сравниваем

 

 

 

значения

J(u i), J(u 2).

Если

 

 

 

J (и\) ^ . J (и2) ,

то

полагаем

 

 

 

ai = a,

bi = u2;

если

же

J ( u i) >

 

 

 

>

J ( u2) , to a\ = ux,bi — b

(рис. 1).

 

 

 

В

результате

получим

отрезок

 

 

 

\аи Ь{\,

содержащий точку и*

 

 

 

минимума функции /(и) на U,

 

 

 

причем

 

 

 

 

 

 

 

 

 

 

 

 

 

Ъ\

—

Ь — а + б

 

 

 

 

 

 

 

 

 

 

 

Если отрезок [а&_], b^-i], содержащий

точку и*,

уже изве­

стен и

 

 

 

 

 

 

 

 

 

 

 

bk—1 — flfc—1

 

1

) б , (k >

2)

 

 

 

 

2*-i

то дальше на этом отрезке поступаем аналогичным образом. А имен­

но,

берем точки

 

 

,,

__ak-i 4 - bk-1 — б

,, __ a k -i + b k -1 + б

+ bk—i — u2k—u

«2А-1 ------------- 2---------

U2 k -------------------------------------- = O-k-

расположенные симметрично на отрезке [afc_i, 6fc_i], и вычислим зна­

чения J

(u2k—i), J (u2k). Если J (u2k-i) < J (u2k), то

полагаем ak — a-k-x,

bk — u2k> если J ( « 2ft—i) > J ( u 2k), to

ak = u2k—u

bk = bk-\. Отрезок

[aft> M

содержит точку и' минимума;

его длина

 

b — а

6* — a k

2*

Допустим, что требуемое число вычислений п — 2k значений функций мы провели и остановились на отрезке [aft, bk]. Тогда в

20 МИНИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ [Гл. 1

качестве приближения для точки минимума ы* в задаче Б примем

и п = - j- (ak + bk), допустив при этом погрешность

+ б -

В задаче А примем

Un =

u2k- l при / (u2k- 1) <

J (игк),

ип =

игк при J («2fc-l) > J («2ft)

с уже известным значением

/ («„);

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

ность

 

 

 

 

 

!«* — «.*| < 6 *— а* <

ь ~з.£.. + б.

Зная

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

в определении и* при 6-кратном де­

лении отрезка пополам, легко подсчитать число п = 26 вычислений значений функции для получения и* с нужной точностью е,

£ > б > 0 .

Заметим, если для функции J(u )^ .Q [a,b ] нижняя грань J (и) на U не достигается, то при 5—>-0, 6-»-оо описанный метод позволя­ ет строить минимизирующую последовательность — для этого до­

статочно,

например, взять упомянутые выше величины ип, п =

= 2 6 ( 6 =

1,2, ...). Метод деления отрезка пополам может быть ис­

пользован для поиска минимума произвольной непрерывной функ­

ции на отрезке [а, b], однако в результате придем, вообще говоря,

к точке локального минимума.

|и* — ипI

Сравнивая полученные выше оценки погрешности

для функций из класса Q*[a, 6] с оценками из теорем 3.1

и 3.3, не­

трудно убедиться в преимуществе метода деления отрезка пополам по сравнению с пассивным поиском уже при небольших п — 21г. Однако существуют последовательные' стратегии, которые лучше метода деления отрезка пополам.

§ 6. ОПТИМАЛЬНЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ДЛЯ ЗАДАЧИ А

 

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

дачи

А связана со знаменитыми числами

Фибоначчи, и поэтому

\, эту

стратегию будем называть стратегией,

или планом, Фибо-

у начни.

Смотрите также файлы