Дрифт плюс штраф - Drift plus penalty

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

Этот метод предназначен для стабилизации сети массового обслуживания, а также для минимизации среднего времени функции сетевого штрафа. Его можно использовать для оптимизации целей производительности, таких как средняя по времени мощность, пропускная способность и полезность пропускной способности.^[1][2]В особом случае, когда нет никаких штрафов, которые нужно минимизировать, и когда целью является разработка стабильной политики маршрутизации в многозвенной сети, метод сводится к маршрутизация противодавления.^[3][4]Метод смещения плюс штраф также может использоваться для минимизации среднего времени случайный процесс с учетом ограничений по времени на набор других случайных процессов.^[5]Это делается путем определения соответствующего набора виртуальные очереди. Его также можно использовать для получения усредненных по времени решений для выпуклая оптимизация проблемы. ^[6][7]

Методология

Метод дрейфа плюс штраф применяется к системам массового обслуживания, которые работают в дискретном времени с временными интервалами. т в {0, 1, 2, ...}. Во-первых, неотрицательная функция L(т) определяется как скалярная мера состояния всех очередей в момент временит. Функция L(т) обычно определяется как сумма квадратов всех размеров очереди в момент времени. т, и называется Функция Ляпунова. В Ляпунов дрифт определено:

${ displaystyle Delta L (t) = L (t + 1) -L (t)}$

Каждый слот t отслеживается текущее состояние очереди и предпринимаются управляющие действия для жадной минимизации ограничения на следующие выражение "дрейф плюс штраф":

${ Displaystyle Delta L (t) + Vp (t),}$

куда п(т) - штрафная функция, а V - неотрицательный вес. Параметр V можно выбрать, чтобы обеспечить среднее по времени п(т) произвольно близка к оптимальной с соответствующим компромиссом в среднем размере очереди. Нравиться маршрутизация противодавления, этот метод обычно не требует знания распределений вероятностей для поступления на работу и мобильности сети.^[5]

Истоки и приложения

Когда ${ Displaystyle V = 0,}$ метод сводится к жадной минимизации ляпуновского дрейфа. Это приводит к маршрутизация противодавления алгоритм, первоначально разработанный Тассиуласом и Ефремидом (также называемый алгоритм максимального веса).^[3][8] В ${ displaystyle Vp (t)}$ термин был добавлен к выражению дрейфа Нили^[9] и Нили, Модиано, Ли^[2] для стабилизации сети, а также для максимизации функции полезности пропускной способности. За это штраф ${ displaystyle p (t)}$ был определен как ${ displaystyle -1}$ раз награда, заработанная на слоте ${ displaystyle t.}$ Этот метод «дрейф плюс штраф» позже был использован для минимизации средней мощности.^[1] и оптимизировать другие показатели штрафов и вознаграждений.^[4][5]

Теория была разработана в первую очередь для оптимизации сетей связи, включая беспроводные сети, специальные мобильные сети и другие компьютерные сети. Однако математические методы могут применяться для оптимизации и управления другими стохастическими системами, включая распределение возобновляемой энергии в умные электросети^[10][11][12] и управление запасами для систем сборки продукции.^[13]

Как это устроено

В этом разделе показано, как использовать метод смещения плюс штраф для минимизации среднего времени функции p (t) с учетом ограничений среднего времени на набор других функций. Приведенный ниже анализ основан на материале в.^[5]

Проблема стохастической оптимизации

Рассмотрим систему с дискретным временем, которая развивается за нормированные временные интервалы t в {0, 1, 2, ...}. Определите p (t) как функцию, среднее время которой должно быть минимизировано, называемую штрафная функция. Предположим, что минимизация среднего времени p (t) должна выполняться с учетом ограничений среднего времени на набор K других функций:

• ${ displaystyle p (t) = { text {штрафная функция, среднее время которой должно быть минимизировано}}}$

• ${ displaystyle y_ {1} (t), y_ {2} (t), ldots, y_ {K} (t) = { text {другие функции, средние значения которых по времени должны быть неположительными}}}$

Каждый слот t сетевой контроллер наблюдает новое случайное событие. Затем он выполняет управляющее действие, основываясь на знании этого события. Значения p (t) и y_i (t) определяются как функции случайного события и управляющего воздействия на слот t:

• ${ displaystyle omega (t) = { text {случайное событие в слоте}} t { text {(предполагается, что i.i.d. по слотам)}}}$

• ${ displaystyle alpha (t) = { text {управляющее действие в слоте}} t { text {(выбрано после наблюдения}} omega (t) { text {)}}}$

• ${ Displaystyle п (т) = п ( альфа (т), омега (т)) { текст {(детерминированная функция}} альфа (т), омега (т) { текст {)} }}$

