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

Однако все эти методы страдают тем же недостатком, что и метод золотого сечения: погрешность, допущенная в задании первой точки хп приводит к быстрому накапливанию погрешностей на дальнейших шагах, и уже при не очень больших и результаты будут сильно отличаться от тех, которые могли бы получиться при точной реализации симметричного метода с точными исходными данными. Если симметричный метод таков, что для А„= ܄— а„выполнено условие $ 5. ОБ ОПТИМАЛЬНЫХ МЕТОДАХ 20 Гл. 1, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 21 при некотором Аг > 1, то А будут удовлетворять конечно-раэностному уравнению (!) при и = 2,..., Аг, и исследование поведения погрешностей в этом случае может быть проведено так же, как это было сделано выше для метода золотого сечения. Чтобы избежать слишком быстрого раста погрешностей в симметричных методах со свойством (4), на каждом отрезке [а„, 6„] (и = 2,..., Аг), содержащем точку х„с предыдущего шага, следующую тачку х„ нужно определять не по формуле х„«! — — а„ц- 6 — в„, а лучше принять за хь «! ту иэ точек а„+ т(Ь вЂ” а ), а„+(! — т)(6„— а„) (т=(пз+ б)/Сь!), котоРаа наиболее Удалена от И„.

Упражнения 1. Найти наименьшее и, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза, "в 1О раз. 2. Написать конечно-равностные уравнения для длин Сг„ отрезков [а„, Ь„], получаемых симметричным методом, для случая, когда на каких-то шагах метода нарушается условие (4). 9 6.

Об оптимальных методах 1. В тех случаях, когда вычисление значений функции связано со значительными затратами, большую ценность приобретают экономичные или, как нх еще называют, оптимальные методы, позволяющие решить задачу минимизации с требуемой точностью на основе вычислений значений минимизируемой функции как можно в меньшем числе точек, а также тесно связанные с ними методы, гарантиру!ощие наилучшую точность при жестко заданном количестве вычислении значений минимизируемой функции. В связи с этим возникают вопросы, что такое оптимальные методы, существуют ли такие методы, как их строить? Абсолютно наилучший метод, пригодный для минимизации всех функций, вряд ли существует, и на поставленные вопросы можно попытаться ответить лишь прн определенных ограничениях на рассматриваемые методы, функции и постановки задач минимизации.

Предположим, что нам задан некоторый класс функций Я, зафиксирована какая-либо постановка задачи минимизации функций из этого класса (например, задача первого или второго типа из $1) и указано множество методов Р, позволяющих решить поставленную задачу минимизации. Пусть дь(7, р) — погрешность решения рассматриваемой задачи минимизации для функции / = /(ю) Е Я с помощью метода р Е Р. Ясно, что, минимизируя одним и тем же методом р различные функции нз Я, мы будем получать, вообще говоря, различные погрешности: для некоторых «хороших» функций из Я эта погрешность может оказаться равной нулю, а для других «плохих» функций из Я погрешность может быть значительной. Имеет смысл считать метод р, Е Р лучше метода рэ Е Р, если погрешность метода р, даже для самых «плохих» (для р,) функций из О будет меньше погрешности метода рз для «плохих» (для р,) функций нз Я.

