Ф.П. Васильев - Методы оптимизации (1125241), страница 6
Текст из файла (страница 6)
тогда на следующем и-м шаге берется точка х„=- в„, + ь„, — л„ расположенная внутри [о„г> 6„~], симметрично точке Уь ~ относительно середины этого отрезка — отсюда происходит название методов. Затем вычйсляется значение /(з„) и сравни- ВастСЯ С /(У„,). ПУСТЬ ДЛЯ ОПРЕДЕЛЕННОСТИ У„Г < Вв (СЛУЧай ач < Уч ~ РаССМатРИВаЕтСЯ аналогично), Тогда при /(У„~) </(хь) полагается и„=и„ы Ь„= як, У =У П если же /(У 1)>/(з ) тои =У 1 Ь =Ь 1 у =в Еслиу ф(и +Ь )/2 топроцессможет быть продолжен дальше. Может оказаться, что У„= (а, + 6„)/2, — в этом случае процесс заканчивается; при необходимости на [а„, Ь„) моькио продолжать поиск минимума аналогичным методом, начиная с выбора новой начальйой точки У„~ (в„+ 6')/2. Из описания симметричного метода видно, что всякий симметричный метод полностью опре.
делается заданием отрезка [о, 6] и первой точки з1 (и < х1 < 6). Отсюда следует, что в качестве другой характеристики симметричного метода можно взять длины Аь отрезков [и„, Ь ] (и = 1, 2,...), где А1 —— Ь-а, Аз —— тах(6 — яб я1 — о). Очевьшно, А„е ~ >А /2 при всех и >1. Как видим, симметричные методы весьма просты и, пожалуй, даже изящны, Однако все эти методы страдают тем же недостатком, что и метод золотого сечения: погрешность, допущенная в задании первой точки сн приводит к быстрому накапливанию погрешностей на дальнейших шагах, и уже при не очень больших и результаты будут сильно отличаться от тех, которые могли бы получиться при точной реализации симметричного метода с точными исходными данными. Если симметричный метод таков, что для А„= ܄— и выполнено условие 20 Гл.
1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 21 $ б. ОБ ОПТИМАЛЬНЫХ МЕТОДАХ при некотором Аг > 1, то Ль„будут удовлетворять конечно-разностному уравнению (1) при и = 2,..., АГ, и исследование поведения погрешностей в этом случае может быть проведено так же, как это было сделано выше для метода золотого сечения, Чтобы избежать слишком быстрого роста погрешностей в симметричных методах со свойством (4), на каждом отрезке [а„, 6„] (и =- 2,..., АГ), содержащем точку х„с предыдущего шага, следующую точку х„+ ! нУжно опРеделЯть не по фоРмУле хч» ! — — хч+ 6„— хтю а лУчше пРинЯть за х„+ ! тУ нз точек х„+ т(Ь вЂ” о„), и„+(1 — т)(6 — и ) (т=(аз+ 6)/А!), которая наиболее удалена от х„.
Упражнения !. Найти наименьшее и, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза; в !О раз. 2. Написать конечно-разностные уравнения для длин а„отрезков [а„, Ь„], получаемых симметричным методом, для случая, когда на какнх-то шагах метода нарушается условие (4), 9 6. Об оптн!нальных методах 1. В тех случаях, когда вычисление значений функции связано со значительными затратами; большую ценность приобретают экономичные или, как их еще называют, оптимальные методы, позволягощие решить задачу минимизации с требуемой точностью на основе вычислений значений минимизируемой функции как можно в меньшем числе точек, а также тесно связанные с ними методы,'гарантирующие наилучшую точность при жестко заданном количестве вычислений значений минимизируемой функции.
В связи с этим возникают вопросы, что такое оптимальные методы, существуют ли такие методы, как их строить? Абсолютно наилучший метод, пригодный для минимизации всех функций, вряд ли существует, и на поставленные вопросы можно попытаться ответить лишь при определенных ограничениях на рассматриваемые методы, функции и постановки задач минимизации. Предположим, что нам задан некоторый класс функций Я, зафиксирована какая-либо постановка задачи минимизации функций из этого класса (например, задача первого или второго типа из $1) и указано множество методов Р, позволяющих решить поставленну!о задачу минимизации. Пусть сь(,/, р) — погрешность решения рассматриваемой задачи минимизации для функции /= /(ш) Е Ь/ с помощью метода р Е Р.
Ясно, что, минимизируя одним и тем же методом р различные функции из Я, мы будем получать, вообще говоря, различные погрешности: для некоторых «хороших» функций из Я эта погрешность может оказаться равной нулю, а для других «плохих» функций из (у погрешность может быть значительной. Имеет смысл считать метод р, Е Р лучше метода р Е Р, если погрешность метода р, даже для самых «плохих» (для р,) функций из (,Ь будет меньше погрешности метода ]ьь для «плохих» (для р,) функций из Я. В связи с этим представляется разумным ввести величину 6(р) = знр йь(/ р), выражающую собой /ео погрешность метода р при минимизации самой «плохой» (для р) функции из Я.
О п р ед е л е н и е 1. Величину 6(р) = зцр ьз(/ р) назовем гаранти/ео. рованной точностью метода р е Р на классе функций (у. Скажем, что метод р, Е Р лучше метода 76 Е Р на классе (у, если 6(р,) < б(р, ). Метод р„Е Р назовем оптималЬным методом на классе Ч, если б(р„) = = ]п[ б(р) = б(р.), а величину 6(р,) — наилучшей гарантированной точ- »«Р пастью методов Р на классе Я. Если для некоторого метода р, Е Р выполняется неравенство 6(р,) < 6(р„)+ г, то метод р, назовем г-оптимальным на классе (у. Вопросы существования оптимальных и г-оптимальных методов, возможности их построения для различных множеств методов Р, классов функций с/ и постановок задач минимизации, а также другие возможные подходы к проблеме выбора оптимальных методов изучались, например, в ]74; 140; 148; 193; 214; 218; 374; 523; 671; 681; 684; 704; 709; 755).
2. Здесь мы кратко остановимся на оптимальных методах решения задачи минимизации функций из класса О, состоящего из всех унимодальных функций на отрезке [и, Ь[. Ограничимся рассмотрением множества Р методов минимизации, использующих лишь значения функции, считая при этом, что число и вычислений значений минимизируемой функции заранее задано. Будем предполагать, что в описание каждого метода р„ из Р входит задание правила выбора точек х!>...,х из отрезка [а, Ь], вычисление значений /(х!),..ч /(х„) минимизируемой функции /(х) Е Гг, выделение из точек хо ....х„ такой точки х„, для которой /(х„) = ппп /(хз), и определение отрезка [о„, Ьч], где в качестве и„, Ь„ берутся ближай!<З<г шие слева или спРава к х„точки сРеДи х!,..., х„, и, Ь (возможности хг = и или хь = Ь не исключаются), Таким образом, применяя конкретный метод р е Р к конкретной функции /(х) е 17, в результате получаем отрезок [и„, 6„] и точку я в~а„, 6„] с вычисленным значением /(я„) = — ппп /(хг), Из определения унймодальной функции й построения отрезка [о, Ь„] следует !К !ьч неравенство /(х) )'/(я„) при всех хе [и, Ь]г, [о„, Ь ), так что А = 1п1 /(х) = 1и! /(х), Х„П]о„, 6„]~ И, (1) ачхКЬ „С*<Ь„ В качестве приближения для /, обычно берут величину /(х ), а в качестве приближения к множеству Х„можно взять любую точку х„иэ отрезка [оч, 6„] — на практике часто принимают х„= х„или х„= (а„+ 6„)/2.
Отрезок [о, 6 ] принято называть отрезком локализации минимума функции /(х) на отрезке [а, 6[. Из (1) следует что расстояние от любой точки х Е [о, 6„[ до множества Х, не превышает длины отрезка локализации 6„— о„: р(х„, Х,) = 1пГ [х„— х] < ܄— а„. (2) Величину А(/ р„) = ܄— х„можно принять за погрешность решения задачи минимизации функции /(х) е О методом р„е Р. Согласно (2), чем меньше погрешность А(/ р„), тем точнее будет определено приближейие х к Х„ и, следовательно, тем лучше метод р„. Для точного определения наилучшего или близкого к нему метода нам остается еще уточнить правило выбора точек х!,...,х„, в которых вычисляются значения минимизируемой функции.
Здесь принято различать два типа методов: пассивные методы и последовательные методы. Если все точки х!, ,х„ метода р выбираются одновременно до начала вычислений и а дальнейшем уже не меняются, то такои метод называют пассивным. Если в методе р„ точки хы ...,х выбираются последовательно отдельными порциями, причем при выборе каждой очередной порции учитыва!отея результаты предыдущих вычислений и проводится уточнение отрезка локализации минимума, то такой метод называется последовательным.
Примером пассивного метода является метод равномерного перебори, В этом методе точки х!, ., х„выбираются по правилу: хг = х! + «А (« = 1,..., п), где Ь > Π— шаг метода, ив заданная точка из [и, 6), х! — а < Ь (йапрймер, х! — — о или х! — — а+ Ь/2), и, кроме того, п)г < <Ь-х, <(.+ПА, ' Примерами последовательного метода служат методы деления отрезка пополам, золотого сечения. Пассивный метод является частным случаем последовательного метода, когда все'и точек выбираются сразу в первой же порции. Поэтому нетрудно понять, что последовательные методы, вообще говоря, обладают большей гибкостью и гораздо точнее пассивных методов. Однако отсюда не следует, что пассивные методы вовсе не находят применения. Такие методы 22 Гл.
1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ э 5. ОБ ОПТИМАЛЬНЫХ МЕТОДАХ весьма полезны, когда можно вести параллельные вычисления, используя, например, много- процессорные ЭВМ. В тех случаях, когда значеяия минимизируемой функции определяются из физического эксперимента, условия проведения таких экспериментов также могут сделать необходимым применение пассивных методов.
Таним образом, и-точечные (т. е, использующие вычисление значений функции и и точ- ках) последовательные и пассивные методы описаны, Если з определении 1 приняты что Я вЂ” класс унимодальных функций на отрезке [а, 6], Р = Ри — множество всех и-точечных последовательных (или пассивных) методов, 62(А ри) = 6 — аи — длина отрезка локализации минимума, полученного минимумом ри для функций / = /(х) я Я, то придем к определениям гарантированной точности, оптимальйого и г-оптимального последовательного (пассивного) метода для унимодальных функций. Кратко рассмотрим вопросы существования и построения оптимальных методов для таких функций.
3. Сначала остановимся на пассивных методах. Пусть р, = (х1,,.«хи) — какой-либо пассивный метод, а = то < х! « ... хи < 6 = хия м ПРименЯЯ его к какой-либо фУнкции /(х) и Я, получаем отрезок [хг 1,х;,1] локализации минимума этой функции, так что по.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