• ${ Displaystyle Y_ {я} (т) = Y_ {я} ( альфа (т), омега (т)) { текст {}} forall i in {1, ldots, K } { text {(детерминированные функции от}} alpha (t), omega (t) { text {)}}}$

Обозначение p (t), y_i (t) в маленьком регистре и обозначение P (), Y_i () в верхнем регистре используется, чтобы отличать значения штрафа от функции, которая определяет эти значения на основе случайного события и управляющего действия для слота t. Случайное событие ${ Displaystyle omega (т)}$ предполагается, что принимает значения в некотором абстрактном наборе событий ${ displaystyle Omega}$. Управляющее действие ${ Displaystyle альфа (т)}$ предполагается, что он выбран в некотором абстрактном наборе ${ displaystyle A}$ который содержит параметры управления. Наборы ${ displaystyle Omega}$ и ${ displaystyle A}$ произвольны и могут быть конечными или бесконечными. Например, ${ displaystyle A}$ может быть конечный список абстрактных элементов, бесчисленное множество (и, возможно, невыпуклый) набор векторов с действительными значениями и т. д. Функции P (), Y_i () также произвольны и не требуют предположений о непрерывности или выпуклости.

В качестве примера в контексте сетей связи случайное событие ${ Displaystyle omega (т)}$ может быть вектором, который содержит информацию о прибытии временного интервала t для каждого узла и информацию о состоянии канала временного интервала t для каждой ссылки. Управляющее действие ${ Displaystyle альфа (т)}$ может быть вектором, который содержит решения о маршрутизации и передаче для каждого узла. Функции P () и Y_i () могут представлять затраты мощности или пропускную способность, связанные с действием управления и состоянием канала для слота t.

Для простоты изложения предположим, что функции P () и Y_i () ограничены. Далее предположим случайный процесс событий ${ Displaystyle omega (т)}$ является независимые и одинаково распределенные (i.i.d.) по слотам t с некоторым, возможно, неизвестным распределением вероятностей. Цель состоит в том, чтобы разработать политику для выполнения контрольных действий с течением времени для решения следующей проблемы:

${ displaystyle { text {Minimize:}} lim _ {t rightarrow infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [p ( тау)]}$

${ displaystyle { text {Subject to:}} lim _ {t rightarrow infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)] leq 0 { text {}} forall i in {1, ldots, K }}$

Предполагается, что эта проблема достижимый. То есть предполагается, что существует алгоритм, который может удовлетворить все K желаемые ограничения.

Вышеупомянутая проблема ставит каждое ограничение в стандартная форма среднего времени ожидания абстрактного процесса y_i (t), неположительного. В этом подходе нет потери общности. Например, предположим, что кто-то желает, чтобы среднее время ожидания некоторого процесса a (t) было меньше или равно заданной константе c. Тогда новая штрафная функция у(т) = а(т) − c можно определить, и желаемое ограничение эквивалентно среднему времени ожидания у(т) быть неположительным. Аналогично, предположим, что есть два процесса а(т) и б(т) и требуется среднее по времени ожидание а(т) быть меньше или равноб(т). Это ограничение записывается в стандартной форме путем определения новой функции штрафа. у(т) = а(т) − б(т). Вышеупомянутая проблема стремится свести к минимуму среднее по времени абстрактной штрафной функциип'(т) '. Это можно использовать для максимизировать среднее время некоторых желательных функция вознагражденияр(т) путем определения п(т) = −р('т).

Виртуальные очереди

Для каждого ограничения я в 1, ..., K}, определите виртуальная очередь с динамикой по слотам т в {0, 1, 2, ...} следующим образом:

${ displaystyle ({ text {Eq.}} 1) { text {}} Q_ {i} (t + 1) = max [Q_ {i} (t) + y_ {i} (t), 0 ]}$

Инициализировать Q_я(0) = 0 для всех я в 1, ..., K}. Это уравнение обновления идентично уравнению виртуальный дискретная временная очередь с отставанием Q_i (t) и с y_i (t), являющимся разницей между новыми поступлениями и новыми возможностями обслуживания в слотет. Интуитивно, стабилизация этих виртуальных очередей гарантирует, что средние по времени функций ограничений меньше или равны нулю, поэтому требуемые ограничения удовлетворяются. Чтобы убедиться в этом, обратите внимание, что (уравнение 1) подразумевает:

${ displaystyle Q_ {i} (t + 1) geq Q_ {i} (t) + y_ {i} (t)}$

Следовательно:

${ Displaystyle у_ {я} (т) leq Q_ {я} (т + 1) -Q_ {я} (т)}$

Суммируя вышеупомянутые первые t слотов и используя закон телескопических сумм, получаем:

