Дрифт плюс штраф

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

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

Методология

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

$\Delta L(t)=L(t+1)-L(t)$

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

$\Delta L(t)+Vp(t),$

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

Происхождение и применение

Когда $V=0,$ метод сводится к жадной минимизации дрейфа Ляпунова. В результате получается алгоритм маршрутизации с противодавлением, первоначально разработанный Тассиуласом и Эфремидом (также называемый алгоритмом максимального веса ). $Vp(t)$ термин был добавлен к выражению дрейфа Нили и Нили, Модиано, Ли для стабилизации сети и одновременного максимизации функции полезности пропускной способности. За это штраф $p(t)$ был определен как $-1$ умножить вознаграждение, полученное в слоте $t.$ Этот метод «дрейф плюс штраф» позже использовался для минимизации средней мощности. и оптимизировать другие показатели штрафов и вознаграждений.

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

Как это работает

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

Задача стохастической оптимизации

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

• $p(t)={\text{penalty function whose time average must be minimized}}$

• $y_{1}(t),y_{2}(t),\ldots ,y_{K}(t)={\text{other functions whose time averages must be non-positive}}$

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

• $\omega (t)={\text{random event on slot }}t{\text{ (assumed i.i.d. over slots)}}$

• $\alpha (t)={\text{control action on slot }}t{\text{ (chosen after observing }}\omega (t){\text{)}}$

• $p(t)=P(\alpha (t),\omega (t)){\text{ (a deterministic function of }}\alpha (t),\omega (t){\text{)}}$

• $y_{i}(t)=Y_{i}(\alpha (t),\omega (t)){\text{ }}\forall i\in \{1,\ldots ,K\}{\text{ (deterministic functions of }}\alpha (t),\omega (t){\text{)}}$

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

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

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

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

${\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. Затем может быть определена новая штрафная функция y ( t ) = a ( t ) − c , и желаемое ограничение эквивалентно тому, что среднее по времени ожидание y ( t ) неположительно. Аналогично, предположим, что существуют два процесса a ( t ) и b ( t ), и требуется, чтобы среднее по времени ожидание a ( t ) было меньше или равно ожиданию b ( t ). Это ограничение записывается в стандартной форме путем определения новой штрафной функции y ( t ) = a ( t ) − b ( t ). Вышеупомянутая задача направлена ​​на минимизацию среднего по времени абстрактной штрафной функции p'( t )'. Это можно использовать для максимизации среднего по времени некоторой желательной функции вознаграждения r ( t ), определив p ( t ) = − r ('t ).

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

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

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

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

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

Поэтому:

$y_{i}(t)\leq Q_{i}(t+1)-Q_{i}(t)$

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

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

Разделив на t и взяв ожидания, получим:

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

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

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

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

Выражение «дрифт плюс штраф»

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

$L(t)={\frac {1}{2}}\sum _{i=1}^{K}Q_{i}(t)^{2}$

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

$Q_{i}(t+1)^{2}\leq (Q_{i}(t)+y_{i}(t))^{2}=Q_{i}(t)^{2}+y_{i}(t)^{2}+2Q_{i}(t)y_{i}(t)$

Поэтому,

${\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)$

Отсюда следует, что

$\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) ограничены. Затем:

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

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

$({\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 можно настроить так, чтобы уделять больше или меньше внимания минимизации штрафов, что приводит к компромиссу в производительности.

Алгоритм «дрифт плюс штраф»

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

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

Учитывая эти наблюдения для слота t, жадно выберите управляющее воздействие $\alpha (t)\in A$ чтобы минимизировать следующее выражение (произвольно разрывая связи):

$VP(\alpha (t),\omega (t))+\sum _{i=1}^{K}Q_{i}(t)Y_{i}(\alpha (t),\omega (t))$

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

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

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

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

${\begin{aligned}&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{aligned}}$

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

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

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

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

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

$({\text{Eq. }}3)\qquad E[P(\alpha ^{*}(t),\omega (t))]=p^{*}={\text{optimal time average penalty for the problem}}$

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

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

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

$\alpha (t)={\text{drift-plus-penalty action for slot }}t$

$\alpha ^{*}(t)=\omega {\text{-only action that satisfies (Eq.3)-(Eq.4)}}$

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

${\begin{aligned}\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))\end{aligned}}$

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

${\begin{aligned}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{ are independent of }}Q_{i}(t)\\&\leqslant B+C+Vp^{*}&&{\text{Using Eq. 3 and Eq. 4}}\end{aligned}}$

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

${\begin{aligned}(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{assume }}L(0)=0\\&\geqslant V\sum _{\tau =0}^{t-1}E[p(\tau )]&&L(t)\geqslant 0\end{aligned}}$

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

${\frac {1}{t}}\sum _{\tau =0}^{t-1}E[p(\tau )]\leqslant p^{*}+{\frac {B+C}{V}}.$

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

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

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

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

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

${\begin{aligned}\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{assume }}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{taking expectation}}\\E[\Delta (t)]+Vp_{\min }&\leqslant B+C+Vp_{\max }+\sum _{i=1}^{K}E[Q_{i}(t)](-\epsilon )&&{\text{Using (Eq. 5)}}\\E[\Delta (t)]+\epsilon \sum _{i=1}^{K}E[Q_{i}(t)]&\leqslant B+C+V(p_{\max }-p_{\min })\end{aligned}}$

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

