научная статья по теме К ПРЕДЕЛЬНОМУ ОПИСАНИЮ РОБАСТНОГО ПАРАЛЛЕЛЬНОГО УПРАВЛЕНИЯ В СЛУЧАЙНОЙ СРЕДЕ Автоматика. Вычислительная техника

Текст научной статьи на тему «К ПРЕДЕЛЬНОМУ ОПИСАНИЮ РОБАСТНОГО ПАРАЛЛЕЛЬНОГО УПРАВЛЕНИЯ В СЛУЧАЙНОЙ СРЕДЕ»

Автоматика и телемеханика, № 7, 2015

© 2015 г. А.В. КОЛНОГОРОВ, д-р физ.-мат. наук (Alexander.Kolnogorov@novsu.ru) (Новгородский государственный университет им. Ярослава Мудрого)

К ПРЕДЕЛЬНОМУ ОПИСАНИЮ РОБАСТНОГО ПАРАЛЛЕЛЬНОГО УПРАВЛЕНИЯ В СЛУЧАЙНОЙ СРЕДЕ1

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

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

есть управляемый случайный процесс, значения которого интерпретируются как доходы, зависят только от выбираемых в текущие моменты времени вариантов и имеют нормальные распределения с плотностями /(х| т,() = = (2п)-1/2 ехр{—(х — т()2/2}, если применен вариант с номером I (I = 1, 2). Такая среда описывается векторным параметром 9 = (т1,т2), множество допустимых значений которого имеет вид ©^ = {(т1,т2) : |т1 — т2| ^ ^ 2сЖ-1/2;0 < с < то}, т.е. рассматриваются среды с единичными дисперсиями и близкими математическими ожиданиями.

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

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

1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 13-01-00334а) и Программы стратегического развития Новгородского государственного университета им. Ярослава Мудрого.

1. Введение

где Л - некоторое априорное распределение на • Предметом исследования статьи является минимаксное (и, следовательно, робастное) управление, которое в силу основной теоремы теории игр ищется как байесовское, соответствующее наихудшему априорному распределению.

Дадим интерпретацию рассматриваемой постановки в приложении к управлению обработкой больших объемов данных. Будем считать, что поступающие на обработку данные разбиваются на партии одинакового объема. Для обработки данных в каждой партии может использоваться один из двух альтернативных методов обработки (вариантов), имеющих разные, априори неизвестные вероятности успешной и неуспешной обработок. Тогда £га есть количество успешно обработанных данных в п-й партии. В силу центральной предельной теоремы распределения будут близки к нормальным уже

при небольших объемах партий, например, партий из двадцати данных.

Требование близости математических ожиданий {£„} может быть обеспечено практически без увеличения полных потерь на начальном этапе при обработке сравнительно небольшой партии данных. В [1] предложена эвристическая процедура, которая в случае методов с сильно различающимися эффективностями выделяет лучший метод уже на начальном этапе и применяет его ко всем оставшимся данным. А в случае методов с близкими эф-фективностями процедура на оставшемся горизонте управления использует изучаемую в данной статье стратегию. При этом на начальном этапе делаются оценки дисперсий {£га}, которые будут близки для методов с близкими эффективностями; соответствующей нормировкой можно добиться того, что дисперсии будут близки к единице. Отметим также, что максимальные полные потери достигаются именно для сред с близкими распределениями доходов; численные эксперименты в [1] показали, что максимальные потери достигаются при |т1 — т21 ~ 3,4Ы-1/2.

Цель данной статьи - асимптотическое описание минимаксного управления. Структура статьи следующая. В разделе 2 приведено инвариантное интегро-разностное уравнение, полученное в [2]. В разделе 3 установлены пороговый характер и некоторые предельные свойства стратегии. В разделе 4 дано предельное описание инвариантного интегро-разностного уравнения дифференциальным уравнением в частных производных второго порядка. В разделе 5 даны результаты численных экспериментов: сравнительный анализ решений интегро-разностного и дифференциального уравнений. Обсуждение результатов содержится в заключении.

2. Интегро-разностное инвариантное уравнение

Оказывается [1, 2], что практически без потери качества управления, т.е. без увеличения минимаксного риска, можно ограничиться стратегиями, допускающими параллельную обработку: сначала оба варианта применяются по Мо = еоЫ раз, а затем варианты могут меняться только после применения М = еЫ раз подряд (при М0 = М = 1 получаем обычное управление). Вместо применения варианта М раз подряд можно осуществлять параллельную обработку М данных.

Замечание 1. Эти стратегии могут использоваться и для управления обработкой больших объемов данных, рассмотренной в разделе 1. При этом начальный этап управления, на котором обрабатываются 2еоЖ данных, может использоваться для проверки близости эффективностей методов обработки и оценки дисперсий для последующей нормировки доходов. В этом случае обработка на начальном этапе сложнее; в [1] приведена одна эвристическая процедура, обеспечивающая эту обработку. Отметим, что вопрос об организации обработки на начальном этапе пока почти не исследован и в этой статье он не рассматривается.

Минимаксное управление в силу основной теоремы теории игр ищется как байесовское, соответствующее наихудшему априорному распределению. Положим т1 = т + V и т2 = т — V, тогда 9 = (т + V, т — V) и в^ = [в : |V| ^ ^ сЖ-1/2}. В новых переменных асимптотически наихудшая плотность распределения может быть выбрана в виде = ка(т)р^), где ка(т) -постоянная плотность при |т| ^ а, р^) = р(—V) - симметрическая плотность и a ^ то. Пусть к моменту времени п = п + п2 оба варианта применены соответственно п и п раз, а XI, Х2 - полные доходы за их применение. Следствием указанного вида априорной плотности распределения является то, что байесовское управление в момент времени п полностью определяется статистикой (и, п1,п2), где V := (Х1п2 — Х2п1)п-1. Обозначим через /о(х) := (2п^)—1/2 ехр(—ж2/(2^)) - плотность нормального распределения. В [2] установлены следующие результаты, которые сформулируем в виде теоремы 1.