${ displaystyle sum _ { tau = 0} ^ {t-1} y_ {i} ( tau) leq Q_ {i} (t) -Q_ {i} (0) = Q_ {i} (t )}$

Деление на т а принятие ожиданий подразумевает:

${ displaystyle { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)] leq { frac {E [Q_ {i } (t)]} {t}}}$

Следовательно, требуемые ограничения задачи выполняются, если для всех i в {1, ..., K}:

${ displaystyle lim _ {t rightarrow infty} { frac {E [Q_ {i} (t)]} {t}} = 0}$

Очередь Q_i (t), удовлетворяющая указанному выше предельному уравнению, называется средняя скорость стабильная.^[5]

Выражение смещения плюс штраф

Чтобы стабилизировать очереди, определите функцию Ляпунова L (t) как меру общего отставания очереди на слотет:

${ Displaystyle L (т) = { гидроразрыва {1} {2}} сумма _ {я = 1} ^ {K} Q_ {я} (т) ^ {2}}$

Возведение уравнения массового обслуживания в квадрат (уравнение 1) приводит к следующей оценке для каждой очереди i в {1, ..., K}:

${ Displaystyle Q_ {я} (т + 1) ^ {2} leq (Q_ {я} (т) + y_ {я} (т)) ^ {2} = Q_ {я} (т) ^ {2 } + y_ {i} (t) ^ {2} + 2Q_ {i} (t) y_ {i} (t)}$

Следовательно,

