автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.02, диссертация на тему:Асимптотические свойства рекуррентных процедур в стохастических моделях

Введение

1. Рекуррентные процедуры в стохастических моделях.

1.1. Независимые возмущения. Мартингальный подход.

1.2. Независимые возмущения, большие уклонения

1.3* Условия сходимости при зависимых возмущениях . 22 1.4. Постановка задач диссертации

2. Условия сходимости стохастических рекуррентных процедур

2.1. Достаточные условия сходимости для процедур с возмущениями, удовлетворяющими условию равномерно сильного перемешивания

2.2. Необходимое условие сходимости

2.3. Сходимость процедур с возмущениями авторегрессионного типа.

2.4. Доказательство вспомогательных лемм

3. Скорость сходимости стохастических рекуррентных процедур

3.1. Асимптотика процедур с линейным полем переноса

3.2. Точные верхние функции для степенного поля переноса

3.3. Скорость сходимости для авторегрессионных возмущений

3.4. Пример процедуры, для которой не существует точных верхних функций

3.5. Доказательство вспомогательных лемм

4. Стохастические рекуррентные процедуры в задачах минимизации аддитивных функций.

- 3

4*1. Вводные замечания.

4.2. Связь между областями, заметаемыми траекториями стохастических рекуррентных процедур, и множеством Парето многокритериальных задач

4.3. Примеры заметаемых областей

Актуальность проблемы. При решении многочисленных задач современной теории автоматического управления широкое распространение получили стохастические рекуррентные процедуры. В основе теории стохастических рекуррентных процедур лежат такие разделы современной науки, как теория адаптивных систем, теория устойчивости систем автоматического регулирования и управления, методы оптимизации, рекуррентные алгоритмы математической статистики.

В работах Я.З.Цыпкина была замечена общность проблем, возникающих в теории адаптивных обучающихся систем, и показано, что эти проблемы могут формулироваться как задачи на экстремум с функционалом типа среднего риска [4бГ) ; была выяснена связь между детерминированными алгоритмами оптимизации (градиентный метод), алгоритмами адаптации и обучения и рекуррентными процедурами математической статистики - процедурами стохастической аппроксимации, предложенными Роббинсом и Монро для оценивания корня уравнения — 0 по результатам измерения роды проблемы измерения подвержены ошибкам.

В связи с постановкой задачи на экстремум естественно возникает задача отыскания условий сходимости и скорости сходимости исследуемых процедур. Сходимость алгоритмов есть выражение факта устойчивости соответствующих стохастических систем, оценка скорости сходимости тесно связана с задачами качества систем.

Теоретические методы исследования свойств стохастических рекуррентных процедур постоянно совершенствовались. В монографиях Кушнера [28] , Невельсона и Хасьминского [ЗбГ] были подведены функции в ситуации, когда в силу стохастической приитоги единого математического подхода, основанного на теории мартингалов, к исследованию асимптотических свойств (сходимость и скорость сходимости) процедур с независимыми ошибками измерений (возмущениями). В последние годы с помощью техники, основанной на теории больших уклонений для марковских процессов, получены новые результаты об асимптотических свойствах стохастических рекуррентных процедур. В работах Коростелёва [j[7) - [яэ] найдены точные (необходимые и достаточные) условия сходимости и скорость сходимости (точные верхние функции) для процедур с независимыми возмущениями.

На практике часто возникает ситуация, когда возмущения в последовательные моменты времени являются зависимыми случайными векторами. Зависимость возмущений находит отражение и в теоретических исследованиях последнего десятилетия, в которых изучаются асимптотические свойства рекуррентных процедур в различных вероятностных смыслах: [2] , [23] , [24] , [2б] , [зз] , , \зв] , [40] , [41] , [59] , [бб] , [67] . Следует отметить, что число публикаций, посвященных исследованию процедур с зави-. симыми возмущениями, относительно невелико, и результаты, полученные в них, носят не столь законченный вид, как для процедур с независимыми возмущениями. В связи с этим поиск точных условий сходимости и скорости сходимости процедур с зависимыми возмущениями представляет несомненный интерес, поэтому тема исследований диссертационной работы является важной и актуальной.

Предмет исследования - рекуррентные процедуры оптимизации и оценивания параметров в стохастических моделях.

Цель исследования состоит в развитии теории стохастических рекуррентных процедур: изучения асимптотических свойств, выполняемых с вероятностью I (сходимость и скорость сходимости) процедур» в которых возмущения имеют степенную асимптотику функций распределения и являются зависимыми случайными векторами.