Теорема 1. Положим и = иЖ-1/2, ¿1 = п1Ж— 1, £2 = п2Ж—1, £ = ¿1 + £2, ш = vN1/2, £>(ш) = N-1/2р^). Оптимальная стратегия при £ ^ 2е0 (п ^ ^ 2е0Ж) применяет варианты по очереди. Далее она определяется рекур-рентно «с конца», т.е. следует решать уравнение, реализующее принцип оптимальности Беллмана:

(1) ге(и,£1,£2) = г£1)(и,£1,^2), где г^1)(и, £1, £2) = г£2)(и, £2) = 0 при £ = 1 и далее

г^1)(и,£1,£2) = ^(1)(и,£ь£2) + У г£(ж,£1 + е, ¿2)/£424-1(4+£)-1 (и — ж)^ж,

—те

(2)

те

г£2)(и,£ь£2) = ^(2)(и, ¿1^2) + У г^ж,^^ + е)/£ф-1 (*+£)-1 (и —

—те

при £ < 1, причем

с

g(l)(u,íl,í2) = J2w ехр((—1)12иш — 2ш2г^-^ I = 1, 2.

0

Текущим оптимальным при t > 2ео (n > 2e0N) является 1-й вариант, если меньшее значение имеет (u, ti, t2). Байесовский риск, соответствующий асимптотически наихудшему распределению, вычисляется по формуле

(3) N-i/2 lim RN(v„(m, v)) = 2Z(ß, ео) + re(ß, ео),

а—те

c те

2i(i>, ео) = 4ео Jг£(^,ео) = J r£(u,eo,ео)/о,5£0(u)du

0 -те

- потери на начальном (t ^ 2ео) и заключительном (t > 2ео) отрезках управления.

При этом при всех u, ti, t2, для которых определены решения уравнений (1) и (2), существуют пределы r(u, ti;t2) = lim r£(u, ti, t2), кото-

£—^о

рые могут быть доопределены по непрерывности на все u, ti > 0 и t2 > 0 (ti + t2 < 1). Эти пределы равномерно ограничены и удовлетворяют условиям Липшица по u при всех u, ti, t2.

Из теоремы 1 следует, что управление будет близким к оптимальному, если ео и е достаточно малы.

3. Свойства стратегии

Установим важное свойство стратегии - ее пороговый характер, т.е. существование такой функции T£(ti,t2), что первый и второй варианты следует выбирать при выполнении неравенств u > T£(ti,t2) и u < T£(ti,t2) соответственно. Это свойство позволяет существенно упростить описание стратегии. Но сначала установим свойство симметричности функций {r£(u,ti,t2)}, которое позволяет вдвое сократить объем вычислений по формулам (1)-(2). Лемма 1. При всех допустимых u, ti, t2 справедливы равенства:

(4) r£(u,ti,t2)= r£(-u,t2,ti), r£l)(u,ti,t2) = r£l)(-u,t2,ti),

1 = Z-i, ¿ = 1,2.

Доказательства леммы 1 и последующих лемм 2, 3, П.1-П.3 и теорем 2 и 3 приведены в Приложении.

Равенства (4) имеют следствием симметричность оптимальной стратегии. Перейдем к проверке порогового свойства стратегии. Положим Ar£(u, ti, t2) = = r£i)(u, ti, t2) — r£2)(u, ti, t2). Ясно, что критериями выбора первого и второго вариантов являются условия Ar£(u,ti,t2) < 0 и Ar£(u,ti,t2) > 0. Обозначим также F+(-) := max(F(■), 0), F-(-) := max(—F(■), 0), так что F(■) = F+(■) —

— F-(-), причем F+(-) ^ 0, F-(-) ^ 0. Справедлива теорема 2.

Теорема 2. При е> 0 и ti + t2 ^ 1 — е справедливы равенства

(5) Ar£(u,ti,t2) = —еF£(u,tl,t2),

где Ре(и, ¿1, _ монотонно возрастающая функция и такая, что Ре(-то, ¿1, ¿2) = —то, Ре(+то, ¿1, ¿2) = +то. При ¿1 + ¿2 = 1 — е функция равна

(6) Ре(и, ¿1, ¿2) = ^Уехр(—2w2í1í2í 1)

а при £ ^ 1 — 2е имеет вид Ре(и, ¿1, ¿2) = Р£(1) (и, ¿2) — Ре(2)(и, ¿2), где

(7)

Р+е (ж,*1 + е^Ш ¡*-1(*+е)-1 (и —

— те

42) («, , « = / Р—.(X, (1, ^ + е)/.,,(-1(1+«)-, (и —

— те

Здесь Р(1) (и, £ 1, £2) > 0, Ре(2) (и, ¿2) > 0, причем Ре(1) (и, £1, £2) монотонно (2)

возрастает, а монотонно убывает по и, так что

Р(1)(—то, ¿1, ¿2) = 0, р(1)(+то, ¿1, £2) = +то, Р(2) (—то, ¿1, £2) = +то, Ре(2) (+то, ¿1, ¿2) = 0.

Замечание 2. Критериями выбора первого и второго вариантов являются, таким образом, условия Ре(и, ¿1, ¿2) > 0

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком