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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

984602373

ВАХИТОВ Александр Тимурович

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ ПРИ НЕОПРЕДЕЛЕННОСТЯХ С БЕСКОНЕЧНЫМ ВТОРЫМ МОМЕНТОМ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург

2010

2 о (..'ДГ; 29'0

004602378

Работа выполнена на кафедре теоретической кибернетики математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

профессор ГРАНИЧИН Олег Николаевич

Официальные оппоненты: доктор физико-математических наук

ЩЕРБАКОВ Павел Сергеевич (Институт проблем управления имени В.А. Трапезникова РАН)

кандидат физико-математических наук, доцент КРИВУЛИН Николай Кимович (Санкт-Петербургский государственный университет)

Ведущая организация: Институт проблем машиноведения РАН

Защита состоится "_"_2010 года в_часов на заседании

совета Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 191023, Санкт-Петербург, наб. реки Фонтанки, д. 27.

С диссертацией можно ознакомиться в Научной библиотеке

им. М. Горького Санкт-Петербургского государственного университета

по адресу: 199034, Санкт-Петербург, Университетская наб., д.7/9.

Автореферат разослан "_"_2010 г.

Ученый секретарь

диссертационного совета Д 212.232.29, доктор физико-математических наук, профессор

В. М. Нежинский

Общая характеристика работы

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

В 50-е годы XX века для решения задачи стохастической оптимизации начинают использоваться методы стохастической аппроксимации Роббинса-Монро и Кифера-Вольфовица. Они были развиты в работах B.C. Боркара, М. Вазапа, Ю.М. Ермольева, Дж. Ина, В.Я. Катков-ника, Т.П. Красулиной, Г. Кушнера, М.Б. Невельсона, A.C. Немиров-ского, Ю.Е. Нестерова, A.C. Позняка, Б.Т. Поляка, Р.З. Хасьминского, Я.З. Цыпкина, В. Фабиана, В.Н. Фомина, A.JL Фрадкова, Д.Б. Юдина, В.А. Якубовича и др.

В работах М. Вадьясагара, Д. Галафиори, JI. Гао, О.Н. Граничина, М. Кампи, JI. Лыонга, Б.Т. Поляка, П.С. Щербакова и др. показана целесообразность использования в задачах оценивания рандомизированных алгоритмов, которые позволяют ускорить процедуры решения задач и устранить эффекты смещения. Рандомизированные алгоритмы стохастической аппроксимации (РАСА, в англоязычной литературе — SPS A, Simultaneous Perturbation Stochastic Approximation), были предложены в работах О.Н. Граничина, Б.Т. Поляка и А.Б. Цыбако-ва, Дж. Спалла, Х.-Ф. Чена, Т. Дункан и Б. Пасик-Дункан в конце 80-х, 90-х гг. XX в., развивая идеи методов случайного поиска, детально исследованных в русскоязычной литературе С.М. Ермаковым и A.A. Жиглявским, А. Жилинскасом, J1.A. Растригиным и многими

другими. О.Н. Граничиным в 1989-1992 гг. было показано, что эти алгоритмы работоспособны в условиях неизвестных ограниченных помех наблюдения (unknown but bounded). В задачах стационарной оптимизации Б.Т. Поляк и А.Б. Цыбаков в 1990 г. обосновали минимаксную асимптотическую оптимальность скорости сходимости оценок этих алгоритмов, в том смысле, что порядок ее не может быть улучшен никаким другим итеративным алгоритмом. Дж. Спаллом в 1992-1997 гг. была установлена оптимальность использования в качестве пробного возмущения распределения Бернулли и уменьшение количества измерений для получения оценки заданного качества по сравнению с процедурой Кифера-Вольфовица.

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

В последнее десятилетие методы управления и оптимизации нашли важное приложение в теории распределенных и мультиагентных систем, а также систем массового обслуживания, в работах Ф. Булло, Г. Вайса, X. Кортес, Н.К. Кривулина, С. Мартинез, A.C. Матвеева, A.B. Савкина, Ж. Фербера и др.

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

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

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

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

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

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

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

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

2. асимптотические оценки скорости сходимости РАСА (Теоремы 3,4);

3. необходимые условия стабилизации последовательности оценок и получено выражение для границы стабилизации РАСА в нестационарном случае (Теорема 5).

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

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

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

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

Апробация работы. Результаты работы докладывались на научных семинарах кафедр системного программирования и теоретической кибернетики СПбГУ, на Балтийских олимпиадах по автоматическому управлению в 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 Multi-conference 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 году. Публикации. Основные результаты диссертации опубликованы в работах [1-32], среди которых [1-3] — в научных журналах перечня ВАК.

Работы [1-4,6-10,14-21,24-27,30-32] написаны в соавторстве. Со-

искателю в них принадлежат формулировки и доказательства основных теорем, имитационное моделирование. В работах [1-4,8-10,30-32] О.Н. Граничину принадлежат общие постановки задач, в [1] С.С. Сысоеву — формулировка алгоритма для квантовых вычислений; в [2,19, 20,24,30,32] Л.С. Гуревичу — формулировки условий на нестационарность и теорема об оптимальном выборе размера шага, в [3,14,15,28] М.А. Паньшенскову — анализ и реализация алгоритмов распределения загрузки вычислительных узлов и оценивания пропускной способности каналов данных, в [6,7,16-18,21,25-27] соавторам — постановки задач и обзоры подходов к их решению.

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

Краткое содержание работы

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

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

Рассмотрим вероятностное пространство (Г2, .^Р) и дифференцируемую по первому аргументу функцию Р(х, и) : М? х 1У —► К, где И7 С Кр. Пусть в каждый момент времени п = 1,2,... в выбираемых экспериментатором точках измерения Х\,Х2,. • • (план наблюдения) доступно наблюдению с аддитивной помехой уп значение функции

Уп = Р(хп, го„) + уп,

где гу„ € V/ — неконтролируемая последовательность независимых случайных векторов, имеющих одинаковое, вообще говоря, неизвестное

распределение Р„;(-). В диссертации рассматривается задача о построении по наблюдениям г/i, J/2, • - ■ последовательности оценок {0п} неизвестного вектора в, минимизирующего функцию f{x) типа функционала среднего риска:

f{x) = E{F(x,w)\x} -> min. (1)

(Здесь и далее Е, £{•}, £{•)•} — символы математического ожидания (МО) и условного МО).

