Автоматика и телемеханика, № 6, 2014
Стохастические системы, системы массового обслуживания
© 2014 г. А.В. НАЗИН, д-р физ.-мат. наук (nazine@ipu.ru), С.В. АНУЛОВА, канд. физ.-мат. наук (anulovas@ipu.ru), А.А. ТРЕМБА, канд. физ.-мат. наук (atremba@ipu.ru) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
АЛГОРИТМ ЗЕРКАЛЬНОГО СПУСКА ДЛЯ МИНИМИЗАЦИИ СРЕДНИХ ПОТЕРЬ, ПОСТУПАЮЩИХ ПУАССОНОВСКИМ ПОТОКОМ1
Для стохастической системы, функционирующей в непрерывном времени, рассматривается задача минимизации ожидания интегральных потерь на заданном горизонте. Потери происходят в моменты скачков пуас-соновского процесса и являются непрерывной выпуклой функцией управляющего параметра, значения которого образуют выпуклый компакт в конечномерном пространстве. В моменты скачков оракул выдает стохастически зашумленные субградиенты функции потерь, ограниченные в среднеквадратическом; шум аддитивный, несмещенный. Предлагается стратегия управления, порожденная алгоритмом зеркального спуска. Для нее доказана явная верхняя граница превышения ожидания интегральных потерь над минимумом. Рассмотрен пример, в котором эта стратегия применена к модели массового обслуживания.
1. Введение
Алгоритм зеркального спуска (ЗС) представляет собой нетривиальное обобщение стандартного метода градиента для задач выпуклой оптимизации в условиях априорной неопределенности [1]. В ряде случаев он имеет преимущество перед другими алгоритмами поиска экстремума при высокой размерности: его гарантируемая скорость сходимости значительно выше. Это ярко выражается и в прикладных задачах, таких, например, как томография [2], классификация [3] и ранжирование [4].
Первоначальная идея метода ЗС описана в [1] в непрерывном времени, но сами алгоритмы как в [1], так и в последующих работах по ЗС представлены в дискретном времени. Мотивация данной статьи — расширить область применения алгоритмов зеркального спуска к стохастическим системам со
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект №12-08-01245). Первый автор также частично поддержан лабораторией ПреМоЛаб при МФТИ (ГУ), грант Правительства РФ №11.034.31.0073.
случайным дискретным временем, связанным с наблюдаемым пуассоновским потоком интенсивности Л. Основным результатом является явная неасимптотическая верхняя граница для превышения минимизируемой функции в текущей оценке над минимумом; при этом оказывается, что заданный горизонт времени Т умножается на интенсивность Л. В частности, в задаче выпуклой минимизации на стандартном симплексе в при априорном условии, что то-норма стохастического градиента ограничена параметром Ь, верхняя оценка полиномиально зависит от 1п N, а не от степени N (что обычно возникает в стандартном методе градиента).
2. Постановка задачи
Пусть некоторая управляемая система (например, маршрутизатор) обрабатывает сообщения, поступающие в случайные моменты 0 < т\ < Т2 < тз ... В каждый момент т% система несет потери, и задача оптимального управления содержательно состоит в минимизации математического ожидания суммарных потерь на заданном временном интервале [0, Т]. Потери зависят от управляемого параметра, эта зависимость описывается выпуклой функцией Q, заданной на выпуклом компакте в конечномерном евклидовом пространстве. Сам процесс потерь не наблюдается, но имеется текущая информация, которая соответствует «градиентному» оракулу: в каждый момент времени т% выходом оракула является стохастически зашумленный субградиент функции Q — стохастический субградиент.
2.1. Базовые определения
Перейдем к точным формулировкам. Обозначим через 1а индикатор множества А, т.е. функцию, равную единице на А и нулю вне А. Евклидово пространство будет рассматриваться с некоторой нормой || ■ || (не обязательно ||ж|| = ^ х\ + • • • + х'2м), а двойственное пространство — с нормой || ■ ||* = 8ируху^1(-,ж), где (■, ■) обозначает скалярное произведение.
Пусть дано вероятностное пространство (О, Я, Р), на котором определены два независимых объекта: пуассоновский процесс € [0, то), и последовательность независимых одинаково распределенных центрированных квадратично интегрируемых случайных величин £(1), £(2),... с значениями в . Обозначим через т1, т2, тз ... последовательные моменты скачков процесса X и добавим то = 0. Определим процесс £ = ^¿=1 € [0, то).
2.2. Функция потерь
Пусть дан выпуклый компакт В С — множество параметров управления. На В заданы непрерывная выпуклая функция потерь Q : В — М+ и ее субградиент — ограниченная борелевская вектор-функция дQ : В — , удовлетворяющая условию
(^(0) , 0' - 0) < Q(0/) - Q(0) V 0,0' € В .
Из непрерывности Q следует, что она ограничена снизу и существуют
(1) Q* = min Q и в* = argmin Q.
de© öe©
2.3. Задача управления
Множество стратегий управления U состоит из всевозможных кусочно-постоянных случайных процессов ut с значениями в В вида ut = = i=o e(i)1[ri,ri+i)(t), определяемых следующим образом. Неслучайное в(0) € В может быть выбрано произвольно; положим
(2) g(i) = dQ(e(i - 1))+ C(i),
где в(г) — произвольная измеримая функция от случайных величин g(1),... ..., g(i) с значениями в В, i = 1, 2,... Соответствующий процесс в непрерывном времени записывается следующим образом2:
(3) gt = öQ(ut-)+ &, t € [0,T].
Далее задается горизонт времени T > 0 и определяется функционал (критерий управления)
T г=Хт г=Хт
(4) Rt({ut}) = E Q(ut-)dXt = Q(uTi-) = Q(e(i - 1)).
0 i=1 i=1
Идеальная задача управления — минимизировать этот функционал по множеству стратегий U.
Очевидно, для любой u € U выполнено:
Rt(u) ^ Q*EXt.
С другой стороны, для стационарной стратегии управления u= {ut = в, t € [0, то)} с фиксированным в € В выполнено RT(u) = Q(e)EXT, а значит, inf Rt(u) по стационарным стратегиям u равен Q*EXt. Следовательно, infueU RT(u) = Q*EXT. Поскольку для пуассоновского процесса EXt — AT, то имеем
inf Rt(u) = Q*AT = Q(e*)AT.
u,eu
2.4. Дополнительные предположения
Полагаем, что априори известны интенсивность пуассоновского потока A > 0 и константа L € (0, то), ограничивающая стохастические градиенты в среднеквадратическом:
(5) E||<7(i)||Ub2 Vi = 1,2,...
2 Под ut- имеется в виду левосторонний предел.
3. Алгоритм зеркального спуска (ЗС)
Напомним, что алгоритм зеркального спуска представляет собой прямо-двойственный метод [1—6]. Исходным пространством является Е = с нормой || ■ ||, а двойственным — Е* = с соответствующей нормой || ■ ||*. Алгоритм ЗС содержит функциональный параметр Шр : Е* — М — выпуклую непрерывно дифференцируемую функцию со скалярным параметром в > 0 и удовлетворяющую следующему условию Липшица:
(6) Уг,геЕ*,р> О,
причем а > 0 — не зависящая от в постоянная. Отметим, что в алгоритме используется потенциальное поле УЩд : Е* — В, отображающее Е* в множество В (см. далее предложение, п. 2, (п)).
Для рассматриваемой здесь задачи алгоритм ЗС запишем в следующем виде с учетом непрерывности времени и специфики пуассоновского процесса:
1) Фиксируем начальные значения пары сопряженных переменных: (о = С(0) = 0 € Е* и 0о = 0(0) = -УЩд(((0)).
2) Для каждого момента времени Ь € [0, Т] получаем выход оракула д* = = ^2¿=1 д(^)1[тг,т-г+1)(Ь) с учетом (2) и формируем траекторию стохастического дифференциального уравнения в Е* в паре с алгебраическим уравнением:
(7) (К* = ^,
(8) щ = -УШв(С*).
3) В момент времени Т получаем реализованную траекторию {и*} и если функция потерь Q задана, то соответствующие интегральные потери
Ът({щ})= £ Q(0(i - 1)),
где тг — моменты скачков процесса X*.
Замечание 1. Очевидно, что определяемая таким образом стратегия и принадлежит и. Фактически, уравнения (7)—(8) означают, что в моменты времени тг, г = 1, 2,..., происходит пересчет величин
с (г) = с (г - 1)+ д(г), 0(г) = -уШв(С(г)).
Для полноты приведем ряд определений и предложений из [3], разъясняющих и дополняющих суть построений алгоритма ЗС (подробнее см. [3, § 3] и приведенную библиографию).
Определение 1. Пусть а > 0. Выпуклая функция V : В — М называется а-сильно выпуклой относительно исходной нормы || ■ || , если
(9) У(8Х + (1 _ 8)у) ^ 8у{х) + (1 _ 8)У{у) _ |5(1 _ 8)\\х _ у||2
при любых х, у € В и в € [0,1].
2 Автоматика и телемеханика, № 6
33
Предложение 1. Пусть функция V : в — М выпукла, а параметр в > 0. Тогда в-сопряженная к V функция
(10) Wß(z) = sup { -zT0 - (0)} V z € E*
обладает следующими свойствами:
1. Функция : Е* — М выпукла и имеет сопряженную вV, т.е.
(11) V0 € в в^(0) = sup j-zT0 - Wß(z)j ;
zeE* ^ *
2. Если функция V является а-сильно выпуклой относительно исходной нормы || ■ У, то:
(I) выполнено условие (6),
(II) атртах {-гт0 - вV(0)} = -У^в(г) € в .
Замечание 2. В соответствии с предложением, п. 2, (п) уравнение (8) можно записать в виде
ut = argmin < ZtT0 + ее© ^
Определение 2. Назовем функцию V : в ^ R+ прокси-функцией, если она выпукла и
(i) существует такая точка 0* € в, что min V(0) = V(0*),
ее©
(ii) для в-сопряженной к V функции Wß выполнено условие (6).
В [5, с. 1586] даны примеры прокси-функций в случае минимизации на симплексе: квадратичная и энтропийная.
4. Основной результат
Теорема. Пусть алгоритм ЗС с прокси-функцией V : в — М+ реализует стратегию щ на горизонте Т > 0 при описанных выше условиях. Тогда справедливо неравенство
2TXV
(12) Е7гт({г/Л) - inf КТ(и) < \ -L.
ueu V а
Параметр алгоритма а описан в (9), а ß и V задаются
(13) ß = \/, V^maxV{e).
V 2aV öe©
Доказательство теоремы. Имеем
Е
ЕКт ({%}) - М Кт (и) =
гь£Ы
Хт
1{хт -1)) - хт д(Г)
г=1
{Хт=П}
п=1
¿д(0(г -1)) - пд(Г)
,г=1
П=1
< Е I /ЗУ + ¿2 ) = ру + ^ ь2.
2ав
2ав ЛТ
2ав
<
Поясним неравенство в этой цепочке. При условии события {Хт = п} случайные величины £Т1, £Т2,..., £Тп распределены так же, как {(1), £(2),... , £(п), и алгоритм работает так же, как в модели [3] с дискретным временем и п шагами. Это позволяет применить предложения 2 и 3 из [3, § 4], с = 1 и получить рассматриваемое неравенство — явную верхнюю оценку превышения средних интегральных потерь над минимумом. В правой части остается провести минимизацию по в > 0. Приходим к (13) и желаемо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.