Рандомизированные алгоритмы стохастической аппроксимации при неопределенностях с бесконечным вторым моментом тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Вахитов, Александр Тимурович

• Вахитов, Александр Тимурович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Вахитов, Александр Тимурович

Введение.

1 Рандомизированные алгоритмы стохастической аппроксимации

1.1 Оптимизация дифференцируемых функций.

1.2 Оптимизация функционала среднего риска.

1.3 Методы на основе аппроксимации градиента.

1.4 Рандомизированные алгоритмы стохастической аппроксимации

1.5 Модели со случайными величинами с бесконечной дисперсией и задачи оптимизации.

1.5.1 Модель высокооптимизированной толерантности

1.5.2 Модель присоединения с предпочтением.

2 Свойства последовательностей оценок РАСА

2.1 Условия состоятельности и стабилизации оценок.

2.2 Примеры задач.'.

2.3 Состоятельность оценок в стационарном случае.

2.4 Скорость сходимости.

2.5 Стабилизация оценок в нестационарном случае.

2.6 Доказательства теорем 1-5.

3 Система управления загрузкой узлов распределенной вычислительной сети

3.1 Задача з-агрузки узлов распределенной сети.

3.2 Управление с обратной связью.

3.3 Имитационное моделирование.

3.4 Доказательства теорем 7,8.

Введение диссертации (часть автореферата) на тему «Рандомизированные алгоритмы стохастической аппроксимации при неопределенностях с бесконечным вторым моментом»

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

В пятидесятые годы XX века для решения задачи стохастической оптимизации начинают использоваться методы стохастической аппроксимации Роббинса-Монро [121] и Кифера-Вольфовица [97]. Они были развиты в работах B.C. Боркара [70], М. Вазана [2], Ю.М. Ермольева [28], Дж. Ина [102], В.Я. Катковника [33-35], Т.П. Красулиной [36-38], Г. Куш-нера [102], М.Б. Невельсона [44], А.С. Немировского [110], Ю.Е. Нестерова [111], А.С. Позняка [120], Б.Т. Поляка [48-50], Р.З. Хасьминского [44], Я.З. Цыпкина [50], В. Фабиана [80], В.Н. Фомина [56,57], A.JI. Фрадкова и В.А. Якубовича [57], Д.Б. Юдина [59] и др.

В работах М. Вадьясагара [132], Л. Гао [93], Д. Калафиори и М. Кам-пи [72], JL Льюнга [93], О.Н. Граничила, Б.Т. Поляка и П.С. Щербакова [24,119] и др. показана целесообразность использования в задачах оценивания рандомизированных алгоритмов, которые позволяют ускорить процедуры решения задач и устранить эффекты смещения.