${ displaystyle { frac {1} {2}} sum _ {i = 1} ^ {K} Q_ {i} (t + 1) ^ {2} leq { frac {1} {2}} sum _ {i = 1} ^ {K} Q_ {i} (t) ^ {2} + { frac {1} {2}} sum _ {i = 1} ^ {K} y_ {i} (t) ^ {2} + sum _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Следует, что

${ displaystyle Delta L (t) = L (t + 1) -L (t) leq { frac {1} {2}} sum _ {i = 1} ^ {K} y_ {i} ( t) ^ {2} + sum _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Теперь определим B как положительную константу, ограничивающую сверху первое слагаемое в правой части указанного неравенства. Такая константа существует, потому что значения y_i (t) ограничены. Потом:

${ displaystyle Delta L (t) leq B + sum _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Добавление Vp (t) к обеим сторонам приводит к следующей оценке выражения смещения плюс штраф:

${ displaystyle ({ text {Eq.}} 2) { text {}} Delta L (t) + Vp (t) Leq B + Vp (t) + sum _ {i = 1} ^ { K} Q_ {i} (t) y_ {i} (t)}$

Алгоритм смещения плюс штраф (определенный ниже) выполняет управляющие воздействия на каждый слот t, которые жадно минимизируют правую часть приведенного выше неравенства. Интуитивно понятно, что действие, которое сводит к минимуму дрейф, было бы полезно с точки зрения стабильности очереди, но не минимизировало бы штраф за среднее время. Само по себе действие, минимизирующее штраф, не обязательно стабилизирует очереди. Таким образом, принятие мер по минимизации взвешенной суммы включает в себя как цели стабильности очереди, так и минимизации штрафов. Вес V можно настроить таким образом, чтобы более или менее упор был сделан на минимизацию штрафа, что приводит к снижению производительности.^[5]

Алгоритм дрейфа плюс штраф

Позволять ${ displaystyle A}$ - абстрактный набор всех возможных управляющих воздействий. В каждом слоте t наблюдайте за случайным событием и текущими значениями очереди:

${ displaystyle { text {Observe:}} omega (t), Q_ {1} (t), ldots, Q_ {K} (t)}$

Учитывая эти наблюдения для слота t, жадно выбирайте управляющее действие ${ Displaystyle альфа (т) в А}$ чтобы свести к минимуму следующее выражение (произвольное прерывание связей):

${ Displaystyle VP ( альфа (т), омега (т)) + сумма _ {я = 1} ^ {K} Q_ {я} (т) Y_ {я} ( альфа (т), омега (t))}$

Затем обновите очереди для каждого i в {1, ..., K} в соответствии с (уравнением 1). Повторите эту процедуру для слота t + 1.^[5]

Обратите внимание, что случайные события и невыполненные очереди в слоте т действуют как заданные константы при выборе управляющего воздействия для минимизации слота t. Таким образом, каждый слот включает детерминированный поиск минимизирующего управляющего воздействия над множеством А. Ключевой особенностью этого алгоритма является то, что он не требует знания распределения вероятностей процесса случайного события.

Примерное расписание

Вышеупомянутый алгоритм включает поиск минимума функции по абстрактному множеству А. В общем случае минимума может не быть или его трудно найти. Таким образом, полезно предположить, что алгоритм реализован приблизительно следующим образом: Определить C как неотрицательную константу и предположим, что для всех слотов т, управляющее воздействие ${ Displaystyle альфа (т)}$ выбирается в наборе А удовлетворить:

${ displaystyle { begin {align} & VP ( alpha (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha (t), omega (t)) leq {} & C + inf _ { alpha in A} [VP ( alpha, omega (t)) + sum _ {i = 1} ^ { K} Q_ {i} (t) Y_ {i} ( alpha, omega (t))] end {align}}}$

Такое управляющее воздействие называется C-аддитивное приближение.^[5] Дело C = 0 соответствует точной минимизации искомого выражения на каждом слотет.

Анализ производительности

В этом разделе показано, как алгоритм приводит к среднему штрафу по времени, который находится в пределах O (1 / V) от оптимальности, с соответствующим компромиссом O (V) в среднем размере очереди.^[5]

Анализ среднего штрафа

Определить ${ displaystyle omega}$-только политика быть стационарной и рандомизированной политикой для выбора управляющего воздействия ${ Displaystyle альфа (т)}$ на основе наблюдаемых ${ Displaystyle omega (т)}$ Только. То есть ${ displaystyle omega}$-только политика определяет для каждого возможного случайного события ${ displaystyle omega in Omega}$, условное распределение вероятностей для выбора управляющего воздействия ${ Displaystyle альфа (т) в А}$ при условии ${ Displaystyle омега (т) = омега}$. Такая политика принимает решения независимо от текущего отставания в очереди. Предположим, что существует ${ displaystyle omega}$-только политика ${ Displaystyle альфа ^ {*} (т)}$ который удовлетворяет следующему:

${ displaystyle ({ text {Eq.}} 3) qquad E [P ( alpha ^ {*} (t), omega (t))] = p ^ {*} = { text {оптимальное время средний штраф за проблему}}}$

${ displaystyle ({ text {Eq.}} 4) qquad E [Y_ {i} ( alpha ^ {*} (t), omega (t))] leqslant 0 qquad forall i in {1, ldots, K }}$

Вышеуказанные ожидания относятся к случайной величине ${ Displaystyle omega (т)}$ для слота ${ displaystyle t,}$ и случайное управляющее воздействие ${ Displaystyle альфа (т)}$ выбран на слоте ${ displaystyle t}$ после наблюдения ${ Displaystyle omega (т)}$. Такая политика ${ Displaystyle альфа ^ {*} (т)}$ можно показать, что существует всякий раз, когда желаемая задача управления является выполнимой и пространство событий для ${ Displaystyle omega (т)}$ и пространство для действий ${ Displaystyle альфа (т)}$ конечны, или когда выполняются свойства умеренного замыкания.^[5]

Позволять ${ Displaystyle альфа (т)}$ представляют действие, предпринимаемое C-аддитивной аппроксимацией алгоритма смещения плюс штраф из предыдущего раздела для некоторой неотрицательной константы C. Для упрощения терминологии мы называем это действие дрейф плюс штраф, а не С-аддитивное приблизительное действие смещения плюс штраф. Позволять ${ Displaystyle альфа ^ {*} (т)}$ представляют ${ displaystyle omega}$-только решение:

${ displaystyle alpha (t) = { text {действие смещения плюс штраф для слота}} t}$

${ displaystyle alpha ^ {*} (t) = omega { text {- только действие, удовлетворяющее (уравнение 3) - (уравнение 4)}}}$

Предположим действие смещения плюс штраф ${ Displaystyle альфа (т)}$ используется на каждом слоте. Согласно (2) выражение смещения плюс штраф при этом ${ Displaystyle альфа (т)}$ действие удовлетворяет следующему для каждого слота ${ displaystyle t:}$

${ Displaystyle { begin {align} Delta L (t) + Vp (t) & leqslant B + Vp (t) + sum _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t) & = B + VP ( alpha (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha (t), omega (t)) & leqslant B + C + VP ( alpha ^ {*} (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) конец {выровнено}}}$

где следует последнее неравенство, поскольку действие ${ Displaystyle альфа (т)}$ входит в аддитивную константу ${ displaystyle C}$ минимизировать предыдущее выражение по всем остальным действиям в наборе ${ displaystyle A,}$ включая ${ displaystyle alpha ^ {*} (т).}$ Исходя из ожиданий указанного выше неравенства, получаем:

${ Displaystyle { begin {align} E [ Delta (t) + Vp (t)] & leqslant B + C + VE [P ( alpha ^ {*} (t), omega (t))] + sum _ {i = 1} ^ {K} E left [Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) right] & = B + C + VE [P ( alpha ^ {*} (t), omega (t))] + sum _ {i = 1} ^ {K} E [Q_ {i} (t)] E [Y_ {i} ( alpha ^ {*} (t), omega (t))] && alpha ^ {*} (t), omega (t) { text {не зависят от}} Q_ {i} (t) & leqslant B + C + Vp ^ {*} && { text {Используя уравнение. 3 и уравнение. 4}} end {выровнено}}}$

Обратите внимание, что ${ Displaystyle альфа ^ {*} (т)}$ действие никогда не было реализовано. Его существование использовалось только для сравнения, чтобы достичь окончательного неравенства. Суммируя указанное выше неравенство по первому ${ displaystyle t> 0}$ слоты дает:

${ displaystyle { begin {align} (B + C + Vp ^ {*}) t & geqslant sum _ { tau = 0} ^ {t-1} E [ Delta ( tau) + Vp ( tau)] & = E [L (t)] - E [L (0)] + V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && Delta ( tau) = L ( tau +1) -L ( tau) & = E [L (t)] + V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && { text {accept}} L (0) = 0 & geqslant V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && L (t ) geqslant 0 конец {выровнено}}}$

Разделив указанное выше на ${ displaystyle Vt}$ дает следующий результат, справедливый для всех слотов ${ displaystyle t> 0:}$

${ displaystyle { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [p ( tau)] leqslant p ^ {*} + { frac {B + РЕЗЮМЕ}}.}$

Таким образом, средний ожидаемый по времени штраф может быть произвольно близок к оптимальному значению. ${ displaystyle p ^ {*}}$ выбирая ${ displaystyle V}$ достаточно большой. Можно показать, что все виртуальные очереди стабильны по средней скорости, и поэтому все требуемые ограничения удовлетворяются.^[5] Параметр ${ displaystyle V}$ влияет на размер очередей, который определяет скорость, с которой функции ограничения среднего времени сходятся к неположительному числу. Более подробный анализ размеров очередей приведен в следующем подразделе.

Анализ среднего размера очереди

Предположим теперь, что существует ${ displaystyle omega}$-только политика ${ Displaystyle альфа ^ {*} (т)}$, возможно, отличный от того, который удовлетворяет (Уравнение 3) - (Уравнение 4), который удовлетворяет следующему для некоторых ${ displaystyle epsilon> 0}$:

${ displaystyle ({ text {Eq.}} 5) qquad E [Y_ {i} ( alpha ^ {*} (t), omega (t))] leq - epsilon qquad forall i in {1, ldots, K }}$

Аргумент, аналогичный приведенному в предыдущем разделе, показывает:

${ Displaystyle { begin {align} Delta (t) + Vp (t) & leqslant B + C + VP ( alpha ^ {*} (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) Delta (t) + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t) ) && { text {accept}} p _ { min} leqslant P leqslant p _ { max} E [ Delta (t)] + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} E left [Q_ {i} (t)] E [Y_ {i} ( alpha ^ {*} (t), omega (t)) right] && { text {с ожиданием}} E [ Delta (t)] + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} E [Q_ {i} (t)] (- epsilon) && { text {Использование (5)}} E [ Delta (t)] + epsilon sum _ {i = 1} ^ {K} E [Q_ {i} (t)] & leqslant B + C + V (p _ { max} -p _ { min}) end {выровнено}}}$

Таким образом, можно использовать аргумент телескопической серии, аналогичный приведенному в предыдущем разделе, чтобы показать следующее для всех t> 0:^[5]

${ displaystyle { frac {1} {t}} sum _ { tau = 0} ^ {t-1} sum _ {i = 1} ^ {K} E [Q_ {i} ( tau) ] leqslant { frac {B + C + V (p _ { max} -p _ { min})} { epsilon}}}$

Это показывает, что средний размер очереди действительно O (V).

Вероятность 1 сходимости

Приведенный выше анализ рассматривает средние временные ожидания. Связанные границы производительности с вероятностью 1 для среднего размера очереди по времени и штрафа за бесконечный горизонт могут быть получены с использованием метода смещения плюс штраф вместе с теория мартингейла.^[14]

Применение в очередях с конечной емкостью

Как показано, дрейф плюс штраф позволяет удерживать средний размер очереди ниже определенного порога, который зависит от выбора параметра V, но в целом не дает никаких гарантий максимальной занятости очереди. Однако, если набор действий соблюдает определенные ограничения, можно добавить дополнительное условие при выборе V, чтобы обеспечить максимальную длину очереди и, таким образом, применить алгоритм также к очередям с конечной емкостью.^[15]

Обработка систем массового обслуживания

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

Выпуклые функции средних значений времени

Связанная с этим проблема - это минимизация выпуклой функции средних значений времени с учетом ограничений, таких как:

${ displaystyle { text {Minimize}} quad f left ({ overline {y}} _ {1}, ldots, { overline {y}} _ {K} right) quad { text {при условии}} quad g_ {i} left ({ overline {y}} _ {1}, ldots, { overline {y}} _ {K} right) leqslant 0 qquad forall i in {1, ldots, N }}$

куда ${ displaystyle f}$ и ${ displaystyle g_ {i}}$ находятся выпуклые функции, и где определены средние по времени:

${ displaystyle { overline {y}} _ {i} = lim _ {t to infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)]}$

Такие задачи оптимизации выпуклых функций средних по времени можно преобразовать в задачи оптимизации средних значений функций с помощью вспомогательные переменные (см. главу 5 учебника Neely).^[2][5] Последние проблемы могут быть решены методом «дрейф плюс штраф», как описано в предыдущих подразделах. Альтернатива первично-дуальный Метод принимает решения, аналогичные решениям с отклонением плюс штраф, но использует штраф, определяемый частными производными целевой функции ${ displaystyle f.}$^[5][16][17] Первично-дуальный подход также может быть использован для поиска локальных оптимумов в случаях, когда ${ displaystyle f}$ невыпуклый.^[5]

Откладывать компромиссы и связанную с ними работу

Математический анализ, приведенный в предыдущем разделе, показывает, что метод смещения плюс штраф дает средний штраф по времени, который находится в пределах O (1 /V) оптимальности с соответствующим О(V) компромисс в среднем размере очереди. Этот метод вместе с О(1/V), О(V) компромисс, был разработан в Нили^[9] и Нили, Модиано, Ли^[2] в контексте максимизации сетевой полезности при условии стабильности.

Родственный алгоритм для максимизации сетевой полезности был разработан Эрилмазом и Шрикантом.^[18]Результатом работы Эрилмаза и Шриканта стал алгоритм, очень похожий на алгоритм «дрейф плюс штраф», но с использованием другой аналитической техники. Эта техника была основана на Множители Лагранжа. Прямое использование метода множителя Лагранжа приводит к худшему компромиссу О(1/V), O (V²). Однако позже Хуанг и Нили усилили анализ множителя Лагранжа, чтобы восстановить исходный О(1/V), О(V) компромиссов, показывая, что размеры очередей тесно сгруппированы вокруг множителя Лагранжа соответствующей детерминированной задачи оптимизации.^[19]Этот результат кластеризации можно использовать для модификации алгоритма смещения плюс штраф, чтобы обеспечить улучшенный О(1/V), О(бревно²(V)) компромиссы. В модификациях можно использовать либо отставание заполнителя^[19] или же Последний вошел - первым ушел (LIFO) планирование.^[20][21]

При реализации для нестохастических функций метод смещения плюс штраф аналогичен методу двойной субградиентный метод из теория выпуклой оптимизации, за исключением того, что его результат является средним по времени основные переменные, а не сами основные переменные.^[4][6] Связанный первично-дуальная техника для максимизации полезности в стохастической сети массового обслуживания был разработан Столяр с использованием анализа жидкостной модели.^[16][17]Анализ Столяр не дает аналитических результатов для компромисса производительности между полезностью и размером очереди. Более поздний анализ первично-двойственного метода для стохастических сетей доказывает аналогичный компромисс между полезностью O (1 / V), O (V) и размером очереди, а также показывает результаты локальной оптимальности для минимизации невыпуклых функций средних по времени при допущение дополнительной сходимости.^[5] Однако в этом анализе не указывается, сколько времени требуется для того, чтобы средние значения времени сходились к чему-то, близкому к их пределам бесконечного горизонта. Родственные первично-двойственные алгоритмы максимизации полезности без очередей были разработаны Агравалом и Субраманианом.^[22]и Кушнер и Уайтинг.^[23]

Расширения для non-i.i.d. событийные процессы

Известно, что алгоритм смещения плюс штраф обеспечивает аналогичные гарантии производительности для более общих эргодических процессов. ${ Displaystyle omega (т)}$, так что i.i.d. предположение не является решающим для анализа. Можно показать, что алгоритм устойчив к неэргодическим изменениям вероятностей для ${ Displaystyle omega (т)}$. В определенных сценариях может быть показано, что он обеспечивает желаемые аналитические гарантии, называемые универсальные гарантии планирования, для произвольных ${ Displaystyle omega (т)}$ процессы.^[5]

Расширения систем с переменной длиной кадра

Метод «дрейф плюс штраф» может быть расширен для обработки систем, которые работают с кадрами переменного размера.^[24][25] В этом случае кадры помечаются индексами р в {0, 1, 2, ...}, а длительность кадра обозначается {Т[0], Т[1], Т[2], ...}, где Т[р] - неотрицательное действительное число для каждого кадрар. Позволять ${ displaystyle Delta [r]}$ и ${ displaystyle p [r]}$ быть дрейфом между кадрами р и р +1, и общий штраф, понесенный во время кадрар, соответственно. Расширенный алгоритм выполняет управляющее действие над каждым кадром r, чтобы минимизировать ограничение на следующее соотношение условных ожиданий:

${ Displaystyle { гидроразрыва {E [ Delta [r] + Vp [r] mid Q [r]]} {E [T [r] mid Q [r]]}}})$

куда Q[р] - вектор невыполненных очередей в начале кадрар. В особом случае, когда все кадры имеют одинаковый размер и нормированы на длину 1 слота, так что Т[р] = 1 для всех р, указанная выше минимизация сводится к стандартному методу "дрейф плюс штраф". Этот метод, основанный на кадрах, может использоваться для ограниченной оптимизации Марковские задачи решения (MDP) и для других проблем, связанных с системами, которые испытывают обновления.^[24][25]

Приложение к выпуклому программированию

Позволять Икс = (Икс₁, ..., Икс_N) быть N-мерный вектор действительных чисел и определить гипер-прямоугольник А к:

${ Displaystyle A = {(x_ {1}, x_ {2}, ldots, x_ {N}) mid x _ { min, i} leq x_ {i} leq x _ { max, i} { text {}} forall i in {1, ldots, N } }}$

куда Икс_{мин, я}, Икс_{Максимум, я} даны действительные числа, удовлетворяющие ${ Displaystyle х _ { мин, я} <х _ { макс, я}}$ для всехя. Позволять п(Икс) и ${ Displaystyle Y_ {я} (х)}$ для i в {1, ..., K} быть непрерывным и выпуклые функции из Икс вектор по всему Икс вА. Рассмотрим следующее выпуклое программирование проблема:

${ displaystyle ({ text {Eq.}} 6) { text {}} { text {Minimize:}} P (x)}$

${ displaystyle ({ text {Eq.}} 7) { text {}} { text {Subject to:}} Y_ {i} (x) leq 0 { text {}} forall i in {1, ldots, K } { text {}}, { text {}} x = (x_ {1}, ldots, x_ {N}) in A}$

Это может быть решено методом дрейфа плюс штраф следующим образом: Рассмотрим частный случай детерминированной системы без процесса случайных событий. ${ Displaystyle omega (т)}$. Определите управляющее действие ${ Displaystyle альфа (т)}$ в качестве:

${ Displaystyle альфа (т) = х (т) = (х_ {1} (т), х_ {2} (т), ldots, x_ {N} (т))}$

и определим пространство действий как N-мерный гипер-прямоугольник А. Определите функции штрафов и ограничений как:

• ${ Displaystyle п (т) = п (х_ {1} (т), ldots, х_ {N} (т))}$

• ${ displaystyle y_ {i} (t) = Y_ {i} (x_ {1} (t), ldots, x_ {N} (t)) { text {}} forall i in {1, ldots, K }}$

Определите следующие средние значения времени:

• ${ displaystyle { overline {x}} (t) = { frac {1} {t}} sum _ { tau = 0} ^ {t-1} (x_ {1} ( tau), ldots, x_ {N} ( tau))}$

