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