Теоретической и методологической основой работы служат:

- методы стохастической оптимизации,

- теория адаптивных систем,

- теория устойчивости динамических систем,

- теория больших уклонений для случайных процессов.

Научная новизна работы. Развит метод исследования стохастических рекуррентных процедур, основанный на теории больших уклонений для случайных процессов. Получены необходимые и достаточные условия сходимости с вероятностью I стохастических рекуррентных процедур для двух классов зависимых возмущений, имеющих степенную асимптотику функций распределения: первый класс - возмущения, удовлетворяющие условию равномерно сильного перемешивания, второй класс - возмущения типа белого щума, пропущенного через линейный неоднородный фильтр с экспоненциальным затуханием.

При изучении скорости сходимости найдены условия, при выполнении которых для процедур с возмущениями, имеющими степенную асимптотику функций распределения, существуют точные верхние функции: рассмотрены случаи независимых возмущений и возмущений, образующих стационарную авторегрессионную схему. Построен пример процедуры, для которой точных верхних функций не существует.

Методы исследования, развитые в диссертации, применены для изучения декомпозиционного алгоритма минимизации детерминированной аддитивной функции. Выявлены связи характеристик исследованного алгоритма с множеством Парето-оптимальных решений соответствующей многокритериальной задачи.

Практическая ценность работы. Теоретические разработки диссертационной работы являются методологической основой для исследования задач рекуррентного оценивания, оптимизации и адаптации в теории автоматического регулирования и управления. Результаты диссертации могут быть использованы для обоснованного выбора параметров рекуррентных алгоритмов, практически реализуемых на цифровых и аналоговых вычислительных средствах. Методы, разработанные в диссертации; позволили детально исследовать декомпозиционные процедуры оптимизации и могут быть также применены к изучению процедур других типов.

Апробация работы. Результаты диссертации докладывались на научных семинарах Всесоюзного научно-исследовательского института системных исследований ГКНТ и АН СССР, Института проблем передачи информации АН СССР, Института проблем управления Министерства приборостроения, средств автоматизации и систем управления СССР и АН СССР, на семинаре "Планирование эксперимента и анализ данных", проводимом совместно МГУ им.Ломоносова и Научным советом по комплексной проблеме "Кибернетика", семинаре "Многомерный статистический анализ и вероятностное моделирование реальных процессов" в ЦЭМИ АН СССР, на б-й конференции молодых учёных ВНШСИ (Москва, июнь 1983 года), на Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (Кемерово, март 1983 г.).

Апробация диссертации в целом проводилась на семинаре направления "Математические методы в системных исследованиях" ВНШСИ ГКНГ и АН СССР. По материалам диссертации опубликованы 3 научные работы - [20] , [29] , [30] - общим объемом 1,5 печатных листа.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка, включающего 76 наименований. Текст изложен на 132 страницах машинописного текста.

ЗАКЛЮЧЕНИЕ

Поставленная цель исследования - развитие теории стохастических рекуррентных процедур: изучение асимптотических свойств, выполняемых с вероятностью I (сходимость и скорость сходимости), процедур, в которых возмущения имеют степенную асимптотику функций распределения и являются зависимыми случайными векторами -реализована следующим образом,

I. Развит метод исследования стохастических рекуррентных процедур, основанный на теории больших уклонений для случайных процессов. Указанный метод состоит в рассмотрении стохастических процедур в качестве малых случайных возмущений устойчивых динамических систем и позволяет, используя точную асимптотику оценок вероятностей больших уклонений', получить точные (необходимые и достаточные) условия сходимости с вероятностью I и скорость сходимости (точные верхние функции) исследуемых процедур.

Z. Исследованы необходимые и достаточные условия сходимости с вероятностью I стохастических рекуррентных процедур, в которых возмущения имеют степенную асимптотику функций распределения (степенные хвосты) с показателем и являются зависимыми случайными векторами. Найдены необходимые и достаточные условия сходимости процедур, в которых возмущения удовлетворяют условию равномерно сильного перемешивания, и показано, что эти условия близки к соответствующим условиям сходимости для процедур с независимыми возмущениями.

3. Для случая возмущений типа белого щума, пропущенного через линейный неоднородный фильтр с экспоненциальным затуханием, найдено необходимое и достаточное условие сходимости, в точности совпадающее с условием сходимости для процедур с независимыми возмущениями.