• ${ displaystyle { overline {P}} (t) = { frac {1} {t}} sum _ { tau = 0} ^ {t-1} P (x_ {1} ( tau), ldots, x_ {N} ( tau))}$

• ${ displaystyle { overline {Y}} _ {i} (t) = { frac {1} {t}} sum _ { tau = 0} ^ {t-1} Y_ {i} (x_ { 1} ( tau), ldots, x_ {N} ( tau))}$

Теперь рассмотрим следующую задачу оптимизации среднего времени:

${ displaystyle ({ text {Eq.}} 8) { text {}} { text {Minimize:}} lim _ {t rightarrow infty} { overline {P}} (t)}$

${ displaystyle ({ text {Eq.}} 9) { text {}} { text {при условии:}} lim _ {t rightarrow infty} { overline {Y}} _ {i} (t) leq 0 { text {}} forall i in {1, ldots, K }}$

К Неравенство Дженсена для всех слотов t> 0 выполняется следующее:

${ displaystyle P ({ overline {x}} (t)) leq { overline {P}} (t) { text {}}, { text {}} Y_ {i} ({ overline { x}} (t)) leq { overline {Y}} _ {i} (t) { text {}} forall i in {1, ldots, K }}$

Исходя из этого, можно показать, что оптимальное решение задачи среднего времени (уравнение 8) - (уравнение 9) может быть достигнуто решениями типа x (t) = x * для всех интервалов t, где x * - вектор, который решает выпуклую программу (уравнение 6) - (уравнение 7). Далее, любой усредненный по времени вектор ${ Displaystyle lim _ {т rightarrow infty} { overline {x}} (т)}$ соответствующий решению задачи среднего времени (уравнение 8) - (уравнение 9) должно решать выпуклую программу (уравнение 6) - (уравнение 7). Следовательно, исходная выпуклая программа (уравнение 6) - (уравнение 7) может быть решена (с любой желаемой точностью), взяв среднее значение по времени решений, принятых при применении алгоритма смещения плюс штраф к соответствующему моменту времени. -средняя задача (уравнение 8) - (уравнение 9). Алгоритм дрейфа плюс штраф для задачи (уравнение 8) - (уравнение 9) сводится к следующему:

