Ф.П. Васильев - Методы оптимизации (1125241), страница 74
Текст из файла (страница 74)
Сразу заметим, что итерационныи процесс (3) представляет собой известный метод ломаных Эйлера для приближенного определения траектории системы (45), выходящей из точки х(0)= х . По аналогии с теоремами 1-3 можно надеяться, что при некоторых ограничениях на функцию /(х), п(Ь) траектории х(6), 6 > О, системы (45) при больших Ь притягиваются ко множеству Я, = (х е Е": /'(х,) = 0) стационарных точек задачи (1) или, в лучшем случае, ко множеству Х, решений задачи (1).
Очевидно, все точки множеств Я„Х, являются точками равновесия (стационарными решениями) системы (45), Приведем две теоремы о сходимости метода (45). Те о ре ма 6. Пусть функция /(х) Е С! '(Е"), выпукла на Е", /„> — оо, Х,фй, а функция п(Ь) непрерывно дифференцируема при Ь >О, сг(ь) > сто > О, а'(ь) < 0 !/6 > О, тогда траектория х(ь) системы (45) с любым начальным условием х(0) = х определена при всех 6 > 0 и существует точка гг, Е Х, такая, что 1пп х(Ь) = 22„ 1пп х(Ь) =О, Г тОО * Г Э О ![ш /(х(Ь» = /(и) = /„!!ш / (х(Ь» =/ч(н) = О. Д о к а з а т е л ь с т в о. При выполнении условий теоремы 0 < ао < сг ( ь ) < < п(0) и правая часть (-сг(Ь)/'(х» дифференциального уравнения (45) удовлетворяет условию Липшица по х, непрерывна по совокупности аргументов (Ь, х).
Тогда задача Коши для уравнения (45) с начальным условием х(0) = х имеет решение х = х(6), определенное при всех Ь > 0 (см, ниже теорему 6.1.1). Возьмем Чх, Е Х„и умножим (45) скалярно на х(Ь) — х,: ('(ь), *(ь) - ..> = -2' 42~ (ь) - .Г = - (ь)(~ (.(2», .(2) - .> Отсюда с учетом равенства /'(х„) =О, условия п(Ь) > 0 и теоремы 4.2.4 имеем: 32!х(Ь) — х,!2=-2сг(6)(/(х(6» — /г(х,), х(Ь) — х„) <О 26 >О.
Таким образом, функция /х(Ь) — х,[2 не возрастает при Ь > О, т. е. !х(Ь) — х„!' < /х(т) — х,/2 !/Ь > т > О, Чх„С Х„. (46) В частности, при т=О: ]х(6) — х„!<!хо — х„!, т. е. траектория х(Ь) ограничена равномерно на Ь > О. Далее, умножим уравнение (45) скалярно на х(Ь); ]х(Ь)!' = — сг(Ь)(Г'(х(Ь», х(Ь)> = — п(Ь)32 (Г(х(2) — /(х.)), Ь > О. 5 1. ГРАДИЕНТНЫЙ МЕТОД 247 :1:-'::::::- Енг 248 Гл. 5.
МЕТОДЫ МИНИМИЗАПИИ 4>УНКПИЙ МНОГИХ ПЕРЕМЕННЫХ 4 1. ГРАДИЕНТНЫЙ МЕТОД 249 Интегрируя зто равенство и преобразуя по частям, получим: с ) ]х(т)! с]т = — а(т)(г(х(т)) — > (х))! + 1 а'(т)(> (х(т)) — 1(х))с]т. о о Так как 0 < ао < а(4) < а(0), ас(ь) < О, 7(х(ь)) — 7(х„) > 0 >/4 > О, то с ) ]х(т)]гс]т < а(0)(/(то) — /(х.)) Чг > О.
о Это значит, что ] ~х(т)]гс]т < со. Тогда найдется последовательность (и,.) — « о -++со, что (х((с)) — «О. Так как ]х(1)/ ограничено при й > О, то, пользуясь теоремой Больцано — Вейерпстрасса, можем считать, что х(4,.) — е . Из (45) при х = хс — со с учетом !!гп а(х) > а > 0 получим ~'(е„) = О. Отсюда и с оо из выпУклости /(х) слеДУет, что г>„Е Х,. Из (46) пРи т = бс, х, = е., имеем; ]х(ь) — п,]г < ]х($,) — п,]г >/Ф > йс Переходя к пределу сначала при $ — «+со, затем ь — + со, отсюда получим ]!п> х(ь) = е,.
тогда ]]гп,/(х(х)) = Г(г>,) = с оо * =,/„!!п> /'(х(б)) =/'(е,) = О, а из (45) следует: йп> х(1) = О. Теорема 6 с о с о доказана. П Для сильно выпуклых функций несложно получить оценку скорости метода (45), Теорема 7. Пусть функция /(х)ЕСЬ (Е ) и сильно нылукла на удо, а функция а(1), Уг>0, ] а(г)дг=+оо.
Тогда для траектории х(1) системы(45) с любым начальным о условием х(0) = хо спранедлиза оценка: с ]х(е) — х„! < ]хо — х,! ехр(-р ] а(т)дт) чз > О, (47) о где настоянная и > 0 нзннш из теоремьс 4.3.3. Доназательстно. Прежде всего заметим, что по теореме 4.3,1 точка минимума х, функции /(х) на хо существует и единственна, а по теореме 4,2,3 /'(х,) = О. Полонсим 1(г)=1! (Е) — [г, С>О, (48) Тогда с учетом (45) и теоремы 4.3.3 имеем: р(1) = (х(з) — т.„х(1)) = -а(г)(/'(х(Ф)) — /'(х„), х(г) — х„) < и <— ра(г)[х(е) — х„[г =-2ра(е))г(с)« '«сг >О; У(0) = [х> — х [г/2.
Отсюда следует.' — ('«'(Е) ехр(2р ] а(т)дт)) < 0 Ус > О, Интегрируя это неравенство, получим о 0 < Р(г) < 1г(0) ехр( — 2р ] а(т)дт) = [хо — х [г ехр(-2р ] о(т)дт) /2, о о что равносильно оценке (47). Теорема 7 доказана. О Пользуясь терминологией, принятой з теории устойчивости обыкновенных дифференциаль. ных уравнений [328; 376; 588; 694], можно сказать, что н теореме 7 доказана асимптотичесная устойчиность системы (45) относительно точки равновесия х, этой системы. Для доказательстна этого факта использован второй метод Ляпунова, н качестве функции Ляпунова была взята функция (48).
В саязи с этим полезно заметить, что при исследовании многих методов минимизации явно или неявно используется второй метод Ляпунове или его диснретный аналог; н качестзе функции ляпунова наряду с (48) часто используются также функции ъ'(г) =/(х(е))-/., И(г) = ]/'(х(1))]~ и др. Систематическое исследование сходимости методов минимизации с помощью метода Ляпунова проведено н [77]. Существуют и другие дифференциальные уравнения, траектории которых являются минимизирующими. Например, так назыааемый метод тяжелого шарика [74[ заключается н рассмотрении системы дифференциальных уравнений вида: х(г)+ х(Ф)-Ь а(1)/~(х(1)) =О, Е ~ )О, а(1) >О.
(49) Оказывается, траектории системы (49) при довольно широких предположениях сходятся и точке минимума фуннции /(х) на Но, причем скорость сходимости, вообще гоаоря, выше, чем у траекторий системы (45) Следует заметить, что непрерывные методы минимизации привлекательны тем, что для приближенного решения возникающих здесь задач Коши могут быть использоааны не тольно метод ломаных Эйлера, но и другие известные методы [59; 74; 89; 481], которые, нозмо>кно, будут сходиться быстрее и лучше приспособлены для минимизации озрахсных функций, приводящих к так назынеемым жесткилс системам дифференциальных уравнений, На этом пути можно получить различные классы дискретных методов минимизации, которые подчас трудно обнаружить, оставаясь н рамках привычных представлений, навязанных итеративными схемами. Перечисленные обстоятельства стимулируют развитие непрерывных методов решения экстремальных задач (см., например, [25; 26; 28-30; 732)) Непрерывные аналоги некоторых методов изложены ниже з 44 2, б, 11, 7.
В заключение отметим, что градиентный метод, вообще говоры, хорошо работает лишь на первых этапах поиска минимума, когда точни хь из (3) не слишком близки к точке минимума х„ а вблизи точки х, расстояние [хь — х„! часто перестает уменьшаться, сходимость метода ухудшается. Это связано с тем, что н окрестности точки минимума градиент /'(хь) близок и нулю, главная линейная часть приращения /(хь) — /(х„), на базе которой выбирается направление спуска н методе (3), становится малой, усиливается влияние квадратичной чести приращения, метод (3) становится слишком чувствительным к неизбежным погрешностям зы.
числений, Поэтому вблизи точки минимума при необходимости пользуются более точными и, вообще говоря, более трудоемкими методами, лучше учитывающими не только линейные, но и кзадратичные части приращения. Упражнении 1, Описать различные варианты градиентного метода для задачи из примера 2.2.2.
2. Установить сходимость, метода скорейшего спуска для функции (5); описать другие нарианты градиентного метода для этой функции. 3, Рассмотреть метод скорейшего спуска и другие варианты градиентного метода для задачи минимизации функции /(х) = ]Ах — ь[г, х е ь'", где А — матрица порядка т х и, ь е В"; исследовать их сходимость. 4. Рассмотреть метод сссооейшего спуска для минимизации функций /(и) = х + ау, и = г г =(х> у) ЕВ, и /(и) =х + у +аз, и=(ж у, з) ЕЕ, при различном начапьном приближении ио, считая коэффициент а намного больше единицы.
5. Доказать теоремы 1, 2 для метода (3), (7). 9 2. Метод проекции градиента 1. Будем рассматривать задачу /(х)- !и[; хЕХСЕ", ([) где множество Х необязательно совпадает со всем пространством Е", а функция /(х) е Сс(Х). Непосредственное применение описанного выше градиентного метода в случае Х ~ Ж" может привести к затруднениям, так как точка хььс из (1.3) при каком-то /с может не принадлежать Х. Однако зту трудность можно преодолеть, если полученную с помощью формулы (1,3) точку х, — аь /'(хн) при каждом й проектировать на множество Х (см. Определенйе 4,4.1). В результате мы придем к так называемому методу проекции градиента. А именно, пусть х е Х вЂ” некоторое начальное приближение. Далее будем строить последовательность (х„) по правилу х„„, =Рх(хь — аь,/'(хь)), й = О, 1,..., 251 250 Гк 3.
метОды минимизАции Функций мнОГих пеРеменных 4 2 МЕТОД ПРОЕКЦИИ ГРАДИЕНТА где сиь — положительная величина. Если Х вЂ” выпуклое замкнутое множество й способ выбора (аь) в (2) задан, то в силу теоремы 4.4.1 последовательность ~х„) будет однозначно определяться условием (2). В частности, при Х = Е метод (2) превратится в градиентный метод.
Если в (2) на некоторой итерации оказалось х„~, = хь (например, это случится при /'(хь) = 0), то процесс (2) прекращают. В этом случае точка х. удовлетворяет необходимому условию оптимальности хь =Рз(хь — а,./'(хь)) (см. теорему (4.4.3), и для выяснения того, является ли в действительности х, решением задачи (1) или нет, при необходимости нужно провести дополнительное исследование поведения функции /(х) в окрестности точки х„, В частности, если /(х) — выпуклая функция, то такая точка х является решением задачи (1).
В зависимости от способа выбора а„ в (2) можно получить различные варианты метода проекции градиента. Укажем несколько наиболее употребительных на практике способов выбора аь. 1) Введем функцию одной переменной дь(а) = /(Рх(хь — а/'(хь)), а > О, и определим аь из условий дь(аь) = !и! дь(а)=д „, а„>0.
(3) и ьО Очевидно, при Х = г," метод (2), (3) превратится в метод скорейшего спуска. Поскольку величину аь из условий (3) удается найти точно лишь в редких случаях (возможно также, что нижняя грань в (3) не всегда достигается), то аь на практике определяют приближенно из условий типа (1.6) или (1.?). 2) Иногда приходится довольствоваться нахождением какого-либо а„> О, обеспечивающего условие монотонности: /(х„~,) < /(хь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