4. Исследована скорость сходимости с вероятностью I - в терминах точных верхних функций - для стохастических рекуррентных процедур, в которых возмущения имеют степенные хвосты распределений с показателем $ • Найдены условия, при выполнении которых точные верхние функции для рассматриваемых процедур с независимыми возмущениями совпадают с точными верхними функциями для процедур с возмущениями, имеющими конечный экспоненциальный момент. Доказано, что при невыполнении указанных условий возможна ситуация, когда точных верхних функций не существует. Найдены точные верхние функции для процедур, в которых возмущения образуют стационарную авторегрессионную схему.

5. Исследована стохастическая рекуррентная процедура поиска минимума детерминированной аддитивной функции. Исследуемая процедура характеризуется случайным выбором номера функции, градиент которой определяет направление движения на данной итерации. Найдены условия, при выполнении которых множеством предельных точек траекторий процедуры является ограниченное замкнутое множество W » содержащее множество Парето-оптимальных решений соответствующей многокритериальной задачи минимизации. Приведены примеры построения множества W , дана его детерминированная интерпретация в терминах области достижимости некоторой динамической системы.

1. Бородин А.Н. Квазимартингалы. - Теория вероятн. и ее прим.,1978, т.23, № 3, с.661-664.

2. Бородин А.Н. Процедура стохастической аппроксимации при наблюдениях, удовлетворяющих условию слабой зависимости. -Теория вероятн. и ее прим., 1979, т.24, № I, с.34-51.

3. Вазан М. Стохастическая аппроксимация. М.: Мир, 1972. - 295 с.

4. Вентцель А.Д. Грубые предельные теоремы о больших уклонениях для марковских случайных процессов. Теория вероятн. и ее прим., I - 1976, т.21, № 2, с.231-251; II - 1976, т.21, № 3, с.512-526; III - 1979, т.24, № 4, с.673-691.

5. Вентцель А.Д., Фрейдлин М.И. О малых случайных возмущениях динамических систем. Успехи мат. наук, 1970, т.25, № I, с.3-55.

6. Вентцель А.Д., Фрейдлин М.И. Флуктуации в динамических системах под действием малых случайных возмущений. М.: Наука,1979. 424 с.

7. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1966. - 576 с.

8. Галошкин В.Ф., Красулина Т.П. О законе повторного логарифма в процессах стохастической аппроксимации. Теория вероятн. и ее прим., 1974, т.19, № 4, с.879-886.

9. Гертнер Ю. О больших уклонениях от инвариантной меры. Теория вероятн. и ее прим., 1977, т.22, № I, с.27-42.

10. Ю.Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. М.: Наука, 1977. - 568 с.

11. И.Гладышев Е.Г. О стохастической аппроксимации. Теория вероятн. и ее прим.» 1965, т.Ю, № 2, с.297-300.

12. Годованчук В.В., Коростелёв А.П. Условия локальной сходимостирекуррентных стохастических процедур. Теория вероятн. и ее прим., 1983, т.28, № I, с.135-142.

13. Ибрагимов И.А., Линник Ю.В. Независимые и стационарно связанные величины. М.: Наука, 1965. - 524 с.

14. Катковник В.Я. Линейные оценки и стохастические задачи оптимизации. М.: Наука, 1976. -324 с.

15. Кибардин В.М. Декомпозиция по функциям в задаче минимизации. -Автоматика и телемеханика, 1979, № 9, с.66-79.

16. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа» М.: Наука, 1976. - 544 с.

17. Коростелёв А.П. Затухающие возмущения динамических систем и условия сходимости рекуррентных стохастических рекуррентных процедур. Теория вероятн. и ее прим., 1979, т.24, № 2,с.298-317.

18. Коростелёв А.П. Замечание о верхних функциях для процедур стохастической аппроксимации. Теория вероятн. и её прим., 1983, т.28, № 4, с.769-775.

19. Коростелёв А.П. Стохастические рекуррентные процедуры (локальные свойства). М.: Наука, 1984. - 208 с.

20. Коростелёв А.П., Леонов С.Л. Верхние функции для стохастических рекуррентных процедур при степенных хвостах распределений.- В кн.: Динамика неоднородных систем. М.:ВНШСИ, 1983. -с.55-64.

21. Коростелев А.П., Мороз П.А. Теория больших уклонений для случайных процессов и стохастические рекуррентные процедуры оптимизации. В кн.: Проблемы случайного поиска, Рига: Зинат-не, 1978, № 6, с.168-201.