Рандомизированные алгоритмы стохастической аппроксимации (РА

СА, в англоязычной литературе — SPSA, Simultaneous Perturbation Stochastic Approximation), были предложены в работах О.Н. Граничина [20], Б.Т. Поляка и А.Б. Цыбакова [49], Дж. Спалла [125,126] в конце 80-х, начале 90-х гг. XX в., развивая идеи методов случайного поиска, детально исследованные в русскоязычной литературе С.М.Ермаковым и А.А.Жиглявским [25,26], А.Жилинскасом [29], Л.А.Растригиным [52] и др. О.Н. Граничиным в 1989-1992 гг. было показано, что эти алгоритмы работоспособны в условиях неизвестных ограниченных помех наблюдения (unknown but bounded) [20,22]. В задачах стационарной оптимизации Б.Т. Поляк и А.Б. Цыбаков в 1990 г. обосновали минимаксную асимптотическую оптимальность скорости сходимости оценок этих алгоритмов, в том смысле, что порядок ее не может быть улучшен никаким другим итеративным алгоритмом [49J. Дж. Спаллом в 1992-1997 гг. была установлена оптимальность использования в качестве пробного возмущения распределения Бернулли и уменьшение количества измерений для получения оценки заданного качества по сравнению с процедурой Кифера-Вольфовица [122,127,128].

Несмотря на большое количество публикаций по исследованию свойств оценок алгоритмов типа SPSA, теоретическая обоснованность их использования в целом ряде важных практических приложений до последнего времени существенно ограничивалась предположениями об ограниченности второго момента у неопределенностей. С.С. Сысоевым в 2005 г. была обоснована в частном случае состоятельность рандомизированного алгоритма стохастической аппроксимации с одним измерением при существовании конечного момента степени р G (1; 2] [54].

В последнее десятилетие методы управления и оптимизации нашли важное приложение в теории распределенных и мультиагентных систем, а также систем массового обслуживания, в работах Ф. Булло, X. Кортес и С. Мартинез [71], Г. Вайса [134], Н.К. Кривулина [100], А.С. Матвеева и А.В. Савкина [107], Ж. Фербера [82] и др.

Цель работы — исследование свойств оценок рандомизированных алгоритмов стохастической аппроксимации в стационарном и нестационарном случае при наличии у неопределенностей конечного момента степени Р, 1 < Р < 2.

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

1. исследовать в стационарном случае свойства состоятельности оценок РАСА с уменьшающимися до нуля размерами шагов.

2. получить асимптотические оценки скорости сходимости РАСА.

3. исследовать в нестационарном случае свойства стабилизируемое™ последовательности оценок РАСА с постоянным размером шага.

4. Разработать модель системы управления загрузкой узлов распределенной вычислительной сети, в контур обратной связи которой включены РАСА, и исследовать ее поведение при неопределенностях, распределенных с бесконечными вторыми моментами.

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

В работе получены следующие основные научные результаты. В задачах оптимизации функционала типа среднего риска со статистическими неопределенностями с конечными моментами степени р £ (1,2] и почти произвольной ограниченной аддитивной помехе наблюдения установлены необходимые условия состоятельности и сильной состоятельности оценок РАСА в стационарном случае, асимптотические оценки скорости сходимости РАСА, необходимые условия стабилизации последовательности оценок и получено выражение для границы стабилизации РАСА в нестационарном случае. Разработана динамическая модель системы управления загрузкой узлов распределенной вычислительной сети, в которой случайный дрейф производительности процессоров имеет бесконечную дисперсию, а в контур обратной связи включены РАСА. Применимость РАСА подтверждается полученными теоретическими границами на время обработки пакета заданий и имитационным моделированием.

Все основные научные результаты диссертации являются новыми.

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

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

Результаты работы докладывались на научных семинарах кафедр системного- программирования и теоретической кибернетики СПбГУ, на Балтийских олимпиадах по автоматическому управлению в 2006 и 2008 гг. (в 2008 г. доклад был удостоен награды первой степени за теоретическую значимость), на научных конференциях: 5th WSEAS Conference on Automatic Control, Modeling and Simulation в 2006 г. (Прага, Чехия, доклад был удостоен премии за лучший студенческий доклад), Всерос. научн. конф. "Научный сервис в сети Интернет" (2006,2007,2009), 9th IFAC Workshop "Adaptation and Learning in Control and Signal Processing" (ALCOSP'07, Санкт-Петербург, 2007), XI конф. молодых ученых "Навигация и управление движением" (Санкт-Петербург, 2009), Первая традиционная всероссийская молодежная летняя школа "Управление, информация и оптимизация" (Персславль-Залесский, 2009), 3rd IEEE Multiconfcrencc on Systems and Control (2009), Sixth Workshop on Simulation (Санкт-Петербург, 2009), VI Всероссийской межвузовской конференции молодых ученых в СПбГУ ИТМО (Санкт-Петербург, 2009, диплом "За лучший доклад аспиранта на секции"), 6th Int. Conf. on Informatics in Control, Automation and Robotics (Милан, Италия, 2009), 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (Шанхай, Китай, 2009).

Результаты диссертации были частично использованы в работах по грантам РФФИ 05-07-90179-в, 09-04-00789-а и проектам "Система видео-' наблюдения на основе стереозрения" и "Разработка рандомизированного подхода к проблемам поиска схожих участков изображений в задачах стереозрения и отслеживания движения", которые победили в конкурсах СТАРТ-08 в 2008 г. и "У.М.Н.И.К." в 2009 году.

Основные результаты диссертации опубликованы в 32 работах [3-19, 40-42,45,87-92,94,99,114-116], среди которых [12-14] - в научных журналах перечня ВАК.

Работы [9-19,40-42,45,87-92,94,99,116] написаны в соавторстве. Соискателю принадлежат формулировки и доказательства основных теорем, имитационное моделирование. В работах [10,12-14, 87-92] O.H. Грани-чину принадлежат общие постановки задач, в [14] С.С. Сысоеву — формулировка алгоритма для квантовых вычислений; в [12,15,17,87,88,94] Л.С. Гуревичу — формулировки условий на нестационарность и теорема об оптимальном выборе размера шага, в [13,19,114,116] М.А. Пань-шенскову — анализ и реализация алгоритмов распределения загрузки вычислительных узлов и оценивания пропускной способности каналов данных, в [9,11,16,18,40-42,45,99] соавторам — постановки задач и обзоры подходов к их решению.

Диссертация состоит из введения, трех глав, заключения, приложения и списка литературы, содержащего 136 наименований. Включает 11 рисунков, 3 таблицы. Общий объем работы — 103 страницы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Вахитов, Александр Тимурович

Заключение

В диссертационном исследовании для задач оптимизации функционала типа среднего риска со статистическими неопределенностями с конечным моментом степени р G (1,2] и почти произвольной ограниченной аддитивной помехой наблюдения получены необходимые условия состоятельности, сильной состоятельности и стабилизации оценок, а также оценки скорости сходимости рандомизированных алгоритмов стохастической аппроксимации. Задачи оптимизации с такого типа неопределенностями появляются в моделях вычислительных систем, финансовой математики, биологического разнообразия, распространения вирусов, и пр. В диссертации разработана модель загрузки узлов распределенной вычислительной сети, использующая полученные в последние годы результаты об эмпирическом распределении размеров заданий с бесконечной дисперсией. Имитационное моделирование системы проиллюстрировало работоспособность рандомизированных алгоритмов стохастической аппроксимации в контуре обратной связи предложенной системы управления.

Перечислим основные результаты диссертации.

1. Для задач оптимизации функционала типа среднего риска со статистическими неопределенностями с конечным моментом степени р е (1,2] и почти произвольной ограниченной аддитивной помехой наблюдения установлены необходимые условия состоятельности (Теорема 1) и сильной состоятельности (Теорема 2) оценок РАСА в стационарном случае;

2. Для задач оптимизации функционала типа среднего риска со статистическими неопределенностями с конечным моментом степени р € (1,2] и почти произвольной ограниченной аддитивной помехе наблюдения получена асимптотическая оценка скорости сходимости РАСА (Теоремы 3,4);

3. Для задач оптимизации функционала типа среднего риска со статистичсскими неопределенностями с конечным моментом степени р € (1,2] и почти произвольной ограниченной аддитивной помехе наблюдения установлены необходимые условия стабилизации последовательности оценок и получено выражение для границы стабилизации РАСА в нестационарном случае (Теорема 5).

4. Разработана динамическая модель системы управления загрузкой узлов распределенной вычислительной сети, в которой случайный дрейф производительности процессоров имеет бесконечную дисперсию, а в контур обратной связи включены РАСА. Применимость РАСА подтверждается полученными теоретическими границами на время обработки пакета заданий (Теоремы 6-8) и имитационным моделированием. i

Список литературы диссертационного исследования кандидат физико-математических наук Вахитов, Александр Тимурович, 2010 год

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

2. Baxumoe А. Т. Методы балансировки загрузки для многопроцессорных систем // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 159-166.

3. Baxumoe А. Т. Адаптивное слияние результатов поиска изображений по содержанию // Стохастическая оптимизация в информатике. 2007. Вып. 3. С. 97-107.

4. Baxumoe А. Т. Балансировка Grid-вычислений методами стохастической оптимизации // Труды II школы-семинара молодых ученых "Управление большими системами". Воронеж, 2007. С. 115-120.i

5. Baxumoe А. Т. Оптимизация балансировки загрузки процессоров при паралелльном выполнении цикла // Материалы шестого научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах". С.-Петербург. 2007. С. 88-90.

6. Baxumoe А. Т. Адаптивное оценивание параметров в параллельных многопользовательских вычислительных системах // Стохастическая оптимизация в.информатике. 2008. Вып. 4. С. 139-150.

7. Baxumoe А. Т. Нестационарная стохастическая оптимизация рандомизированными алгоритмами в случае бесконечной дисперсии неопределенностей // Стохастическая оптимизация в информатике. 2009. Вып. 5. С. 24-39.

8. Вахитов А.Т., Вяххи Н.И., Петров А.Г. Грид-вычислсния в задаче Ant colony optimization: базовая архитектура приложения и адаптивное распределение заданий // Тр. конф. "Технологии Microsoft в теории и практике программирования". 2009. С. 62-65.

9. Вахитов А. Т., Граничил О. Н. Рандомизированные алгоритмы оценивания при нерегулярных помехах // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 3-37.

10. Вахитов А. Т., Граничина О.А. Алгоритмы классификации за минимальное число шагов // Стохастическая оптимизация в информатике. 2006. Вып. 2. С. 167-175.

11. Вахитов А. Т., Граиичин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. № 11. С. 70-79.

12. Вахитов А.Т., Граиичин О.Н., Панъшенсков М.А. Методы оценивания пропускной способности в распределенных системах // Нейрокомпьютеры: разработка, применение. N2 11. 2009. С. 45-53.

13. Вахитов А. Т., Граничии О. П., Сысоев С. С. Точность оценивания рандомизированного алгоритма стохастической оптимизации // Автоматика и телемеханика. № 4. 2006. С. 86-96.

14. Вахитов А. Т., Гуревич Л. С. Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации // Стохастическая оптимизация в информатике. 2008. Вып. 4. С. 36-47.

15. Вахитов А. Т., Гуревич Л. С., Павленко Д.В. Обзор алгоритмов сте-реозрения // Стохастическая оптимизация в информатике. 2008. Вып. 4. С. 151-169.

16. Baxumoo A. TКраснощекое В. E. Оптимизация выполнения заданий в GRID на основе адаптации // Материалы шестого научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах". С.-Петербург. 2007. С. 79-88.

17. Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. № 1(4). С. 19-21.

18. Граничин О.Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 88-99.

19. Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Проблемы передачи информации. 1992. № 2. С. 16-20.

20. Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 44-55.

21. Граничин О. Н.; Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. — М.: Наука. 2003. 291 с.

22. Ермаков С.М., Жиглявский А.А. Математическая теория оптимального эксперимента. — М.: Наука. 1987. 320 с.

23. Ермаков С. М., Жиглявский А. А. О случайном поиске глобального экстремума // Теория вероятностей и ее применения. 1983. Т. 28, № 1. С. 129-134.

24. Ермольев Ю.М. О методе обобщенных стохастических градиентов и стохастических квазифейеровских последовательностях // Кибернетика. 1969. № 2. С. 73-83.

25. Ермольев Ю.М. Методы стохастического программирования. — М.: Наука. 1976. 239 с.

26. Жиглявский А.А., Жилиискас А.Г. Методы поиска глобального экстремума. — М.: Наука. 1991. 248 с.

27. Зорин В.А. Математический анализ. Часть II. М: МЦНМО. 2002. 794 С.

28. Карлип С. Математические методы в теории игр, программировании и экономике,— М.: Мир. 1964. 836 с.

29. Карманов В.Г. Математическое программирование. — М.:ФИЗМАТЛИТ. 2004. 264 с.

30. Катковник В. Я. Метод операторов усреднения в итерационных алгоритмах решения стохастических экстремальных задач // Кибернетика. 1972. № 4. С. 123-131.

31. Катковник В.Я. Параметрические операторы усреднения в итерационных алгоритмах решения стохастических экстремальных задач. I. Операторы усреднения и статистические оценки // Автоматика и телемеханика. 1974. № 3. С. 67-75.

32. Катковник В.Я. Параметрические операторы усреднения в итерационных алгоритмах решения стохастических экстремальных задач. II. Итеративные алгоритмы оптимизации // Автоматика и телемеханика. 1974. № 4. С. 613-620.

33. Красулииа Т.П. О процессах стохастической аппроксимации с бесконечной дисперсией // Теория вероятностей и ее применения. 1969. Т. 14. № 3. С. 546-551.

34. Красулина Т.П. Об односторонней сходимости модифицированного процесса Роббинса-Монро при малых шагах // Вестник С.-ПетербургСкого Университета. Сер. 1. № 4. С. 67-72.

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

36. Коростелев А.П. Стохастические рекуррентные процедуры: локальные свойства. — М.: Наука. 1984. 208 с.

37. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклой оптимизации. — М.: Наука. 1987. 279 с.

38. Невелъсон Ы.В., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание. — М.: Наука. 1972. 304 с.

39. Нестеров Ю.Е. Метод решения задачи выпуклого программирования со скоростью сходимости О(р) // Докл. АН СССР. 1983. Т. 269, № 3. С. 543-547.

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

41. Поляк Б. Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. I. Общий случай // Автоматика и телемеханика. 1976. № 12. С. 83-94.

42. Поляк Б. Т., Цыбаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 26. С. 126-133.

43. Поляк Б.Т., Цыпкин Я.З. Псевдоградиентные алгоритмы адаптации и обучения // Автоматика и телемеханика. № 3. 1973. С. 45-68.

44. Поляк Б. Т., Щербаков П.С. Робастная устойчивость и управление.1. М.: Наука. 2002. 303 с.

45. Растригин Л.А. Статистические методы поиска. — М.: Наука. 1968. 369 с.

46. Сухарев AT. Минимаксные алгоритмы в задачах численного анализа. M.:URSS. 2009. 304 с.

47. Сысоев С. С. Рандомизированные алгоритмы стохастической оптимизации, квантовые компьютеры, искусственный интеллект // Стохастическая оптимизация в информатике. 2005. Вып. 1. С. 206221.

48. Фельдбаум А. А. О проблемах дуального управления //В кн.: Методы оптимизации автоматических систем. М.:Наука. 1972. с. 89108.

49. Фомин В.Н. Рекуррентное оценивание и адаптивная фильтрация- М.: Наука. 1984. 288 с.I

50. Фомин В.П., Фрадков А.Л., Якубович В.А. Адаптивное управление динамическими объектами. — М.: Наука. 1981. 448 с.

51. Харди Г.Г., Литлвуд Д.Е., Полиа Г. Неравенства. — М.:КомКнига, 2006. 456 с.

52. Юдин Д.Б. Математические методы управления в условиях неполной информации. — М.: Советское радио, 1974. 400 с.

53. Anderson D.P.,Cobb J., Korpela E., Lebofsky M., Werthimer D. SETIhome: an experiment in public-resource computing // Communications of the ACM. 2002. Vol. 45. No. 11. P. 56-61.

54. Astrom К. J., Wittenmark В. Adaptive control (2nd cd.) — Reading, MA: Addison-Wesley. 1995. 574 p.

55. Auguin M., Jalby W., Maillard J. Use of SIMD-SPMD machine for simulation in particle physics // Proc. Conf. on Computing in high energy physics. 1986. P. 355 362.

56. Babiker S., Asenov A., Barker J. R., Beaumont S. P. Finite element Monte Carlo simulation of recess gate compound FFTs // Solid-State Electronics. 1996. Vol. 39. No 5. P. 629-635.

57. Barabasi A.-LAlbert R. Emergence of Scaling in Random Networks // Science. 1999. Vol. 286. P. 509-512.

58. Benveniste A., Metiever M.} Priouret P. Adaptive algorithms and stochastic approximations. — Berlin-Heidelberg-New York: Springer-Verlag. 1990. 365 p.

59. Berger N., Borgs p., Chayes J., and Saberi A. On the spread of viruses in the Internet// Proc. SODA, 2005. P. 301-310.

60. Blum J.R. Multidimensional Stochastic Approximation // Ann. Math. Statist. 1954. Vol. 9. P. 417-425.

61. Bonomi F., Kumar A. Adaptive Optimal Load Balancing in a Nonhomogeneous Multiserver System with a Central Job Scheduler //' IEEE Transactions on Computers. 1990. Vol. 30. No. 10. P. 1239-1250.

62. Borkar V.S. Stochastic approximation: a dynamical systems viewpoint — New York: Cambridge University Press. 2008. 164 P.

63. Bidlo F., Cortez J., Martinez S. Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms. USA: Princeton University Press. 2009. 336 p.

64. Calafiore D., Campi M. Uncertain convex programs: randomized solutions and confidence levels // Mathematical Programming. 2005. Vol. 102. No. 1. P. 25-46.

65. Chen H.-F., Duncan Т. E., Pasik-Duncan B. A Kiefer-Wolfowitz algorithm with randomized differences. // IEEE Trans. Automat. Contr. 1999. Vol. 44. No. 3. P. 442-453.

66. Carlson J:, Doyle J. Highly optimized tolerance: A mechanism for power laws in designed systems // Physical Review. 1999. Vol. 60, No. 2. P. 1412-1427.

67. Carlson J.M., Doyle J. Complexity and robustness // Proc. Natl. Acad. Sci. U. S. A. 2002. Vol. 99 (Suppl. 1). P. 2538-2545.

68. Dobson I., Carreras A., Lynch VNewman D. Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization // CHAOS. 2007. Vol. 17, No. 2. P. 13.

69. Drapper P. S., Li Y. T. Principles of optimalizing control systems and an application to the internal combustion engine // ASME Publication. 1951. P. 160-168.

70. Dupac V. A dynamic stochastic approximation method // Ann. Math. Statist. 1965. Vol. 36, No. 6. P. 1695-1702.

71. Durlauf S. N. Complexity and Empirical Economics // Economic Journal. 2005. Vol. 115. No 504. P. 225-243.

72. Fabian V. Stochastic Appoximation // Optimizing Methods in Statistics. 1971. P. 439-470.

73. Flaxman A. D., Kalai A. T, McMahan H. B. Online convex optimization in the bandit setting gradient //' In Proc. SODA, 2005. P. 385-394.

74. Ferber J. Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence. Harlow: Addison Wesley Longman. 1999. 509 p.

75. Flynn M. Some Computer Organizations and Their Effectiveness // IEEE Trans. Comput. 1972. Vol. C-21. P. 948.

76. Foster I. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // Euro-Par 2001 Parallel Processing. 2001. P. 1-4.

77. Gabaix X., Gopikrishnan P., Plerou V., Stanley H.E. A theory of power-law distributions in financial market fluctuations // Nature.2003. Vol. 423. P. 267-270.

78. Granichin 0. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automatic Control.2004. Vol. 49. P. 1830-1835.

79. Granichin O., Gurevich L., and Vakhitov A. SPSA with a fixed gain for intelligent control in tracking applications //In Proc. of 2009 IEEE Int. Symp. on Intelligent Control. P. 1415-1420.

80. Granichin O.N., Vakhitov A.T. Architecture for artificial intelligence hybrid computing // Proc. of the 3rd Int. IEEE Scientific Conf. on Physics and Control. Potsdam, Germany. 2007. P. 181.

81. Granichin 0. N., Vakhitov A. T. SPSA-Based Adaptive control: accuracy of estimates // Proc. 9-th IFAC Workshop "Adaptation and Learning in Control and Signal Processing" (ALCOSP). 2007. P. 51.

82. Granichin O. N., Vakhitov A. T. Accuracy for the SPSA algorithm with two measurements // WSEAS Transactions on Systems. 2006. Vol. 5. No. 5. P. 953-957.

83. Guo L., Ljung L. Performance analysis of general tracking algorithms // IEEE Trans. Automat. Contr. 1995. Vol. 40. No 8. P. 1388-1402.

84. Gurevich L. S., Vakhitov A. T. SPSA algorithm for tracking //In Proc. of 12th Int. Student Olympiad on Automatic Control (Baltic Olympiad). P. 52-57.

85. Harchol-Balter M., Downey A.B. Exploiting Process Lifetime Distributions for Dynamic Load Balancing. Report No. UCB/CSD-95-887 University of California Berkeley. 1995. 19 p.

86. Jenkins S., Kirk S.R. Software architecture graphs as complex networks: A novel partitioning scheme to measure stability and evolution // Information Sciences. 2007. Vol. 177. No. 12. P. 25872601.

87. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function, // Annals of Mathematical Statistics. Vol. 23. No. 3. 1952. P. 462-466.

88. Killingback TDoebeli M. Self-organized criticality in Spatial Evolutionary Game Theory // Journal of Theoretical Biology. 1998. Vol. 191. No. 3. P. 335-340.

89. Krasnotcshekov V., Vakhitov A. Adaptive Scheduling and resource asessment in GRID //In Proc. of 9th Int. Conf. Parallel Computing Technologies. P. 240-244.

90. Krivulin N.K. Unbiased estimates for gradients of stochastic network performance measures // Acta Appl. Math. 1993. Vol. 33. P. 21-43.

91. Krstic M., Wang H.H. Stability of extremum seeking feedback for general nonlinear dynamic systems // Automatica. 2000. Vol. 200. P. 595-601.

92. Kushner H. J. , Yin G. Stochastic approximation and recursive algorithms and applications. — Springer. 2003. 474 p.

93. Lange K. Optimization. — Springer. 2004. 252 p.

94. Maeda Y., Kanata Y. Learning rules for rcccurent neural networks using perturbation and their application to ncurocontrol / / Transactions of IEE of Japan. 1993. Vol. 113. P. 402-408.

95. Matveev A., Savkin A. Estimation and Control Over Communication Networks. Springer, 2008. - 533 p.

96. Mitzenmacher M. A Brief History of Generative Models for Power Law and Lognormal Distributions // Internet Mathematics. 2004. Vol. 1. No. 2. P. .226-251.

97. Poznyak A. S., Tehickin D. O. Gradient procedures for stochastic approximation with dependent noise and their asymptotic behaviour // International Journal of Systems Science. 1985. Vol. 16. No. 8. P. 917949.

98. Robbins E., Monro S. A Stochastic Approximation Method // Annals of Mathematical Statistics. 1951. Vol. 22. No. 3. P. 400-407.

99. Sadegh P., Spall J.C. Optimal Random Perturbations for Stochastic Approximation using a Simultaneous Perturbation Gradient Approximation / / IEEE Transactions on Automatic Control. 1998. Vol. 43. No. 10. P. 1480-1484.

100. Schroeder В., Harchol-Balter M. Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness //In Proc. 9th IEEE Symposium on High Performance Distributed Computing (HPDC '00). 2000. P. 211-219.

101. Simon H. A. On a Class of Skew Distribution Functions // Biometrika. 1955. Vol. 42. No. 3/4. P. 425-440.

102. Spall J. C. Multivariate Stochastic Aproximation Using a Simultaneous Perturbation Gradient Aproximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332-341.

103. Spall J. C. A Stochastic aproximation technique for generating maximum likelihood parameter estimates, //' In Proc. of the American Control Conference. 1987. P. 1161-1167.

104. Spall J.C. Developments in stochastic optimization algorithms with gradient aproximations based on function measurements // In Proceedings of the Winter Simulation Conference. 1994. P. 207-214.

105. Spall J.C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. Vol. 33. No. 1. 1997. P. 109112.

106. Spall J. C. Introduction to Stochastic Search and Optimization. — New York: Wiley. 2003. 620 p.

107. Spall J.C., Cristion J.A. Model-Free Control of Nonlinear Stochastic Systems with Discrete-Time Measurements // IEEE Transactions on Automatic Control. 1998. Vol. 43. P. 1198-1210.

108. Sternby J. Adaptive control of extremum systems // Methods and Aplications in Adaptive Control. 2006. P. 151-160.

109. Vidyasagar M. Statistical learning theory and randomized algorithms for control // IEEE Control Systems. 1998. No. 12. P. 69-85.

110. Vijay Srinivas A., Janakiram D.,Venkateswar Reddy M. Avalanche Dynamics in Grids: Indications of SOC or HOT? // Frontiers in Artificial Intelligence and Applications. 2005. Vol. 135. P. 183-193.

111. Weiss G. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Cambridge: MIT Press. 1999. 619 p.

112. Yi Y., Song H., Zheng R., Xiao L. Scale-Free Property in Large Scale Object-Oriented Software and Its Significance on Software Engineering //In Proc. Second International Conference on Information and Computing Science. 2009. Vol. 3. P. 401-404.

113. Yule G. A Mathematical Theory of Evolution Based on the Conclusions of Dr. J.C. .Willis // F.R.S. Philosophical Transactions of the Royal Society of London (Series B). 1925. No. 213. P. 21-87.