${\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 для среднего размера очереди и штрафа с бесконечным горизонтом времени могут быть получены с использованием метода дрейфа плюс штрафа вместе с теорией мартингала .

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

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

Лечение систем массового обслуживания

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

Выпуклые функции средних по времени

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

${\text{Minimize}}\quad f\left({\overline {y}}_{1},\ldots ,{\overline {y}}_{K}\right)\quad {\text{subject to}}\quad g_{i}\left({\overline {y}}_{1},\ldots ,{\overline {y}}_{K}\right)\leqslant 0\qquad \forall i\in \{1,\ldots ,N\}$

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

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

Подобные задачи оптимизации выпуклых функций средних по времени можно трансформировать в задачи оптимизации средних по времени функций через вспомогательные переменные (см. главу 5 учебника Нили). Последние проблемы затем можно решить с помощью метода сноса плюс штраф, как описано в предыдущих подразделах. Альтернативный первично-двойственный метод принимает решения, аналогичные решениям «снос плюс штраф», но использует штраф, определяемый частными производными целевой функции. $f.$ Первично-двойственный подход также можно использовать для поиска локальных оптимумов в случаях, когда $f$ является невыпуклым.

Задержка компромиссов и связанных с ними работ

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

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

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

Расширения для процессов событий, отличных от iid

Известно, что алгоритм «дрейф плюс штраф» обеспечивает аналогичные гарантии производительности для более общих эргодических процессов. $\omega (t)$, так что предположение iid не имеет решающего значения для анализа. Можно показать, что алгоритм устойчив к неэргодическим изменениям вероятностей для $\omega (t)$. В определенных сценариях можно показать, что он обеспечивает желательные аналитические гарантии, называемые универсальными гарантиями планирования , для произвольных $\omega (t)$ процессы.

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

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

${\frac {E[\Delta [r]+Vp[r]\mid Q[r]]}{E[T[r]\mid Q[r]]}}$

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

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

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

$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\}\}$

где x _{min, i} , x _{max, i} — действительные числа, удовлетворяющие условиям $x_{\min ,i}<x_{\max ,i}$ для всех я . Пусть P ( x ) и $Y_{i}(x)$ для i в {1, ..., K } — непрерывные и выпуклые функции вектора x по всем x в A . Рассмотрим следующую задачу выпуклого программирования :

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

$({\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$

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

$\alpha (t)=x(t)=(x_{1}(t),x_{2}(t),\ldots ,x_{N}(t))$

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

• $p(t)=P(x_{1}(t),\ldots ,x_{N}(t))$

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

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

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

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

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

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

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

$({\text{Eq. }}9){\text{ }}{\text{subject to: }}\lim _{t\rightarrow \infty }{\overline {Y}}_{i}(t)\leq 0{\text{ }}\forall i\in \{1,\ldots ,K\}$

По неравенству Йенсена для всех слотов t>0 справедливо следующее:

$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). Далее, любой усредненный по времени вектор $\lim _{t\rightarrow \infty }{\overline {x}}(t)$ соответствующий решению задачи усреднения по времени (уравнение 8)–(уравнение 9), должен решать выпуклую программу (уравнение 6)–(уравнение 7). Следовательно, исходную выпуклую программу (уравнение 6)–(уравнение 7) можно решить (с любой желаемой точностью), взяв среднее по времени решений, принятых при применении алгоритма дрейфа плюс штрафа к соответствующему времени. -усредненная задача (уравнение 8)–(уравнение 9). Алгоритм «дрейф плюс штраф» для задачи (уравнение 8)–(уравнение 9) сводится к следующему:

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

Для каждого слота t выберите вектор $x(t)=(x_{1}(t),\ldots ,x_{N}(t))\in A$ минимизировать выражение:

$VP(x(t))+\sum _{i=1}^{K}Q_{i}(t)Y_{i}(x(t))$

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

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

Вектор среднего времени ${\overline {x}}(t)$ сходится к аппроксимации O(1/V) выпуклой программы.

Этот алгоритм аналогичен стандартному двойному субградиентному алгоритму теории оптимизации, использующему фиксированный размер шага 1/V. Однако ключевое отличие состоит в том, что алгоритм двойного субградиента обычно анализируется при ограничительных строгих предположениях о выпуклости, которые необходимы для основных переменных x ( t сходимости ). Есть много важных случаев, когда эти переменные не сходятся к оптимальному решению и даже не приближаются к оптимальному решению (это относится к большинству линейных программ , как показано ниже). С другой стороны, алгоритм «снос плюс штраф» не требует строгих предположений о выпуклости. Это гарантирует, что средние значения по времени простых чисел сходятся к решению, которое находится в пределах O (1/ V ) от оптимальности, с ограничениями O ( V ) на размеры очереди (можно показать, что это приводит к O ( V) ² ) с привязкой ко времени сходимости).

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

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

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

• $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 ), ( a _in ), ( b ₁ , …, b _K ). Тогда приведенный выше алгоритм сводится к следующему: для каждого слота t и для каждой переменной n в {1, …, N } выберите x _n ( t ) в [ x _{min, n} , x _{max, n} ], чтобы минимизировать выражение:

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

Затем обновите очереди Q _i ( t ), как и раньше. Это равносильно выбору каждой переменной x _i ( t ) в соответствии с простой политикой оперативного управления:

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

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

Поскольку основные переменные x _i ( t ) всегда являются либо x _{min, i,} либо x _{max, i} , они никогда не смогут сходиться к оптимальному решению, если оптимальное решение не является вершиной гиперпрямоугольника A . Однако средние по времени эти релейные решения действительно сходятся к O (1/ V аппроксимации оптимального решения ). Например, предположим, что x _min,1 = 0, x _max,1 = 1, и предположим, что все оптимальные решения линейной программы имеют x ₁ = 3/4. Тогда примерно в 3/4 случаев верным решением для первой переменной будет x ₁ ( t ) = 1, а в оставшееся время это будет x ₁ ( t ) = 0.

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

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

Первоисточники

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