Алгоритм смещения плюс штраф для выпуклого программирования

Каждый слот т, выберите вектор ${ Displaystyle х (т) = (х_ {1} (т), ldots, х_ {N} (т)) в А}$ чтобы минимизировать выражение:

${ Displaystyle VP (х (т)) + сумма _ {я = 1} ^ {K} Q_ {я} (т) Y_ {я} (х (т))}$

Затем обновите очереди в соответствии с:

${ displaystyle Q_ {i} (t + 1) = max [Q_ {i} (t) + Y_ {i} (x (t)), 0] { text {}} forall i in { 1, ldots, K }}$

Вектор среднего времени ${ Displaystyle { overline {x}} (т)}$ сходится к приближению O (1 / V) к выпуклой программе.^[6]

Этот алгоритм аналогичен стандартному двойной субградиентный алгоритм теории оптимизации, используя фиксированный размер шага 1 / V.^[26] Однако ключевое отличие состоит в том, что алгоритм двойного субградиента обычно анализируется при ограничительных предположениях о строгой выпуклости, которые необходимы для основные переменные Икс(т) сходиться. Есть много важных случаев, когда эти переменные не сходятся к оптимальному решению и даже не приближаются к оптимальному решению (это так для большинства линейные программы, как показано ниже). С другой стороны, алгоритм смещения плюс штраф не требует строгих предположений о выпуклости. Это гарантирует, что среднее время примитивов сходятся к решению, которое находится в пределах О(1/V) оптимальности, с О(V) границы размеров очереди (можно показать, что это переводится в О(V²) оценка времени сходимости).^[6]

Алгоритм дрейфа плюс штраф для линейного программирования

Рассмотрим частный случай линейная программа. В частности, предположим:

• ${ Displaystyle P (x (t)) = sum _ {n = 1} ^ {N} c_ {n} x_ {n} (t)}$

• ${ displaystyle Y_ {i} (x (t)) = sum _ {n = 1} ^ {N} a_ {in} x_ {n} (t) -b_ {i} { text {}} forall i in {1, ldots, K }}$

для заданных действительных констант (c₁, …, c_N), (а_в), (б₁, …, б_K). Тогда приведенный выше алгоритм сводится к следующему: Каждый слот т и для каждой переменной п в 1, …, N}, выберите Икс_п(т) в [Икс_мин,п, Икс_{Максимум,п}], чтобы минимизировать выражение:

${ displaystyle left [Vc_ {n} + sum _ {i = 1} ^ {K} Q_ {i} (t) a_ {in} right] x_ {n} (t)}$

Затем обновите очереди Q_я(т) как прежде. Это означает выбор каждой переменной Икс_я(т) согласно простому ПИФ-паф политика контроля:

${ displaystyle { text {Choose}} x_ {i} (t) = x _ { min, i} { text {if}} Vc_ {n} + sum _ {i = 1} ^ {K} Q_ {i} (t) a_ {in} geq 0}$

${ displaystyle { text {Choose}} x_ {i} (t) = x _ { max, i} { text {if}} Vc_ {n} + sum _ {i = 1} ^ {K} Q_ {i} (t) a_ {in} <0}$

Поскольку первичные переменные Икс_я(т) всегда либо Икс_мин,я или же Икс_{Максимум,я}, они никогда не могут сходиться к оптимальному решению, если оптимальное решение не является вершиной гипер-прямоугольника А. Тем не менее средние по времени из этих взрывных решений действительно сходятся к О(1/V) приближение оптимального решения. Например, предположим, что Икс_{мин, 1} = 0, Икс_{макс, 1} = 1, и предположим, что все оптимальные решения линейной программы имеют Икс₁ = 3/4. Тогда примерно в 3/4 случаев удачное решение для первой переменной будет Икс₁(т) = 1, а оставшееся время будет Икс₁(т) = 0.^[7]

Ссылки по теме

• Маршрутизация противодавления
• Оптимизация по Ляпунову
• Выпуклая оптимизация
• Линейное программирование

Рекомендации

Основные источники

• М. Дж. Нили. Стохастическая оптимизация сети с приложением к системам связи и массового обслуживания, Морган и Клейпул, 2010 г.