Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 17
Текст из файла (страница 17)
Допустим, что при поиске минимума Ф„,(и, ие) на [из+ а, Ь] такая точка эо не нашлась, и мы пришли к некоторой точке локального минимума юо(но+ а < юо < Ь) со значением Ф (юо, ио) >О, причем Ф (и, иа) >О при всех и гн [из+ и, и"э]. Здесь имшотсн две возможности: либо Ф„(ю„иа) > О, либо Ф„,(юь и,) = = О. Если Ф (юм ио) > О, то, пользуясь свойством 3, увеличиваем ьч так, чтобы соотвегствуюнгая функции гэ„,(и, ио) в точке юэ не достигала локального минимума, и продолвгаем поиск минимума на отрезке [юи Ь]. Заметим, что прп минимизации функции грм(и, ие), соответствующей новому значению т, иет необходимости возвращаться к отрезку [из+ а, ю,], так как неРавенство Ф„,(и, ио) > О (и ш [из+ а, и ]), Установленное дла какого-то значснпя ое останется верным при всех т = 1, 2,, и свидетельствует об отсутствви па [и, + а, ю] искомой точки гь Рассмотрим случай Ф„(юэ, иэ) = О. Согласно свойству ! функция 1(и) также будет достигать локального минимума в точно ю, со значением 1(им) = 1(иэ).
Поскольку локальные минимумы функции 1(и) строгие, то можем выбрать а > О столь малым, чтобы 1(и) > 1(ю,) и, следовательно, Ф (и, иэ) > О при юа < и < и'а+ а. Увеличивая при необходимости ю, согласно своиству 3 можно сделать Ф (ю + и, и ) < О и затем перейти к о ' о минимизации соответствующей функции гг (и, ио) на отрезке [юэ+ а, Ь].
Можно ожидать, что продолжая этот процесс далыпе, либо мы найдем искомУю точкУ ги ДлЯ котоРой Ф (он иэ) < О, либо, конечное число Раз увеличивая п~ и выбирая а > О, дооеремся до точки Ь и выясним, что !Э„(и, иэ) > О при всех и (ио < и < Ь). В последнем случае переходим к отрезку [а, ио] н на нем аналогичным образом ищем точку э, со свойством Ф (эм из) < О. Если и на отрозве [а, иэ] такая точка го не найдется, то это бУДет означать, что Ф (и, иэ) > О пРи и гн [а, Ь] (и Ф иэ), т. е. согласно свойству ! точка иэ есть точка глобального минимума функции 1(и) на [а, Ь]. С другой стороны, если иа пе является точяой глобалыюго минимума, то в силу того же свойства ! существует точка э„для которой (ээ, и,) < О, и можно надеяться, что описанным выше способом удастся найти точку и реализовать изло'кенпую в начале параграфа схему поиска глобального минимума функции 1(и) на [а, Ь].
6 11! ДРУГОЙ 31ЕТОД НОИСКА ГЛОБАЛЬНОГО ЫПНИЫУ31А 65 Следует заметптгч что для более строгого обосновании предложенного способа поиска точки п, ггадо бы еще доказать, что поиск минимума ори(и, и,) на [ио, Ь) и [а, ио) всегда удастся вакончить за конечное число изменений величин ш, и. Интересно также исследовать, как влияют погрешности, неизбежные при определении точек локального минимума рассматриваемых функций, па весь процесс поиска глобального минимума.
Эти вопросы, по-видимому, пока еще должным образом не изучены. При практическом использовании описанного метода обычно задают некоторое достаточно большое натуральное число М и ограничиваются рассмотрением функций грп(и, ио) лишь при т = 1, ..., М, Численные эксперименты наказывают, что удачный выбор М и точность определения точек локального минимума рассматриваомых функций обеспечивают достаточно высокую эффективность этого метода [90]. 3.
Применим описанный метод поиска глобального минимума к задаче зп минимизации многочленов х(и) = р (и) = ~ агиг степени 2п, где все коо=о эффицненты аг — действительные числа, старший коэффициент аоо ) О. По. скольку !!ш р „(и) = оо и ро (и) — непрерывная функция, то мно. !и! нсество М(о) = (и; и оп К, ро (и) ( ро (и)) непусто, ограничено и аамкнуто при любом фиксированном и. Кроме того, очевидно ш! р,„(и) = имк гп! р „(и) = Уо. Поэтому, применяя теорему 1И к функции ро„(и) на ипш1о) множестве М(о), получаем, что о'о ) — оо и множество(го точек минимума р,„(и) на К непусто.
Более того, так как производная р „(и), нвляется многочленом степени 2п — 1, то она может иметь не более 2п — 1 действительных корней, и ро„(и) на К может иметь не более и — 1 точек локального максимума п не более п точек локального минимума. Поиск глобального минимума функции ро (и) на К можно осуществить следующим образом. Отправляясь от произвольной начальной точки, с помощью какого-либо локального метода минимизации, например, метода параоол, находим точку ио локального минимума ро„(и). В этой точке р (и ) = 0 и справедливо представление р, (и) = р (и ) + р, (и ) (и — и )з/2! + ...
... + ре1~™П(и ) (и — ио)з" 1/(2п — 1)!+а„(и — и )тп. По аналогии с (2) введем функцию йо(и, ио) = (ро (и) — ро„(ио))((и — ио)' = Ро„Пи, ио). Из предыдущего представления следует, что ро о(и, ио) — многочлен степени 2п — 2 со старшим коэффициентом ао ) О. Поскольку ро (и)— ро (ио) = (и — ио) оров о(и, ио) при всех и ш К, то ясно, что точка ио будет точкой глобального минимума ро„(и) на К тогда и только тогда, когда гп1 р „(и, и ) ~ )О. Это означает, что исходная задача минимизации мно=к гочлена степени 2п сволась к задаче минимизации многочлена ро„о(и, и,) меньшей степени 2п — 2, которую в свою очередь можно аналогично решать последовательным сведением к задаче минимизации на К многочленов меныпих степеней 2п — 4, 2п — 6, ..., 2 с одним п тем же старшим коэффициентом аоо ) О.
Остается заметить, что для многочлона второй степени ро(и) = Ьои'+ Ь,и+ Ь, (Ьо = ао„) 0) точка минимума К находится по известной формуле ио = — Ь1Я2Ь ). Бели при поиске минимума ро„о(и, ио) на К будет найдена точка о„ для которой роо,(и„ио) ( О, то сразу же возвращаемся к исходной задаче минимизации ро (и): отправляясь от начальной точки о„каким-либо ло- бб 31етоды ыпыньн1злцин Функции Однои пегеменнон )Гл. 1 к" льным методом находам следугощую точку и1 локального ьпзнвмума р,„(и) со звачеипев рг (и~) ( рз„(ге) < рм,(ие) в затем с вовой тс*п;ой и, 11ОСтУпасп таК жЕ, Ках С ПРЕДЫДУЩЕЙ тОЧКОВ иь П т. Д. ЭтОт ПРОЦОСС ПЕРЕ- хода от одной точки и; ~ локального мвнвмума к следугощей точке из с более глубоквм локальным минимумом закончвтсл не более чем через и шагов обнаружением того, что 1п1 ртв,(и, иг) Ъ О.
ьык $13. О методе стохастической аппроксимации Выше предполагалось, что значение минимизируемой функции пли ее производной в каждой точке вычисляется точно. Между тем из-эа погрешностей применяемого здесь метода и ошибок округления значения дая е простейших элементарных функций могут быть вычислены, вообще говоря, лшпь приближенно.
Поэтому при поиске минимума вместо точных значений функции У(и) мы будем иметь дело с приблиягенными значениями з(и) с некоторой погрешностью )з(и) — з (и)) ~ е. В этом случае уверенно можно различать значения функции в двух точках н выяснить, какое пз них меньше, только тогда, когда разность этих значений больше 2е. Понятно, что это обстоятельство должно быть учтено при использовании описанных выше методов минимизации. Весьма усложняется решение задачи минимизации в тех случаях, когда па значения функции в каждой точке накладываются случайные ошибки или, как говорят, помехи. Такая ситуация, например, имеет место, если значения функции получаются в результате измерений какой-либо физической величины.
В том случае, когда помехи являются случайной величиной и обладают определеннымп вероятностными характеристиками, для поиска минимума целесообразно использовать метод стохастической аппроксимации. Опишем один из вариантов этого метода. Будем предполагать, что значения фуннции з(и) могут быть измерены в любой фиксированной точке иш К, причем результаты измерений не содержат систематических ошибок. Тогда для поиска минимума функции У(и) на К может быть использован следующий итерационный метод: ивы = и„— а„(г(и„+ с„) — г(и„— с„) )lс„п = 1, 2, ..., (1) где последовательности (а„), (с„) заданы п удовлетворяют ус- ловиям а )О, с )О, п=1 2, ..., Пша„= Птс„=0, (2) а„= со, и=1 Например, здесь можно взять а„= 1!и, с„=1(пн' (и= 1, 2, ...), е~и о ъгатодк стохастическои лппгоксныацпи 67 Следует заметить, что в тех случаях, когда слева от точки минимума график функции имеет крутой спуск, справа — крутой подъем, а на остальных участках функция з(и) изменяется медленно, сходимость метода (1) может ухудшаться.
В самом деле, на пологих участках разность г(и„+ с„) — з(и„— с„) может стать очень малой, и тогда шаги поиска ~и„~, — и„~ будут малыми, а на крутых участках, наоборот, шаги поиска могут стать очень большими. В результате значительная часть времени на поиск может быть затрачена на чрезмерно медленные спуски на пологих участках и последующие большие скачки через точку минимума с попаданием на другой пологий участок. В таких ситуациях моя~ет оказаться полезным следующий вариант метода стохастической аппроксимации: и„э, = и„— а„в1яп(з(и„+ с„) — г(и„— с„) ), и = 1, 2, ..., (3) где последовательности (а„), (с„) по-прежнему удовлетворяют условиям (2), е~8па — знак числа а, т. е. з1япа= 1 при а) О, в1япа= — 1 при а(0, з!яп0=0.
Сходимость метода (3) можно ускорить, если длину шага а„менять лишь при изменении знака з(и„+ с„) — з(и„— с„), сохраняя а„постоянным в остальных случаях. При некоторых предполоя ениях относительно функции у(и) и вероятностных характеристик случайной величины з(и) мозкно доказать сходпмость по вероятности последовательности (и„), определяемой формулами (1) пли (3), к точке глобального минимума У(и) на В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