Обычно исследуется случай F(w. х) = f(x). Сделанное обобщение позволяет, например, учесть случай мультипликативной неопределенности: F(x,w) = wf(x) и Ew = 1.

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

Определение 1. Последовательность оценок {вп} величины в называется состоятельной, если Ve > 0 limn_^ooP{||ön — > б} = 0.

Определение 2. Последовательность оценок {0ц} величины в называется сильно состоятельной, если сходимость оценок к 0 выполняется с вероятностью единица 0п —» в при п —► оо.

Наряду с (1) в диссертации рассматривается и нестационарная постановка задачи. Пусть задано семейство функций {F^(x, дифференцируемых по первому аргументу, х\, X2,... — выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени п = 1,2,... доступно наблюдению с аддитивной помехой vn значение функции (хп, wn)

Уп = F(n{x„,w„) + vn,

где с,п — неконтролируемая последовательность, £п 6 S. Требуется по наблюдениям ух, Уг, ■ • • построить последовательность оценок {0п} неизвестных векторов {<9„}, минимизирующих функции f„(x) типа функционала среднего риска:

fn(x) = E{F6Sx,w)|rc} min. (2)

Задача (l) является частным случаем (2) при вп = в и Н = {£i}.

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

Определен и еЗ. Последовательность оценок {0п} имеет границу стабилизации Ь > 0 (стабилизируется) по отношению к последовательности {0П} С К?, если

Ш(Е]\ва-вп\)^1/"<Ь.

71—»ОО '

(Здесь и далее ||х - г\\р = И0 ~ , Ух,г € М? с компонен-

тами х®, г®, г = 1,..., д и р е (1,2]).

Рандомизированными называют те алгоритмы оптимизации, которые опираются на некоторые контролируемые случайные величины, влияющие на результаты наблюдений, существующие в системе или добавляемые экспериментатором. Обычно рандомизация процесса наблюдений позволяет повысить скорость работы алгоритма оптимизации в случае большой размерности и его устойчивость к помехам. Обозначим Ап пробное возмущение, п = 1,2,... и Рд„(-) — его распределение.

Пусть во £ Ж5 и задана последовательность {©„} выпуклых множеств 0П С К9, содержащих начиная с некоторого ./V > 0 точку/-и минимума/-ов функционала (1)/-ов (2). Например, {6П} — последовательность расширяющихся до бесконечности шаров. В диссертации рассматриваются свойства оценок следующих трех алгоритмов типа случайного поиска, сформулированных в четвертом разделе:

(Хп = вп-1 + Рп&п, Уп = Р(хП! №„) + ,

(3)

Оп = Гп(0п-! - ^/СП(Дп)уп),

{%2п = Оп-\ + (Зп&п, %2п-1 = Оп-\ - Рп&п,

(4)

вп = Рп{вП-1 - ^£п{&п)(У2п - У2п-1)),

%2 п = &п-1 + |ЗпАп, %2п-1 =

' . . (5)

А = Тп{Оп-1 - %£п(Ап){у2п - угп-д),

где Тп — проекторы на 0П, причем для алгоритма (3) вп — компакты, а /Сп(-) : М.9 —>■ М.9 — некоторые вектор-функции (ядра), например, Кп{х) = х.

В пятом разделе описаны две теоретические модели: высокоопти-мизированной толерантности и присоединения с предпочтением, — соответствующие ряду практически значимых задач со статистическими неопределенностями без конечного второго момента, но с конечным моментом степени р £ (1,2].

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

(A) Сильная выпуклость /(х) в точке минимума. Для х, в е 6га, существуют р,п> О такие, что

(B) Ограниченность скорости изменения градиента

ЗМН > 0 : Ух, у 6 еп \\VFix,«;) - ЧР(у, ш)||„ < М(ю)\\х - уЦт Е\М{ш)\1 < М4 < оо, где 0 < -у < 1, ¿=р-1;р.

(C) Условие перестановки операторов интегрирования и дифференцирования для Р(х,т) и т).

Ух,3 окрестность их : Мх' е 11х \Р{х',ги)| + < $1(10), где

Фг(и>) /¡уФх(и>)Р„(<1п) < оо.

(О) Ограниченность моментов Р(х, и) и ||г1>)\\р в точке минимума. Е\Р(в,и))\р +\\Т7хР(в,и))\\рр < оо.