22. Красненкер А.С. 0 качестве алгоритмов векторной оптимизации.

23. Автоматика и телемеханика, 1984, № 3, с.168-172.

24. Красулина Т.П. О стохастической аппроксимации для случайных процессов с непрерывным временем, Теория вероятн. и ее прим., 1971, т.16, №4, с.688-695.

25. Красулина Т.П. Некоторые замечания о процессах стохастической аппроксимации. Автоматика и телемеханика, 1975, № 7,с.70-74.

26. Красулина Т.П. Оценка скорости сходимости процесса Роббинса -Монро. Автоматика и телемеханика, 1983, №Д, с.ИЗ-117.

27. Кульчицкий О.Ю. Немарковские алгоритмы статистической оптимизации с непрерывным временем. Автоматика и телемеханика, 1978, № 5, с.73-86; № 6, с.56-66.

28. Кунцевич В»М., Лычак М.М. Синтез систем автоматического управления с помощью функций Ляпунова. М.: Наука, 1977. - 400 с.

29. Кушнер Г. Стохастическая устойчивость и управление. М.: Мир, 1969. - 200 с.

30. Леонов С.Л. Условия сходимости процедур стохастической аппроксимации при зависимых возмущениях. Сборник трудов ВНИИСИ, 1982, вып.10, с.44-54.

31. Леонов С.Л. Процедуры стохастической аппроксимации с зависимыми помехами и принцип усреднения. -В кн.:Тезисы докладов Всесоюзного научно-практического семинара "Прикладные аспекты управления сложными системами". М. Кемерово, 1983, с.213-214.

32. Логинов Н.В. Методы стохастической аппроксимации. Автоматика и телемеханика, 1966, № 4, с.185-204.

33. Лоэв М. Теория вероятностей. М.: Иностранная литература, 1962. - 720с.

34. Льюнг Л. Асимптотические дисперсии алгоритмов стохастической аппроксимации. Автоматика и телемеханика, -I974, № 9, с.178-182.

35. Невельсон М.Б. О приближении процессов стохастической аппроксимации суммами независимых случайных величин. Problems of Control and Information Theory, 1976, vol.5, N 2, pp.117-133.

36. Зб.Невельсон М.Б. О сходимости моментов метода стохастической аппроксимации. Автоматика и телемеханика, 1978, № 2, с.83-92.

37. Невельсон М.Б., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание. М.: Наука, 1972. - 304 с.

38. Немировский А.С. 0 процедуре стохастической аппроксимации при зависимых шумах. Изв. АН СССР, сер. Техн.кибернетика, 1981,1. I, с.14-25.

39. Немировский А.С. 0 рекуррентном оценивании параметров линейных объектов. Автоматика и телемеханика, 1981, № 4, с.77-86.

40. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

41. Позняк А.С. 0 сходимости алгоритмов стохастической аппроксимации при идентификации параметров динамических объектов. Автоматика и телемеханика, 1979, № 8, с.186-190.

42. Позняк А.С., Товстуха Т.И. 0 сходимости квазиоптимальных алгоритмов идентификации. Автоматика и телемеханика, 1981, № 7, с.120-128.

43. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

44. Поляк Б.Т., Цыпкин Я.З. Адаптивные алгоритмы оценивания (сходимость, оптимальность, стабильность). Автоматика и телемеханика, 1979, № 3, с.71-84.

45. Растригин JI.A. Статистические методы поиска. М.: Наука, 1968. - 376 с.45.§рейдлин М.И. Принцип усреднения и теоремы о больших уклонениях. Успехи мат.наук, 1978, т.ЗЗ, № 5, с.107-160.

46. Цыпкин Я.З. Адаптация и обучение в автоматических системах. -М.: Наука, 1968. 400 с.

47. Цыпкин Я.З. Основы теории обучающихся систем. М.: Наука, 1970. - 252 с.

48. АпЪаг D. A modified Robbins Monro procedure approximating zero of a regression function from below. - Ann.Stat., 1977, v.5, No.1, pp.229-234.

49. Blum J.R. Approximation methods which, converge with probability one. Ann.Math.Stat., 1954, v.25, No.2, pp.382-386.

50. Blum J.R. Multidimensional stochastic approximation method. -Ann.Math.Stat., 1954, v.25, N0.4, pp.737-744.

