Ф.П. Васильев - Методы оптимизации (2002), страница 9

К недостаткам метода ломаных следует отнести то, что с увеличением числа шагов и растет требуемый объем памяти ЭВМ для хранения координат вершин ломаной р„(х). В $7 будет рассмотрен другой метод, по своей идее близкий к методу ломаных, но предъявляющий менее жесткие требования к объему памяти и более удобный для реализации на ЭВМ. Следует также отметить, что метод ломаных невозможно реализовать без знания постоянной Х из условии (1). На практике оценку для Х получают, вычисляя угловые коэффициенты некоторого числа хорд, соединяющих точки графика минимизируемой функции. Здесь полезно иметь в виду, что если и'<о<ш, то [/(ш) — /(и)]/(ш — и) < тах(]/(ш) — /(о)]/(ш — о); ]/(с) — /(и)|/(о — и)), (7) т.

е, при добавлении новой точки на отрезке [и, ш] появляется новая хорда с неменьшим угловым коэффициентом. 28 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ Для доказательства (7) нужно рассмотреть два случая, когда неравенство /(и) > (/(ю) — /(и))(и — и)/(ю — и) + /(и) (8) выполняется и когда оно не выполняется. Если /(ю) > /(и) и (8) выполняется, то (/(и) — /(и))/(и — и) > (/(ю) — /(и))/(ю — и) > О; если /(ю) > /(и) и'(8) не выполняется, то (/(ю) — /(и))/(ю — и) > (/(ю) -/(и))/(ю '— и) > О. Аналогично доказывается (7) в случае /(ю) < /(и). Пусть а» во<и, «...и„=Ь;обозначим Е = !пах [/(из) — /(из,)[ [и«в — из,[ '. Ясно, что Ех < Е. Пусть при каждом п« > 1 величина Ь„+1 вычисляется по точкам а = ю < ю, «...

ю„+, — — 6, полученным добавлением к точкам ио, и1 «..., и одной новой точки, Тогда согласно (7) имеем Л„< Ь„+1 < 7 (гп > 1). Это значит, что с возрастанием пь величины 7,„ все лучше и лучше приближают 7 снизу, Если шах [из — и [ — «О при О<1< пь — со, то !пп 4,„ =, Ь . Приведенные соображения могут помочь в полу«» «» чении оценки для Ь.

При определении 6 могут быть полезны теоремы 1,2. Следует заметить, что использование завышенной оценки для 7, ухудшает скорость сходимости метода ломаных, приводит к излишне большому количеству вычислений значений минимизируемой функции. Если же пользоваться заниженной оценкой для 7, то метод может привести к неправильному определению приближения минимального значения. Упражнения 1. Привести пример функции, которая удовлетворяет условию (1), но не является уннмо- дальной. 2.

Можно лн утверждать, что всякая уннмодальная на отрезке [а, Ь] функция удовлетворяет условию (1) на ]а, Ь]? Рассмотреть пример функции 7(х) = «««х на [О, 1], 3. Рассмотреть первые шесть шагоз метода ломаных для функции 7(х).= !]ха — 1! — 1! на отрезке [-2,2] прн различном выборе начальной точки хо. 4. Выяснить, как ведет себя метод ломаных прн минимизации функции /(х) ш 1 на отрезке [О, 1].

б. Пусть'у(х) <» о„х" +... +о1 х+оо — многочлен и-й степени на отрезке [о, Ь]; где 0 < о < Ь. Обоаначнм А+ = (4: 0 ( «( и, аз > О), А = (4. '0 ~( Г < ж аз < О), 7+(х) = г озх, у (х) = Л, ]»1]х . «ел««ел Доказать, что 7(х) = У+(х) — 7 (х), а е качестве постоянной о на условия (1) для функции 7(х) на ]о, Ь! можно лаять величину шахЯ(Ь) — г((о)1 Д(о) — Ь((Ь)!) [214). 9 7. Методы покрытий 1. Обозначим через (г(7) класс функций, удовлетворяющих условшо Липшица (6.!) на отоезке [а, 6[ с одной и той же для всех функций этого класса постояннои 6 > О. Дая функций / = /(х) е (е(7 ) будем рассматривать задачу'минимизации первого типа, когда ищется величина !п1 /(х).

Для решения этой задачи будем пользоваться методами р, »е!еь| которые заключаются в выборе точек х„..., х„(а < х, «... х„< Ь), вычи- $7 МЕТОДЫ ПОКРЫТИЙ 29 еленин значений функции /(х«),..., /(х„) и определении величины /(хь) = = гп!и /(х,.), принимаемой за приближение к /„. Возникает вопрос: как выбрать метод р„ = (х„ ...,х„), чтобы х,=а+Ь/2, х =х,+Ь, ..., х,,„=хз+Ь=х,+зЬ,..., х„, = х, + (п — 2)Ь, х„= ш!п(х« + (и — 1)Ь; 6), (2) где Ь = 2е/7 — шаг метода, а число п определяется условием х„, < Ь— — Ь/2 < х, +(и — 1)Ь.

Т е о р е м а 1. Метод равномерного перебора (2) решает задачу (1) на классе (г(Т ). Если Ь > 2е/й, то суи(ествует функция /(х) е (г(7 ), для которой метод (2) не решает задачу (1). Д о к а з а т е л ь с т в о. Пусть / = /(х) — произвольная функция из (г(Т ). С учетом неравенства (6.2) для любого х е [хз — Ь/2, хз + Ь/2) имеем /(х) >/(хз)-й[х — х [>/(хз) — ЕЬ/2> ппп /(хз) — е при всех а =1,..., й. 1<1<» Поскольку система отрезков [хз — Ь/2, хз + Ь/2[ (з = 1,..., и) покрывает весь отрезок [а, 6], т.

е. всякая точка х из [а, 6[ принадлежит одному из отрезков этой системы, то из предыдущего неравенства следует, что /(х) > гп]п /(хз) — е для всех х е [а, ь]. поэтому /2 > ппп /(хз) — е 1<««» * 1<«<» для любой функции / /(х) б (г(Ь), что равносильно неравенству (1). Если Ь > 2е/7, то, например, для функции /(х) = Ьх метод (2) дает ппп (Х х«) — Ьа=ЬЬ/2 > е. П 1<1<» 3. Метод равномерного перебора (2) относится к пассивным методам, когда точки х„..., х„задаются все одновременно до начала вычислений значений функции.

На классе (г(Т ) можно предложить такой же простой, но более эффективный последовательный метод перебора, когда выбор точки хз при каждом з' > 2 производится с учетом вычислений значения функции в предыдущих точках х„..., х о и задачу (1) удается решить, вообще говоря, за меньшее количество вычислений значений функции, чем методом (2). А именно, следуя [286[, положим х =а+ Ь/2, х.,1 — х,.+Ь+(/(х«) — Р)/Е«з =1«п — 2« х„= ппп(х„, + Ь + (/(х„,) — Е. 1)/Е; 6) где Ь = 2е/Т, Р,.

= ппп /(ху), а число и определяется условием х„, < Ь— 1 К 1' < « — Ь/2 < х„, + Ь + (/(х„1) — Р„1)/Ь. ппп /(хз)</„+е Ч/(х)Е Я(7), (1) 1<«<» где е > Π— заданная точность? Ниже будет изложено несколько методов решения поставленной задачи (1). В каждом из этих методов определенным образом строится некоторая система отрезков, покрывающих исходный отрезок [а, Ь[, и вычисляются значения функции в подходящим образом выбранных точках этих отрезков. Поэтому излагаемые ниже методы принято называть методами покрытий. 2.

Простейшим методом р» для решения задачи (1) может служить метод равномерного перебора, когда точки х„..., х„выбираются по правилу $1. МЕТОДЫ ПОКРЪ|ТИЙ 31 30 Гл. !. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ Упражнении 'фьб", Т е о р е м а 2. Метод последовательного перебора (3) решает задачу 1) на классе Я(5). оказ ательство. Пусть /=/(х) — произвольная функция из Я(Л ). С учетом неравенства (6 2) для всех х Е [х1, х1 + Ь/2+(/(х ) — Рй )/й ] имеем /(х) > /(х1) — Т (Ь/2+(/(х,) — Р1)/Т ) = Р1 —.5 Ь/2 > Р— г. Аналогично для всех х Е [х1 — Ь/2, х;] получим /(х) > /(хй) — ЬЬ/2 > Є— г.

Поскольку система отрезков [х, — Ь/2, х +Ь/2+(/(х<) — Рй)/й] (й = 1,..., п) покрывает весь отрезок [а, Ь[, то из предыдущих неравенств следует, что /(х) > Р— г при всех х е [а, ь]. тогда /, > Р„ — г при всех / = /(х) е (г(ь ), что равносильно неравенству (1). П * В худшем случае, когда, например, функция /(х) постоянна или монотонно убывает на [а, Ь] и, следовательно, Р, = ппп /(ху) = /(хй),метод (3) 1»У»1 превращается в метод (2), и для решения задачи (1) тогда потребуется Аг1 = (Ь вЂ” а)Ь/(2г) вычислений значений функции.

Б самом лучшем случае, когда /(х) = А + Ь (х — В), где А,  — постоянные и, следовательно, Рй = /(х,.), х,. = х, + (21 ' — 1)Ь (й = !,...,тй — 2), для решения задачи (1) понадобйтся всего АГ, =!+!од,(Ь вЂ” а)Х/(2г) вычислений значений функции. И вообще, если /(хй) > Рй при каком-либо й, то х,, — хй > Ь, и поэтому число и вычислений значений функции, необходимое для решения задачи (1), будет, вообще говоря, меньше )й/1 и больше Ж,. Заметим также, что метод (3) идейно примыкает к методу ломаных из ф 6, но метод (3) выгодно отличается простотой реализации и не требует большой машинной памяти. Недостатком метода (3), как и метода ломаных, является необходимость априорного знания постоянной Ь из условия (6.1). 4.

Следуя [590], изложим еще один вариант метода покрытий для решения задачи (1). Пусть зафиксирована сетка точек (2) с шагом Ь = = 2г/Ь. Выберем две произвольные точки в,, в, этой сетки, вычислим значения /(в1),/(ва) минимизируемой функции и положим Р1 = /(в1), Ра = = ш!п~Р1; /(в,)) = ш!и(/(в1), /(в.)), Имеются две возможности: либо Рв = = /(вт) < Р1, либо Ре = Р1 < /(ве), Если Ре < Р„то из Дальнейших Рассмотрений йсключаем точку в, вместе.

с теми точками ху сетки (2), для которых ]ху — в,[ < — '', не вычисляя значений /(ху). Если Рй = Р„то исключаем точку в, вместе с точками ху сетки (2), для которых !ху — ве~ < < ') '. Начальный шаг метода описан. Опишем общий шаг. Пусть в точках в„в„..., вй сетки (2) уже вычислены значения /(в1), /(вт),..., /(вй), НайдЕНа ВЕЛИЧИНа Рй хе Ш!П(Рй 1; /(ВВ)) =,Ш!и /(Вй); И ПуСтЬ В. та ИЗ тО- 1'»1» й я чек в„в,..., вй, в которой Р = /(ву ) = 'щ!и /(в,:). Далее возьмем любую точку вйй, сетки (2), которая на предыдущих шагах не исключалась и в которой еще не вычислялось значение функции /(х).

Вычислим /(в,'„1) и величину Р, =ш!п(Рй;/(вй„1)~=' . ппп /(в1), Имеются две возможной+! 1»1»й+1 сти: либо Рйй, =/(вй 1) < Рй, либо Рй+, =' Рй < /(вй„,). В первом случае, когда Рй+1 < Р,, из дальнейших РассмотРений исключим точкУ ву и вместе с нею те точки ху сетки (2), для которых !ху — ву [< + (4) Заметим, что некоторые из этих точек могли оказаться исключенными уже на предыдущих шагах. Для нас здесь важно лишь то, что среди исклю- ченных точек заведомо нет таких, в которых значение функции /(х) было бы меньше, чем Рй„1. В самом деле, пРежде всего /(ву ) = Рй > Рй „1. ДлЯ остальных исключенных точек х, имеем: /(ху) — Рй 1 = /(ху) — /(ву )+ Р,— — Рй „, > — Х, [ху — ву [+ Рй — Рй »1 > 0 в силУ (6.2) и (4).