В связи с этим представляется разумным ввести величину б(р) = зпр /ь(/', р), выражающую собой еео погрешность метода р при минимизации самой «плохой» (для р) функции из („Ь. Определение 1. Величину б(р) = знр ьь(7", р) назовем гаранти- 1«О рованной точностью метода р е Р на классе функций Я. Скажем, что метод р, Е Р лучше метода р Е Р на классе (,], если б(р,) ( б(р,), Метод р, Е Р назовем оптимальным методом на классе (г, если б(р,) = = !и[ б(р) = б(р,), а величину б(р.) — наилучшей гарантированной точрер настою методов Р на классе Я.

Если для некоторого метода р, е Р выполняется неравенство б(р,) ( б(р,)+ г, то метод р, назовем е-оптимальным на классе Я. Вопросы существования оптимальных и г-оптимальных методов, возможности их построения для различных множеств методов Р, классов функций Я и постановок задач минимизации, а также другие возможные подходы к проблеме выбора оптимальных методов изучались, например, в [74; 140; 148; 193; 214; 218; 374; 523; 671; 681; 684; 704; 709; 755]. 2. Здесь мы кратко остановимся на оптимальных методах решения задачи минимизации функций из класса О, состоящего из всех унимодальных функций на отрезке [а, Ь]. Ограничимся рассмотрением множества Р методов минимизации, использующих лишь значения функции, считая при этом, что число и вычислений значений минимизируемой функции заранее задано. Будем предполагать, что в описание на>якого метода р из Р входит задание правила выбора точек х!,...,х из отрезка [а, Ь], вычисление значений /(х!),..., /(хи) минимизируемой функции /(х) Е г/, выделение из точек х!,...,х„ такой точки х„, для которой /(х„) = ппп /(х,), и определение отрезка [а„, Ьа], где в качестве а„, 6„ берутся ближай!<Ь<ч шие слева или справа к х„точки среди х!,..., х„, а, 6 (возможности хг = а или х! = 6 не исключаются).

таким образом, применяя конкретный метод р е Р к конкретной функции /(х) е г?, в результате получаем отрезок [а„, Ь„] и точку х е ~а„, 6„[ с вычисленным значением /(х„) = ппп /(хг). Из определения унймодальной функцйи й построения отрезка [а„,6„] следует неравенство /(х) > '/(х„) при всех х в [а, Ь]г,[а„, Ь ], так что !п1 /(х) = !п1 /(х), Х, п[а„Ь„] Р' и!. (1) <*<Ь а„крСЬ„ Б качестве приближения для /, обычно берут величину /(х ), а в качестве приблюкения к множеству Х, можно взять любую точку х„из отревка [а„,Ъ„] — на практике часто принимают х„= я„или х„= (а„+ Ь„)/2. Отрезок [а„, Ь ] принято называть ошрезком локализации минимума функции /(х) на отрезке [а, Ь]. Из (1) следует что расстояние от любой точки х„е [а, 6 [ до множества Х, не превышает длины отрезка локализации Ь вЂ” а„: р(хз, Х,) = 1п1 ]х„— х] < ܄— ая. (2) е Величину А(/ р„) = ܄— а можно принять за погрешность решения задачи минимизации функции /(х) е О методом р„е Р.

согласно (2), чем меньше погрешность А(й р„), тем точнее будет определено приближейие х„ к Х, и, следовательно, тем лучше метод Р„. Для точного определения наилучшего или близкого к нему метода нам остается еще уточнить правило выбора точек х!,...,х , в которых вычисляются значения минимизируемой функции. Здесь принято различать два типа методов: пассивные методы и последовательные методы. Если все точки х!, ,х„ метода р„ выбираются одновременно до начала вычислений и в дальнейшем уже не меня1отся, то такой метод называют пассивным.

Если в методе р„точки х!,..., х„выбираются последовательно отдельными порциями, причем при выборе каждой очередной порции учитываются результаты предыдущих вычислений и проводится уточнение отрезка локализации минимума, то такой метод называется лосладоаашзл»н»гм. Г1рнмером пассивного метода является метод равномерного перебора. В этом методе точки х!,..., х„выбираются по правилу: х,. = х!+46 (« = 1, „и), где Ь >Π— шаг метода, х!— заданная точка из [а, Ь], х! — а( 6 (йапрймер, х! — — а или х! —— а+ Ь/2), и, кроме того, пь < <Ь-., к( +1)Ь.' Примерами последовательного метода служат методы деления отрезка пополам, золотого сечения.

Пассивный метод является частным случаем последовательного метода, когда все и точек выбираются сразу в первой вге порции. Поэтому нетрудно понять, что последовательные методы, вообще говоря, обладают большей гибкостью и гораздо точнее пассивных методов, Однако отсюда не следует, что пассивные методы вовсе не находят применения.

Такие методы 22 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 23 $5. ОБ ОПТИМАЛЬНЫХ МЕТОДАХ весьма полезны, когда можно вести параллельные вычисления, используя, например, много- процессорные ЭВМ. В тех случаях, когда значения минимизируемой функции определяются из физического эксперимента, условия проведения таких экспериментов также могут сделать необходимым применение пассивных методов.