Содержание к диссертации
Стр.
Введение ....................................... 4
1. Рекуррентные процедуры в стохастических моделях 10
Ї.Ї. Независимые возмущения. Мартингальный подход 12
-
Независимые возмущения, большие уклонения ... 16
-
Условия сходимости при зависимых возмущениях ..... 22
-
Постановка задач диссертации 28
2. Условия сходимости стохастических рекуррентных процедур 30
-
Достаточные условия сходимости для процедур с возмущениями, удовлетворяющими условию равномерно сильного перемешивания 32
-
Необходимое условие сходимости 46
-
Сходимость процедур с возмущениями авторегрессионного типа 50
-
Доказательство вспомогательных лемм .............. 56
3. Скорость сходимости стохастических рекуррентных проце
дур 72
-
Асимптотика процедур с линейным полем переноса 73
-
Точные верхние функции для степенного поля переноса 81
-
Скорость сходимости для авторегрессионных возмущений ..* 84
-
Пример процедуры, для которой не существует
точных верхних функций 90
3.5. Доказательство вспомогательных лемм 98
4. Стохастические рекуррентные процедуры в задачах миними
зации аддитивных функций 108
4.1. Вводные замечания 108
4.2« Связь между областями, заметаемыми траекториями стохастических рекуррентных процедур, и множеством
Парето многокритериальных задач .е........... 114
4.3. Примеры заметаемых областей 124
Заключение 131
Литература 133
Введение к работе
Актуальность проблемы. При решении многочисленных задач современной теории автоматического управления широкое распространение получили стохастические рекуррентные процедуры. В основе теории стохастических рекуррентных процедур лежат такие разделы современной науки, как теория адаптивных систем, теория устойчивости систем автоматического регулирования и управления, методы оптимизации, рекуррентные алгоритмы математической статистики.
В работах Я.З.Цыпкина была замечена общность проблем, возникающих в теории адаптивных обучающихся систем, и показано, что эти проблемы могут формулироваться как задачи на экстремум с функционалом типа среднего риска [46J ; была выяснена связь между детерминированными алгоритмами оптимизации (градиентный метод), алгоритмами адаптации и обучения и рекуррентными процедурами математической статистики - процедурами стохастической аппроксимации, предложенными Роббинсом и Монро [_73] <^ля Ченива-ния корня уравнения 1э(Х)~ 0 по результатам измерения функции &(/) в ситуации, когда в силу стохастической природы проблемы измерения подвержены ошибкам.
В связи с постановкой задачи на экстремум естественно возникает задача отыскания условий сходимости и скорости сходимости исследуемых процедур. Сходимость алгоритмов есть выражение факта устойчивости соответствующих стохастических систем, оценка скорости сходимости тесно связана с задачами качества систем.
Теоретические методы исследования свойств стохастических рекуррентных процедур постоянно совершенствовались. В монографиях Кушнера [28j , Невельсона и Хасьминского \3&\ были подведены итоги единого математического подхода, основанного на теории мартингалов, к исследованию асимптотических свойств (сходимость и скорость сходимости) процедур с независимыми ошибками измерений (возмущениями). В последние годы с помощью техники, основанной на теории больших уклонений для марковских процессов, получены новые результаты об асимптотических свойствах стохастических рекуррентных процедур. В работах Коростелева Гі7] - |_29J найдены точные (необходимые и достаточные) условия сходимости и скорость сходимости (точные верхние функции) для процедур с независимыми возмущениями.
На практике часто возникает ситуация, когда возмущения в последовательные моменты времени являются зависимыми случайными векторами. Зависимость возмущений находит отражение и в теоретических исследованиях последнего десятилетия, в которых изучаются асимптотические свойства рекуррентных процедур в различных вероятностных смыслах: [2] , [ZZ] , [24] , [2б] , [зз] , J37J , \зв] , [40] , [4l] , [59] , [бб] , [б7] . Следует отметить, что число публикаций, посвященных исследованию процедур с зави-. симыми возмущениями, относительно невелико, и результаты, полученные в них, носят не столь законченный вид, как для процедур с независимыми возмущениями. В связи с этим поиск точных условий сходимости и скорости сходимости процедур с зависимыми возмущениями представляет несомненный интерес, поэтому тема исследований диссертационной работы является важной и актуальной.
Предмет исследования - рекуррентные процедуры оптимизации и оценивания параметров в стохастических моделях.
Цель исследования состоит в развитии теории стохастических рекуррентных процедур: изучения асимптотических свойств, выпол- - б - няемых с вероятностью I (сходимость и скорость сходимости) процедур» в которых возмущения имеют степенную асимптотику функций распределения и являются зависимыми случайными векторами. Теоретической и методологической основой работы служат: методы стохастической оптимизации, теория адаптивных систем, теория устойчивости динамических систем, теория больших уклонений для случайных процессов.
Научная новизна работы. Развит метод исследования стохастических рекуррентных процедур, основанный на теории больших уклонений для случайных процессов. Получены необходимые и достаточные условия сходимости с вероятностью I стохастических рекуррентных процедур для двух классов зависимых возмущений, имеющих степенную асимптотику функций распределения: первый класс - возмущения, удовлетворяющие условию равномерно сильного перемешивания, второй класс - возмущения типа белого шума, пропущенного через линейный неоднородный фильтр с экспоненциальным затуханием.
При изучении скорости сходимости найдены условия, при выполнении которых для процедур с возмущениями, имеющими степенную асимптотику функций распределения, существуют точные верхние функции: рассмотрены случаи независимых возмущений и возмущений, образующих стационарную авторегрессионную схему. Построен пример процедуры, для которой точных верхних функций не существует.
Методы исследования, развитые в диссертации, применены для изучения декомпозиционного алгоритма минимизации детерминированной аддитивной функции. Выявлены связи характеристик исследованного алгоритма с множеством Парето-оптимальных решений соответствующей многокритериальной задачи.
Практическая ценность работы. Теоретические разработки диссертационной работы являются методологической основой для исследования задач рекуррентного оценивания, оптимизации и адаптации в теории автоматического регулирования и управления. Результаты диссертации могут быть использованы для обоснованного выбора параметров рекуррентных алгоритмов, практически реализуемых на цифровых и аналоговых вычислительных средствах. Методы, разработанные в диссертации; позволили детально исследовать декомпозиционные процедуры оптимизации и могут быть также применены к изучению процедур других типов.
Апробация работы. Результаты диссертации докладывались на научных семинарах Всесоюзного научно-исследовательского института системных исследований ГКНТ и АН СССР, Института проблем передачи информации АН СССР, Института проблем управления Министерства приборостроения, средств автоматизации и систем управления СССР и АН СССР, на семинаре "Планирование эксперимента и анализ данных", проводимом совместно МГУ им.Ломоносова и Научным советом по комплексной проблеме "Кибернетика", семинаре "Многомерный статистический анализ и вероятностное моделирование реальных процессов" в ЦЭМИ АН СССР, на 6-й конференции молодых учёных ВНИИСИ (Москва, июнь 1983 года), на Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (Кемерово, март 1983 г.).
Апробация диссертации в целом проводилась на семинаре направления "Математические методы в системных исследованиях" ВНИИСИ ПШГ и АН СССР. По материалам диссертации опубликованы 3 научные работы - [z6\ , [29] , [зо] - общим объемом 1,5 печатных листа.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка, включающего 76 наименований. Текст изложен на 132 страницах машинописного текста.
В первой главе диссертации приведен обзор результатов и методов исследования стохастических рекуррентных процедур. Материалы обзора сгруппированы в три раздела. В первых двух разделах обсуждается проблема исследования стохастических рекуррентных процедур при независимых возмущениях: первый раздел посвящен мартингальному подходу к исследованию процедур, второй раздел -подходу, основанному на теории больших уклонений для случайных процессов. В третьем разделе приведен обзор исследований рекуррентных процедур при зависимых возмущениях. В четвертом разделе первой главы дана постановка задач диссертации.
Во второй главе исследуются необходимые и достаточные условия сходимости с вероятностью Ї стохастических рекуррентных процедур, в которых возмущения имеют степенную асимптотику функций распределения (степенные хвосты распределений) с показателем >2 и являются зависимыми случайными векторами. Найдены необходимые и достаточные условия сходимости процедур, в которых возмущения удовлетворяют условию равномерно сильного перемешивания (р.с.п.). Показано, что эти условия близки к соответствующим условиям сходимости для процедур с независимыми возмущениями. Для случая возмущений типа белого щума, пропущенного через линейный неоднородный фильтр с экспоненциальным затуханием, найдено необходимое и достаточное условие сходимости, которое совпадает с условием сходимости для процедур с независимыми возмущениями.
В третьей главе исследуется скорость сходимости с вероят- ностьго I - в терминах точных верхних функций - стохастических рекуррентных процедур, в которых возмущения имеют степенные хвосты распределений с показателем \>Z Найдены условия, при выполнении которых точные верхние функции для рассматриваемых процедур совпадают с точными верхними функциями для процедур с возмущениями, имеющими конечный экспоненциальный момент. Доказано, что при невыполнении указанных условий возможна ситуация, когда точных верхних функций не существует. Найдены точные верхние функции для процедур, в которых возмущения образуют стационарную авторегрессионную схему.
В четвёртой главе диссертации исследована стохастическая рекуррентная процедура поиска минимума аддитивной функции. Исследуемая процедура характеризуется случайным выбором номера функции, градиент которой определяет направление движения на данной итерации. Найдены условия, при выполнении которых множеством предельных точек траекторий процедуры является ограниченное замкнутое множество уу » содержащее множество Парето-опти-мальных решений соответствующей многокритериальной задачи минимизации. Приведены примеры построения множества W , дана его детерминированная интерпретация в терминах области достижимости некоторой динамической системы.
Заключение содержит выводы из диссертации.
