Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 94
Текст из файла (страница 94)
Оказывается, если функциями(х) не ';.1' л! !, '«,, ЬД является гладкои, то метод покоординатного спуска может не сходиться ко множеству решений задачи (!). Об этом говорит следующий Пример 1. Пусть Г(и) = хл+ уг — 2(х+ у)+2!х — у), и =(х, у) Е Ел. Нетрудно проверить, что 7(и) сильно выпукла на Е' и, следовательно, ограничена снизу и достигает своей нижней грани на Е' в единственной точке.
Возьмем в качестве начального приближения точку и = (О, 0). Тогда имеем 7(и + ое) = 7(ое ) = ол — 2о + 2)о ~ ) 0 = 7(0), 7(ио+ ое) = 7(ое ) = о'— — 2о+ 2!о) > 0= 7(0) при всех действительных о. Отсюда следует, что все итерации метода (2) — (7) при начальной точке и, = (О, 0) и любом выборе начального параметра о = о, > 0 будут неудачными, т. е. и, = и при всех к =О, 1,... Однако в точке и,= (О, 0) функция 7(и) не достигает своей нижней грани на Е~: например, в точке и =(1, 1) имеем 7"(и) = — 2 < 7(и ) =О.
2. Описанный выше метод покоординатного спуска нетрудно модифицировать применительно к задаче минимизации функции на параллелепипеде: у(х) — «!и1; хЕХ=((х',,х"): а,(х'(Ь,, 1=1«...«п)« где а„Ь,. — заданные числа, а, < Ь,, Г = 1,..., и. А именно, пусть й-е приближенйе х е Х и число о„>0 прй некотором к >0 уже найдены. Выберем вектор р, = е,. согласно формуле (2), составим точку х„+ оьр„и проверим условия х + о,р„Е Х у(х«, + о„р ) < 7(х ). (10) Если оба условия (10) выполняются, то следующее приближение х„„„о„ч, определяем по формулам (4). Если же хотя бы одно условие (10) йе выполняется, то составляем точку хь — о,рл и проверяем условия хь о«Рь Е Х Г(хг оьРл) < 7(хь) (11) В случае выполнения обоих условий (11) следующее приближение определяем по формулам (6), а если хотя бы одно из условий (11) не выполняется, то следующее приближение находится по формулам (7).
Теорема 2. Пусть функция 7"(х) выпукла на Х и 7"(х)е С'(Х). Тогда при любом выборе начальных х„е Х и оь > 0 последовательность (х,), получаемая методом (10), (4), (11), (6), (7), минимизирует функцию 7(х) на Х и сходится ко множеству рггигний задачи (9). До к а з а т е л ь с т в о. Так как Х вЂ” параллелепипед, то множество М(т) =(х: х е Х, 7(х) < 7(хь)) ограничено, Так как Г(х „,) < 7(х ), к =О, 1,..., то (х„) Я Х и сУществУет !пп 7(хь) >7,, Так же, как в теореме 1, доказывается существование бесконечного числа номеров к, с... ...
< Ь„<... итераций, на которгях длина шага о„дробнтся, и поэтому !пп о„= О. В силу ограниченности М(х,) из (х„) можно выбрать сходящуюся подпоследовательность. Не умаляя общности, можем считать, что (х„)- х„=(х.',..., х,"), Прн каждом Г =1,,„п возможны следующие трй" случая. 1) а,, < х,* < Ь, Так как !пп о =О, то найдется номер Аг такой, что х + « + о„е, Е Х и х„— о е, е Х при всех «и > А!.
Поскольку оь при й = Ь дробйтся, то 7(х„+ ог е,) ) у(х„), 7(хь — о„е,) > 7(хь ) 314 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 315 $12. МЕТОД ПОКООРДИНАТНОГО СПУСКА для всех т > 7ть. Отсюда, как и в теореме 1, получаем 7"„,(х,) = О, так !то 7м(х„)(х' — хс) = О, а, ( хс < Ьс. 2) хс = а,. Тогда х + ст ес Е Х и 7(хь + сть ес) > 7" (хь ) пРн всех т > Ж. Следовательно, (!'(х + д,„сть е,), е,)оа >О йли 7,,(х +д,„сть е,.) >О длЯ каждого гп > Аг.
Отсюда при т — оо получим ум(х„) > О или 7,,(х,)(хс— — а.) =~,;(х.)(х' — хс) > О, ас < хс ( 6, 3) хс = Ь, Тогда х — а, ес ЕХ и 7(хь — оь ес) >7(хь ) при всех тп > )тг. ПоэтомУ (7(хь — д схь ес), ес)( — сть ) ~>О или Ум(хь — д сть ес) <О, т > 71Г. Отсюда при т- со получим 7"„.(х„) <О, следовательно, ~,(х„)(хс — Ьс) = 7,:(х,)(хс — хс) > О, ас < хс < Ь, Объединяя все три рассмотренных случая, заключаем, что 7"„,(х,)(хс — х„с) > О, ас < хс < Ьс, е' = 1,..., и. Суммируя эти неравенства по всем ( = 1,..., о, получим (7'(х„), х — х,) >О для всех х 6Х. Согласно теореме 4.2.3 тогда х, е Х..
Следовательно, 1пп 7(хь) = ь ч = !11п 7'(хь ) = 7(х„) = Г„т. е. (хь) — минимизиРУющаЯ последовательное™ть. Ото!ода и из теоремы 2.1.2 следует, что 1пп р(х„Х„) = О. Теорема 2 доказана. П 3. Существуют и другие варианты метода покоординатного спуска. Можно, например, строить последовательность (хь) по правилу (12) ха+ ~ = ха + «"ьуь~ где Рь определяется согласно (2), а аа — условиями а >О, д (ст )= пнп д„(ст), дь(сх)=У(х +сара).
(13) Метод (12), (13) имеет смысл применять в том случае, когда величина сть из (13) находится в явном виде. Так будет, если функция 7(х) — квадатичная, т. е. Р ! .Г(х) = 2(Ах, х) — (6, х), х Е Я", (14) где А — симметричная положительно определенная матрица, Ь е Е'. Нетрудно убедиться, что для функции (14) метод (12), (13) приводит к хо ошо известному методу Зейделя нз линейной алгебры !74; 891. отя и скорость сходимости метода покоординатного спуска, вообще говоря, невысокая, благодаря простоте каждой итерации, скромным требованиям к гладкости минимизируемой функции этот метод довольно широко применяется на практике, Существуют и другие методы минимизации, использующие лишь значения функции и не требующие для своей реализации вычисления производных.
Например, используя вместо производных их разностные аппроксимации, можно построить модификации рассматривавшихся в предыдущих параграфах методов, требующие вычисления лишь значений функции в подходящим образом выбранных точках. Другой подход для минимизации негладких функций, основанный лишь на вычислении значений функции, дает метод случайного поиска, который будет рассмотрен ниже в $ 19. Метод поиска глобального минимума, излагаемый в следующем параграфе, также относится к методам, не требу!ощим вычисления производных минимизируемой функции.
Упражнении !. Нарисуйте линии уровня Пя) = С = сопя! функции иэ примера 1 и поясните причину расходимости метода покоординатного спуска для этой функции при выборе оо = (0,0). 2. Опишите метод покоординатного спуска и докажите его сходимость для случая, когда в эадаче (9) о, = -со или ьь = оо дла каких-либо т, У, 1 < А г' к и.
3. Докажите сходимость метода (!2),(13) для функции (14) [74). 9 13. Метод покрытия в многомериььх задачах Опишем еще один метод минимизации, основанный лишь на вычислении значений целевой функции без привлечения значений каких-либо ее производных. Речь пойдет о методах покрытий, одномерный вариант которых был изложен в $1.7.
Эти методы служат для минимизации функций, удовлетворяющих условию Липшица. Заметим, что такие задачи в общем случае являются многоэнстремальньсми, т. е. в ннх могут существовать точки локального минимума, отличные от глобального минимума. Большинство методов, описанных выше в этой главе, прн их применении к многоэкстремальным задачам скорее всего нам помогут найти лишь какую-либо точку локального минимума, расположенную поблизости от начальной точки. Поэтому эти методы часто называют локальными методами. На практике для решения многоэкстремальных задач локальные методы обычно используются следующим образом: на множестве задают некоторую сетку точек и, выбирая в качестве начального приближения точки этой сетки, с помощью того или иного локального метода находят локальные минимумы функции, а затем, сравнивая полученные результаты, определяют ее глобальный минимум.
Однако ясно, что такой подход к решению многоэкстремальных задач весьма трудоемок н не всегда приводит к цели. Поэтому представляют большой интерес методы поиска глобального минимума в многоэкстремальных задачах. Перейдем к изложению одного из методов покрытий, которые служат для решения многоэкстремальных задач с целевой функцией, удовлетворяющей условию Липшица. Ограничимся рассмотрением задачи минимизации на параллелепипеде: 7"(х)- !и1, хЕ П=(х=(х',..., х"): ас < хс < Ьс, ь'=1,..., и), (1) где а,, Ьс — заданные числа, а,. < 6,, а функция Г'(х) удовлетворяет условию )7(х) — 7(у)) ( 7 !х — у) 'ох, у Е П, (2) где Х = сопз! > О, )х — у/ = !пах )хс — ус/. В правой части (2) можно было 1ссяь поставить любую другую норму ~ х — у)„, 1 < р < оо, например, евклидову норму )х — у~, как это мы неоднократно делали выше, когда требовали условие Липшица от функции или ее производных. В силу эквивалентности норм в 316 Гл.
З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $ !3. МЕТОД ПОКРЫТИЯ В МНОГОМЕРНЫХ ЗАДАЧАХ 317 Е" условие Липшица в любой норме может быть сведено к виду (2). А норма !х-у~ здесь привлекает нас тем, что такие множества, как параллелепипед, куб удобно описывать с помощью именно такой нормы. Так, например, множество (х ЕЕ": !х — т ( < 6/2)=(хеЕ": !х' — х*'!(6/2, 4 =1,..., и) представляет собой куб с центром в точке х,, ребром длины 6 н с гранями, параллельными осям координат. Именно такими кубами мы будем покрывать параллелепипед П.
Кроме того, использование нормы ! ~ позволит нам изложить многомерный вариант метода покрытий для решения задачи (1) также просто, как в одномерном случае (см. $ 1,7, п, 4). На параллелепипеде П введем сетку П„, состоящую из точек х, =(х1, х~,..., х>',..., хз), >'-я координата х> которых при каждом у=1,..., п образована по правилу (ср.
с $ 1.7): х,'=а.+2 4=х>>+6, ..., х,'„.,=х,','+6, ..., Ь т 21 х', = х, +(п>з — 2)6, х = пни(х, + (тз — 1)6; Ь,), где 6 = — — шаг метода, а натуральное число тг определяется условием 2е = Ь х, < Ьз — ' — < х>! Е(тз — 1)'6. В качестве приближения нижней грани /, в Ь задаче (1), можно взять величину пни /(х>, ) = Г>„которую можно найти с помощью простого перебора всех значений функции /(х) по точкам сетки П„. Справедлива Теорема 1. Для любой функции /(х), удовлетворяющей условию (2), справедлива оценка / ( Г>, ( /, + е. Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