(Е) Ограниченность колебаний функции F в последовательные моменты времени. При разных значениях ш для всех х 6 0„ изменение функции Р(х, •) в моменты времени пип + 1 ограничено с вероятностью 1 следующим образом:

™п) ~ -^„-.(я, »„-1)1 < гуп_ 1)||ж - вп\\р + и!®{у)п, 11<п-1),

где функции С/п^(го„, «/'„_!), е = 1,2 имеют равномерно ограниченные моменты степени 4 £ = 1,р — 1,р, й = 1,2 соответственно. (Е) Ограниченность дрейфа точек минимума: \\вп - < Л,

либо при случайной природе дрейфа {тои} не зависит от {£„} и

над - < а, Е\\вп - вп-1\\ьр <АиЬ = р-1-р.

(G) Условия на помеху наблюдения vn. |(п| < где (n = vn для

алгоритма (3) или (п = V2n — V2n~i Для (4)-(5). При случайной природе, не зависит от Ап и Е]С„| < av%n, ■E|Cn]'> <

Заметим, что vn м.б. зависимы либо неслучайны и ограничены.

(H) Условия на пробное рандомизированное возмущение. Уп € N случайные величины Дп независимы с ет-алгеброй порожденной случайными величинами ..., Дп-ъ во,..., f?„_ i, w\,wmn, (m = 1 для алгоритма (3), m = 2 для (4)-(5)) и fi,...,fmn> если рассматривается нестационарная постановка задачи и дрейф случайный. Для распределений Рд„(-) и вектор-функций /С„(-) выполняются условия симметричности f }Сп(х)Рдп((1х) = 0, взаимной независимости компонент f JCn(x)^x^P&n(dx) = 0 при г ^ j и 1 при г = j, ограниченности supn / ||£п(я)||2||:г||£||х||^.Рдп(ск) < оо для а = 1 ;р, 6 и с = 0; — 1; р.

(I) Условия на размеры шагов алгоритмов. ап, (Зп > 0,

> а„ц„ = оо,ап+(Зп+апцп+--► 0, грп = -тгг +

*—•' II— П—>00

п=1

Мп /4 №

¿п = 1 + а1ат/)(0п)-'" для (3) или (1п = + и®р для (4) и (5).

Далее во втором разделе приводятся примеры задач, удовлетворяющих условиям (А)-(Н).

В разделе 2.3 диссертации сформулированы теоремы, описывающие поведение оценок алгоритмов (3)-(5) в стационарном случае.

Теорема 1. Если выполнены условия (А) для /(х), (В)-(Е) для F(.т, ю), а также (С)-(1), тогда оценки алгоритмов (3)-(5) являются состоятельными и Е\\9п — в\\р,—»0 при п

оо.

Теорема 2. Если выполнены условия Теоремы 1 и

оо

^Г^ апЕ{^)п\вп-1, Д„_1, Рп-х} < оо с вероятностью 1,

71=1

тогда оценки алгоритмов (3)-(5) являются сильно состоятельными.

В четвертом разделе для характеристики скорости сходимости {9п} вводятся специальные последовательности

фп ( Чп Л 1 , Л 7?п+Л 1

Пп = —, Рп =--1 —:■ Рп = 1---.

\Пп+1 V Чп уп+\

vn = anßn{ 1 - Л) - а^Кр, фп = + anLpn, в которых А € (0; 1) -произвольная константа, а Кр, LJ]V Lp определяются из условий (А)-(1).

Теорема 3. Если выполнены условия Теоремы 1, а также для всех п выполнено неравенство 0 < vn < 1, и

1. lim р„ < р < 1, то Е\\вп - 0П||£ < ^ + о(7]п);

П—»0O ' У

2. Vnpn<p< 1, то Е\\вп - вп\\р < + (^ülS - ^ ПГ=о(1 -(1 -рШ

3. lim р'п > р> > 1, то Е\\в„ - 9п\\р = 0(П?="о(1 - "дУ,

Т1—>00 г

4. Vn р'п > р> > 1, то Е\\вп - вп% < {Е\\ёй - <90||> + ffl ПГ=о (1 - щ)-Пусть q, ß > О, Д, d > О,

а„ ~ an-", /?„ ~ ßn~ß, ßn ~ crpn ~ стп^, diamp(9n) ~ dnd (6)

и обозначим к = min{p(ä — ß — v), p(ä — d-y), а + ßpj — ц(р — 1)} для алгоритма (3) или к = min{p(ä — ß — v),ä + ßp/y — ß(p — 1)} для (4),(5).

Теорема 4. Пусть выполнены условия Теоремы 1 и (6). 1. Если й + ß = 1, тогда

lim nV(£||0n - е\\рЛ'р < оо, при ац( 1 - Л) > к - 1,

п—>оо ^

Hm - < оо, при а/х(1 - Л) = к - 1,

lim EVT0^1"^!?« - < оо, при ац{1 - Л) < к - 1.

ге—»ос

Если же а + Д < 1, то lim - Q\\p)~? < оо.

П—>00 р

В пятом разделе сформулирована теорема о стабилизации оценок в нестационарном случае.

Теорема 5. Пусть цп = д > 0, размеры шагов постоянны: ап = а, ßn = ß, и равномерно по п выполнены условия (А) для f„{x), (В)-(Е) для F^(x,wn), (F) для дрейфа минимума, (G) для аддитивных помех наблюдения, (Н) для рандомизированного возмущения. Если ЗА > 0 : К = (1 + тА{р - 1)А)(1 - ас{) 4- аАс2 + а"с3 6 (0,1), то

Е\\вп - втп\\р < КпЕ\\90 - воГр + (1 - ^YZjc'

где Ь = С4+аС5-(-о:/'(сб+С7а^), Сь ..., С7 — константы определяемые по условиям (А)-(1), и последовательность оценок {9п} имеет границу

В шестом разделе приведены доказательства Теорем 1-5, при этом Теоремы 1 и 5 вызвали наибольшие трудности при доказательстве.

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

В первом разделе сформулирована постановка задачи управления загрузкой узлов распределенной вычислительной сети. Пусть в системе имеется г/ узлов. Шаг работы системы заключается в обработке пакета заданий известного размера гп. Предположим, что весь пакет может быть произвольным образом разделен на ц заданий для узлов, при этом узел г получает задание размером и„\ г = 1, 2,..., д, ^1=1 = гп-Время вычисления для узла г определяется по формуле =

&п

где е Ж — производительность узла г. Необходимо минимизировать

/ (1) (2) («)\т по ип = (и„ ,и„ ,..., и„) среднее время вычисления задания пакета

При введенных обозначениях, если производительности узлов известны и не меняются 9п = 9, тогда оптимальным является правило пропорционального распределения заданий (Теорема 6).

На практике производительности узлов могут быть искажены из-за сторонних заданий, т. е. вп = в + гу„ — \юп , либо изменяться со временем: вп = 9„-\ + £„, где £„, ц}„ € Ж® - векторы независимых случайных величин, распределенных по Парето. В р. 3.2 диссертации обоснована целесообразность использовать контур обратной связи, в который включен РАСА для идентификации или отслеживания изменений 9п.

Далее в разделе 3.3 формулируются Теоремы 7 и 8, оценивающие отклонение среднего времени на выполнение одного пакета заданий от оптимального при использовании РАСА в стационарной и нестационарной задаче. При этом в качестве наблюдений используются величины

стабилизации, равную Ь = тгр-

Т(ип)

тах -

¿=1,...,? гп

тт.

"г.

которые в силу выбранной стратегии управления являются зашумлен-ными измерениями функции fn(x) = \\вп — х\\рр. Доказательства Теорем 7 и 8 даны в последнем разделе.

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

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

Публикации автора по теме диссертации:

Статьи в журналах, рекомендованных ВАК:

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

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

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

Другие публикации:

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

- СПб.: Изд-во СПбГУ. 2006. - С. 3-37.

[5] Вахитов А.Т. Методы балансировки загрузки для многопроцессорных систем // Стохастическая оптимизация в информатике. Вып. 2. — СПб.: Изд-во СПбГУ. 2006.

- С. 159-166.

[6] Вахитов А.Т., Граничина O.A. Алгоритмы классификации за минимальное число шагов // Стохастическая оптимизация в информатике. Вып. 2. — СПб.: Изд-во СПбГУ. 2006. - С. 167-175.

[7] Лобанов А.Л., Кирейчук А.Г., Смирнов И.С., Граничин О.Н., Вахитов А.Т., Ди-анов М.В. К реализации идеального интерактивного определителя биологических объектов в интернете // Сб. тр. Всерос. научн. конф. "Научный сервис в сети Интернет" - Новороссийск. 2006. - С. 202-204.

[8] Granichin O.N., Vakhitov А.Т. Accuracy for the SPSA algorithm with two measurements // WSEAS Transactions on Systems. - 2006. - Vol. 5. No. 5. - P. 953-957.

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

[10] 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.

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

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

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

[14] Panshenskov М., Vakhitov A. Adaptive scheduling of parallel computations for SPMD tasks // Proc. of Int. Conf. on Computational Science and Its Applications - ICCSA.

- Kuala Lumpur, Malaysia. 2007. - P. 38-50.

[15] Baxumoe А. Т., Панъшенсков M. А. Автоматизированные вычисления в Grid: адаптивная балансировка // Тр. конф. "Технологии Microsoft в теории и практике программирования". — С.-Петербург. 2007. — С. 155.

[16] Вахитов А. Т., Краснощекое В.Е. Оптимизация выполнения заданий в GRID на основе адаптации // Тр. VI сем. "Высокопроизводительные параллельные вычисления на кластерных системах". - С.-Петербург. 2007. - С. 79-88.

[17] Krasnotcshekov V., Vakhitov A. Adaptive scheduling and resource assessment in GRID // Proc. of 9th Int. Conf. Parallel Computing Technologies. — Pereslavl-Zalessky, Russia. 2007. - P. 240-244.

[18] Лобанов А.Л., Кирейчук А.Г., Baxumoe A.T., Граничин O.H. Алгоритмы построения вопросника минимальной длины для биологического определителя в Интернет и успехи в их реализации // Сб. тр. Всерос. научн. конф. "Научный сервис в сети Интернет" - Новороссийск. 2007. - С. 321-323.

[19] Gurevich L.S., Vakhitov A.T. SPSA algorithm for tracking // Proc. of 12th Int. Stud. Olymp. on Automatic Control (Baltic Olympiad). - St. Petersburg. 2008. - P. 52-57.

[20] Baxumoe A.T., Гуревич Л.С. Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации // Стохастическая оптимизация в информатике. Вып. 4. — СПб.: Изд-во СПбГУ. 2008. — С. 36-47.

[21] Вахитов А.Т., Гуревич Л.С., Павленко Д.В. Обзор алгоритмов стереозрения // Стохастическая оптимизация в информатике. Вып. 4. — СПб.: Изд-во СПбГУ. 2008.

— С. 151-169.

[22] Вахитов А.Т. Адаптивное оценивание параметров в параллельных многопользовательских вычислительных системах // Стохастическая оптимизация в информатике. Вып. 4. - СПб.: Изд-во СПбГУ. 2008. — С. 139-150.

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

[24] Вахитов А.Т., Гуревич Л.С. Метод стохастической аппроксимации с пробным одновременным возмущением на входе в задаче отслеживания минимума нестационарного функционала // Тр. XI конф. мол. уч. "Навигация и управление движением". — С.-Петербург. 2009. - Режим доступа: http:/ /www.elektropribor.spb.ru/cnf/kraul 1 /rrefs.html, свободный.

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

[26] Лобанов А.Л., Кирейчук А.Г., Вахитов А.Т., Граничин О.Н. Параллельный алгоритм обучения для интерактивного политомического определителя биологических видов // Сб. тр. Всерос. научн. конф. "Научный сервис в сети Интернет." — Новороссийск. 2009. - С. 332-334.

[27] Немнюгин С. А., Вахитов А. Т., Граничин О.Я., Кияев В.И. Об опыте деятельности лаборатории СПРИНТ СПбГУ по подготовке ИТ-специалистов в области высокопроизводительных вычислений // Сб. тр. Всерос. научн. конф. "Научный сервис в сети Интернет" -- Новороссийск. 2009. —■ С. 440-443.

[28] Panshenskov М., Vakhitov A. TYansfer speed estimation for adaptive scheduling in the data grid // Proc. of Grid and Pervasive Computing Conf. — Geneva, Switzerland. 2009. - P. 58-63.

[29] Panshenskov M., Vakhitov A. Methods of linear transfer speed estimation in the data grid // Proc. of 1st ACM workshop on Data grids for eScience, Conf. On Computing Frontiers. - Ischia, Italy. 2009. - P. 29-34.

[30] Granichin O., Gurevich L., Vakhitov A. SPSA with a fixed gain for intelligent control in tracking applications // Proc. of IEEE Int. Symp. on Intelligent Control. — St. Petersburg. 2009. - P. 1415-1420.

[31] Granichin O., Gurevich L., Vakhitov A. Minimum tracking with SPSA and applications to image registration // Proc. of 6th Int. Conf. on Informatics in Control, Automation and Robotics, - Milan, Italy. 2009. - P. 66-74.

[32] Granichin O., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of 48th IEEE Conf. on Decision and Control. — Shanghai, P.R. China. 2009. — P. 5763-5767.

Подписано к печати 21.04.10. Формат 60 *84 1/16 . Бумага офсетная. Гарнитура Тайме. Печать цифровая Печ. л. 1,0. Тираж 100 экз. Заказ 4729. Отпечатано в Отделе оперативной полиграфии Химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-40-43,428-69-19

Введение.

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

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.