Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 97
Текст из файла (страница 97)
Зто значит, что для поиска минимального корня уравнения (5) и в этом случае может быть применен описанный выше метод (20) — (24) или ого модификация (20), (29) — (31). Только условие (25) адесь нужно заменить условием В,~2Тю т=1,2, (33) МЕТОД НАГРУЖЕННЫХ ФУНКЦИЙ 409 У 1з) последовательность (Г„), определяемая методом (20) — (24), сходится к сь при любозз выборе тв( — оо < т < ть). 11ри ослом, если вв < со, то ите- рации (20) при каждом» >-1 будут заканчиваться за конечное число шаеов выполнением условий (21); случай (23) возможен лишь при те со. Доказательство проводится дословно так же, как доказательство теоре- мы 5.
Нужно лишь неравенство (27), полученное в предположении монотон- ности р(т) и условия (25), заменить следующим неравенством, вытекающим из условий (15), (19), (26), (33): Р (т» 1+г) = [Р ("» ььг) Р (т» ььг)] + [Р (т~ ~ь~) Р (т~)[ < < 7»+ С (т» ьь г — "е) ~( 27» < О». Нетрудно также показать, что при выполнении условий теоремы 6 пс следовательность (т,), полученная методом (20), (29) — (30), сходится к шш(тз; Т). Приведем пример, показывающий, что условие (33) в общем случае не может быть ослаблено. Пример 10. Пусть 1(и) ьиО, У вЂ” проиавольное непустое множество вида (1), Тогда Ф(и, т) = [т) + МР(и), и» Уе и р(т) =)1); те =0= 1». Пусть р,(т) = )Ц + 7, (» = 1, 2, ...).
Предположим, что условие (ЗЗ) нарушено, т. е. О, < 27,. Возьмем начальное приближение зз = т,е < < ш!и ( 1„— О„; 0). Тогда Р,(юс) = ) с,с[ + 7 = — то+» > О,. Далее, си = = вю+ р»(т'е) = "1. > О, и снова р„(еы) = Р,(7,) = 27, > О,. Отсюда с уче- том монотонности Р„(г) пРи с>0 имеем Р„(П > Р„(тп) > О, длЯ всех 1 > Ыь Это значит, что Р (т ь) > О, для всех й =О, 1, ...
— реализовался случай (23), и искомый минимальный корень т = 0 уравнения (5) вдесь не будет найден, Полезно заметитгь что при описании методов (17), (20) — (24) и (20), (29) — (31), а также при формулировке и доказательстве теорем 4 — 6 никак не лспольаовался тот факт, что функция р(г) получена из (4) и как-то свя- вана с задачей (1),с методом нагруженных функций. Это значит,что описан- ные методы могут быть использованы длл поиска минимального корня уравнения (5) для любой неотрицательной функции р(с), удовлетворягощей условию (15) п приближенно заданной посредством условий (19).
По поводу метода нагруженных функций см., например, [8, 21, 82, 85, 257). Упражнения. 1 Найти минимальное решение уравнения (5), где функции Ф(и, 1), Р(г) олределлются из (2), (3), (6), (13) или (32), и про- верить условие те = 1з для задачи: 1(и) - ш1; и ем У = (и» Е': и» Уе, у(и) <О), гдо а) 1(и) = агсьй и, у(и) из — 4, у(и) = (из — 4)(ие+ 1) ', у(и) = и, у(и) =и(из+1) ', у(и) =и', Уз=(и»Е'.
и>1), Уе=(и»Е'. и>0), Уз = Е', б) 1(и) = и айпи, у(и) = и' — 1; у(и) = (из — 1) (ие+ 1) ', у(и) =(из — 1)е и; Уь=(и»Е'. и>0); в) 1(и) — произвольная функция, а У = Уе = Е', г) 1(и) = 1 при и (1, 1(и) = и-' при и > 1; у(и) = и — 1, у(и) = =(и — 2)(из+1) ', у(и)=е ", Уе=(иемЕ'. и>0) или Уз=Е; д) 1(и) ~1, у(и) =и, у(и) =из+1, у(и)=е и (и +1), у(и)= =изе ь~ Уь=Е',Уь=(и»Е'.и>0). 2.
Найти функцию р(Г) для задачи 1(и) -ь[п1; и» У = (и» Е' = У,: у(и) = [и) — 1 < О), берн за основу функции Ф(и, г) из (13) и (32), срав- нить результаты с примером 2. 3. Показать, что если функция р(т) построена с помощью функций (2) или (6) прп рс > 1, то условия (14), (15), вообще говоря, не будут иметь места (ни с какой константой Ь). Указание: рассмотреть задачу (1) при 1(и) 1, У Уь 410 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ ГГЛ, В 4, Указать такой способ аадапия множества УУ из примера 5, чтобы за- дача иыела согласованную постановку на (Уо = Е'.
Рассмотреть возможно- сти Х(з) = (и( — 1, д(з) = зз — 1, З(и) = о " (й — 1) (воспользуйтесь тео- ремой 2). 5, Выяснить геометрический смысл методов (17), (20) — (24) и (20), (29) — (31), а также геометрический смысл условий (25), (ЗЗ). 6, Проверить, будут ли функции Ф(з, г) иа (2), (6), (13), (32), а также соответствующая функция р(г) из (4) выпуклы, если исходная аадача (1) выпукла, 7. Пусть в задаче (1) Уо ) — о», УУо Ф й), и эта задача имеет согла- сованную постановку на множестве УУо.
пусть последовательность (1о) по- строена методом (17), а последовательность (оо) определена условиями: во ш (Уо р(1о) =Ф(зь го) ()о = О 1, ...). 51ожно ли ожидать, что (иь)-ь -и П ? Приведите примеры. 8. Пусть функция Лагранжа задачи (1) имеет седловую точку (ио, Л*) ои(У х Ло. Показать, что та же точка (зо, Л*) является сед- ловой точкой функции Лагранжа для задачи шах (У(з) — г; О)-иш1; и <и 0 при всех с<У». Выяснить связь между множествами точек минимума последней задачи и задачи (1).
9. Для задачи (1) ввести функцию Ф,(з, Г) =Ежах(У(з); Г) +МР(з), зш(Уо, где Р(и) ваята из (3), Х,) О, ))У > О, и положить р (Ц = 1п( Ф (и, 1). ими Покааать, что У = р (У ). Можно ли утверждать, что У будет минималь- ным корнем уравнения р~(с) — г = 07 Пользуясь равенством шах (У(з), г) = шах (У(л) — ц О) + д установить связь между функциями Ф~(з, Ю), р~(г) и функциями Ф(о, с), р(1) иа (2), (13). 10.
для задачи у(з) -«(п1; за П = (и ои Гуо, Х~(и) < О, ..., д (и) <» О) ввости функцию 6(ю, и) = шах (У(ю) — У(о); Кь(з') ° ., Хи(м)) или С(ю, и) = (У(ю) — У(и))йз(ю)... З (ю) переменных и, го он (го и рассмот реть итерационный процесс 0(иь+г, ид) = (п( б(ю, и ); исследовать его ижпо сходимость (метод центров, [159) ). й 17. О методе случайного поиска Наряду с описанными выпге методами минимизации функций переменных существует большая группа методов поиска минимума, объединенных под названием метода случайного поиска. Метод случайного поиска„ в отличие от ранее рассмотренных методов, характеризуется намеренным введениеы элемента случайности в алгоритм поиска.
Многие варианты метода случайного поиска сводятся к построению последовательности (и„) по правилу: и,о,=из-)-ссД, Уг О, 1, ..., (1) гДе ао — некотоРаЯ положительнаЯ величина 9 (9', ..., 9")— какая-либо реализация и-мерной случайной величины $ с известным законом распределения. Например, координаты $' случайного вектора 9 могут представлять независимые случайные ве- О МЕТОДЕ СЛУЧАЙНОГО ПОИСКА З»71 411 личины, распределенные равномерно на отрезке [-1, 1]. Как видим, метод случайного поиска минимума функции и переменных предполагает наличие датчика (или генератора) случайных чисел, обращаясь к которому, в любой нужный момент можно получить какую-либо реализацию и-мерного случайного вектора $ с заданным законом распределения. Такие датчики, оформленные в виде стандартных программ, имеются в библиотеках подпрограмм на ЭВМ.
1. Приведем несколько вариантов метода случайного поиска минимума функции 7(и) на множестве»»' — Е", предполагая, что й-е приближение и, ~ »»' (й > 0) уже известно. а) Алеоритм с возвратом при неудачном шаве. Смысл этого алгоритма заключается в следующем. С помощью датчика случайного вектора получают некоторую его реализацию $ и в пространстве Е определяют точку о,=и,+а$, а=сопа1)0. Если ов»и 17 и в' (ов) < в' (ив), то сделанный шаг считается удачным, и в этом случае полагается ив».» = о,. Если о,ш»7, но з(ов)> >в'(и,), или же о,ш 1», то сделанный шаг считается неудачным и полагается и„з, = ив. Если окажется, что и, = и,т, =...
= и,зв для достаточно больших»в, то точка и, может быть принята в качестве приближения искомой точки минимума. б) Алгоритм наилу иией крабы. Берутся какие-либо з реализаций $„..., $, случайного вектора $ н вычисляются значения функции в'(и) в тех точках и=ив+с»$» (1=1, ..., з), которые принадлежат множеству»7. Затем полагается изт» = из+ а$», в' где индекс 1, определяется условием л" (ид + а$» ) = ппп Х (иь + и$»). а» +а4»по »л»<в Величины з ) 1 и с» = сопз1 > 0 являются параметрами алгоритма. в) Алгоритм статистического градиента. Берутся какие-либо з реализаций $„..., $, случайного вектора $ и вычисляются разностп Лвв» = в'(ив + "(зв) — в'(ив) для всех и„+ ($»н О'. Затем 1 полага»от рь = — „,$,.ЛХА», где сумма оерется по всем тем 1 (» < з, для которых и, + (е»»н (7.
Если и„+ арв»н 07, то принимается и,„, = и,+»хрв. Если же и,+ арвид 0', то повторяют описанный процесс с новым набором из з реализаций случайного вектора $. Величины з) 1, и) О, () 0 являются параметрами алгоритма. Вектор р, называют статистическим градиентом. Если (»'=Е", в = и, и векторы С» являются неслучайными н совпадают с соответствующими единичными векторами е,=(0, ..., О, 1, ..., 0) (» =1, ..., и), то описанный алгоритм, как нетрудно видеть, превращается в разностный аналог градиентного метода. 412 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ (ГЛ, » 2.
В описанных вариантах а) — в) метода случайного поиска предполагается, что закон распределения случайного вектора й не зависит от номера итераций. Такой поиск называют случайным поиском без обучения. Алгоритмы случайного поиска беа обучения не обладают «способностью» анализировать результаты предыдущих итераций и выделять направления, более перспективные в смысле убывания минимизируемой функции, и сходятся, вообще говоря, медленно. Между тем ясно, что от метода случайного поиска можно ожидать большей эффективности, если на каждой итерации учитывать накопленный опыт поиска минимума на предыдущих итерациях и перестраивать вероятностные свойства поиска так, чтобы направления $, более перспективные в смысле убывания функции, становились более вероятными.
Иначе говоря, жела тельно иметь алгоритмы случайного поиска, которые обладают способностью к самообучению и самоусовершенствованию в процессе поиска минимума в зависимости от конкретных особек. ностей минимизируемой функции. Такой поиск называют случайным поиском с обучением. Обучение алгоритма осуществляют посредством целенаправленного изменения закона распределения случайного вектора $ в зависимости от номера итерации и результатов предыдущих итераций таким образом, чтобы «хорошие» направления, по которым функция убывает, стали более вероятными, а другие направления — менее вероятными. Таким образом, на различных этапах метода случайного поиска с обучением приходится иметь дело с реализациями случайных векторов $ с различными законами распределения. Имея в виду это обстоятельство, итерационный процесс (1) удобнее записать в виде (2) и,«, = и, + иДМ )«=0, 1, подчеркнув зависимость случайного вектора $ от )г.
В начале поиска закон распределения случайного вектора $ = э, выбирают с учетом имеющейся априорной информации о минимизируемой функции. Если такая информация отсутствует, то поиск обычно начинают со случайного вектора ь« =($'„..., ~,")« компоненты э«(1 = 1, ..., и) которого представляют собой независимые случайные величины, распределенные равномерно на отрезке ( — 1, 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
