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

• Автор: Вахитов, Александр Тимурович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Санкт-Петербург
• Количество страниц: 103 с.

Оглавление
Введение

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 Доказательства теорем
3 Система управления загрузкой узлов распределенной вычислительной сети
3.1 Задача загрузки узлов распределенной сети
3.2 Управление с обратной связью
3.3 Имитационное моделирование
3.4 Доказательства теорем 7
Заключение
Литература

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

СА, в англоязычной литературе — SPSA, Simultaneous Perturbation Stochastic Approximation), были предложены в работах О.Н. Граничина [20J, Б.Т. Поляка и А.Б. Цыбакова [49], Дж. Спалла [125,126] в конце 80-х, начале 90-х гг. XX в., развивая идеи методов случайного поиска, детально исследованные в русскоязычной литературе С.М.Ермаковым и А.А.Жиглявским [25,26], А.Жилинскасом [29], Л.А.Растригиным [52] и др. О.Н. Граничиным в 1989-1992 гг. было показано, что эти алгоритмы работоспособны в условиях неизвестных ограниченных помех наблюдения (unknown but bounded) [20,22]. В задачах стационарной оптимизации Б.Т. Поляк и А.Б. Цыбаков в 1990 г. обосновали минимаксную асимптотическую оптимальность скорости сходимости оценок этих алгоритмов, в том смысле, что порядок ее нс может быть улучшен никаким другим итеративным алгоритмом [49|. Дж. Спаллом в 1992-1997 гг. была установлена оптимальность использования в качестве пробного возмущения распределения Бернулли и уменьшение количества измерений для получения оценки заданного качества по сравнению с процедурой Кифера-Вольфовица [122,127,128].
Несмотря на большое количество публикаций по исследованию свойств оценок алгоритмов типа SPSA, теоретическая обоснованность их использования в целом ряде важных практических приложений до последнего времени существенно ограничивалась предположениями об ограниченности второго момента у неопределенностей. С.С. Сысоевым в 2005 г. была обоснована в частном случае состоятельность рандомизированного алгоритма стохастической аппроксимации с одним измерением при существовании конечного момента степени р G (1; 2] [54].
В последнее десятилетие методы управления и оптимизации нашли важное приложение в теории распределенных и мультиагентных систем, а также систем массового обслуживания, в работах Ф. Булло, X. Кортес и С. Мартинез [71], Г. Вайса [134], Н.К. Кривулина [100], А.С. Матвеева и А.В. Савкина [107], Ж. Фербера [82] и др.
Цель работы — исследование свойств оценок рандомизированных алгоритмов стохастической аппроксимации в стационарном и нсстационар-
УигК0(п)=0, г = 2
J К[и)йи = 1, У итК(и)йи = 1, г = 1
Одним из способов построения таких ядер является их выбор на основе ортогональных полиномов Лежандра.
Ядра выбраны таким способом, чтобы для функции /(ж), имеющей I непрерывных частных производных, было выполнено равенство
г1 [ 1Сп(и) Е-Пк/{х)ик(ЗЧи = V/(ж),
ц<1
где и имеет носитель [—0, 5; 0, Б]9, к - мультииндекс, а Пк/(х) - частная производная, ему соответствующая.
Для такой функции имеет место оценка
ия?) - Е - *)*и < - *и7+г>
|л|<г
для некоторого 7 € (0; 1].
Из приведенных равенств вытекает, что, делая рандомизированное измерение Л_1/(ж+/ЗД) в точке ж+/ЗД, где Д равномерно распределено в кубе [—0,5; 0,5]9, в среднем значение измерения отличается от значения градиента функции У/(ж) на величину порядка /Зг+7. Используя этот факт, авторы [49] обосновывают скорость следующую асимптотическую сходимости аналогичных (1.13)-(1.14) методов для всякой функции /(ж) с описанными выше свойствами:
8ир£||(9„ — в\2п 1+~1 < оо,

а также доказывают ее асимптотическую максимальность в минимаксном смысле.
При I = 1 аналогичная точность аппроксимации градиента достигается при использовании бернуллиевских величин. Более того, для доста-