51. Callianpur G. A note on a Robbins Monro stochastic approximation method. - Ann.Math.Stat., 1954, v.25, No.2,pp.386-388.

52. Chung K.L. On a stochastic approximation method. Ann.Math. Stat., 1954, v.25, No.3, PP.463-483.

53. Derman C. An application of Chung's lemma to Kiefer Wolfo-witz stochastic approximation procedure. - Ann.Math.Stat., 1956, v.27, No.2, pp.532-536.

54. Driml M., Nedoma J. Stochastic approximation for continuous random processes. In: Trans. 2-nd Prague Conference on Inform. Theory, Stat. Decision Functions and Random Proc., 1960, Prague, pp.145-158.

55. Dvoretzky A. On stochastic approximation. In: Proc. 3-d Berkeley Sympos. Math. Stat, and Prob., 1956, Berkeley: Univ. of California Press, v.1, pp.39-55.

56. Eichhorn B.H., Zacks S. Sequential search of an optimal dose.-J.Amer.Stat.Assoc., 1973, v.68, pp.594-598.

57. Fabian V. On asymptotic normality in stochastic approximation. Ann.Math.Stat., 1968, v.39, N0.4, pp.1327-1332.

58. Fisk D.L. Quasi-martingales. Trans.Amer.Math.Soc., 1969, v.120, No.3, pp.369-389.

59. Geman S. A method of averaging for random differential equations with applications to stability and stochastic approximation. In: Approximate Solution of Random Evolution Equations, 1979, N.Y. - Oxford; North Holland, pp.49-86.

60. Hanson D.L., Wright F.T. Some more results on rates of convergence in the law of large numbers for weighted sums of independent random variables. Trans. Amer. Math. Soc., 1969, v.141, pp.443-464.

61. Heyde C.C. On martingale limit theory and strong convergence results for stochastic approximation procedures. Stoch. Proc. Appl., 1974, v.2, N0.4, pp.359-370.

62. Hodges J.L., Lehman E.L. Two approximations to the Robbins -Monro process. In: Proc. 3-d Berkeley Sympos. Math. Stat, and Prob.,1956, Berkeley: Univ. of California Press, v.1, pp.95-104.

63. Kersting G. Almost sure approximation of the Robbins Monro process by sums of independent random variables. - Ann.Prob., 1977, v.5, N0.6, pp.954-965.

64. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function. Ann.Math.Stat., 1952, v.23, No.3,pp.462-466.

65. Komlos J., Revesz P. On the rate of convergence of the Robbins Monro process. - Z. Y/ahrscheinlichkeitstheorie verw. Geb., 1972, v.25, No.1, pp.39-47.

66. Igung L. Convergence of recursive stochastic algorithms. -Report 7403, Division of Automatic Control, Lund Institute of Technology, 1974, Lund, Sweden. 134pp.

67. Ljung L. Strong convergence of a stochastic approximation algorithm. Ann.Stat., 1978, v.6, No.3, pp.680-696.

68. Loeve M. On almost sure convergence. In: Proc. 2-nd Berkeley Sympos. Math. Stat, and Prob., 1951, Berkeley: Univ, of California Press, pp.279-303.

69. Major P. A law of iterated logarithm for the Robbins Monro method. - Studia Sci.Math.Hungar., 1973, v.8, pp.92-102.

70. Major P., Revesz P. A limit theorem for the Robbins Monro approximation. - Z. Wahrscheinlichkeitstheorie verw. Geb., 1973, v.27, No.1, pp.79-86.

71. Mises R., Pollaczek-Geiringer H. Praktigche Verfahren der Gleichungsauflosung. Z. Angew. Math. Mech., 1929, v.9, pp.58-77.

72. Revesz P. A note on the Robbins Monro method. - Studia Sci. Math. Hungar., 1972, v.7, pp.355-362.

73. Robbins H., Monro S. A stochastic approximation method. -Ann.Math.Stat., 1951, v.22, Uo.1, pp.400-407.74» Sacks J. Asymptotic distribution of stochastic approximation procedures. Ann.Math.Stat., 1958, vv.29, Ho.2, pp.373-405.

74. Sakrison D.J. A continuous Kiefer Wolfowitz procedure for random processes. - Ann.Math.Stat., 1964, v.35, Ho.2, pp. 590-599.

75. Wolfowitz J. On the stochastic approximation method of Robbins and Monro. Ann.Math.Stat., 1952, v.23, Ho.3, pp. 457-461.