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

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

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

Методология [ править ]

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

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

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

${\displaystyle \Delta L(t)+Vp(t),}$

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

Истоки и приложения [ править ]

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

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

Как это работает [ править ]

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

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

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

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

• ${\displaystyle 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:

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

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

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

• ${\displaystyle 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. Предполагается, что случайное событие принимает значения в некотором абстрактном наборе событий . Предполагается, что управляющее действие выбирается в некотором абстрактном наборе , содержащем варианты управления. Множества и произвольны и могут быть как конечными, так и бесконечными. Например, это может быть конечный список абстрактных элементов, бесчисленное множество (и, возможно, невыпуклый) набор векторов с действительными значениями и т. Д. Функции P (), Y_i () также произвольны и не требуют предположений непрерывности или выпуклости.${\displaystyle \omega (t)}$${\displaystyle \Omega }$${\displaystyle \alpha (t)}$${\displaystyle A}$${\displaystyle \Omega }$${\displaystyle A}$${\displaystyle A}$

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

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

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

${\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. Затем может быть определена новая функция штрафа 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) = - г ('т ).

Виртуальные очереди [ править ]

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

${\displaystyle ({\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) подразумевает:

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

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

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

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

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

Разделив на 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) как меру общего отставания очереди в слоте  t :

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

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

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

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

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

Алгоритм "дрейф плюс штраф" [ править ]

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

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

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

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

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

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

Примерное расписание [ править ]

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

${\displaystyle {\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-аддитивным приближением . ^[5] Случай C = 0 соответствует точной минимизации искомого выражения на каждом слоте  t .

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

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

Анализ среднего штрафа [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анализ среднего размера очереди [ править ]

Предположим, что теперь существует политика только-только , возможно, отличная от той, которая удовлетворяет (Уравнение 3) - (Уравнение 4), которая удовлетворяет следующему для некоторых :${\displaystyle \omega }$${\displaystyle \alpha ^{*}(t)}$${\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{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: ^[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{subject to}}\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]} Последние проблемы могут быть решены методом «дрейф плюс штраф», как описано в предыдущих подразделах. Альтернативный первично-дуальный метод принимает решения, аналогичные решениям о смещении плюс штраф, но использует штраф, определяемый частными производными целевой функции ^{[5] [16] [17]} Первично-дуальный подход также может использоваться для поиска локальных optima в случаях, когда невыпуклый. ^[5]${\displaystyle f.}$${\displaystyle f}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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 (t)}$${\displaystyle \alpha (t)}$

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

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

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

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

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

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

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

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

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

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

Этот алгоритм аналогичен стандартному двойному субградиентному алгоритму теории оптимизации, использующему фиксированный размер шага 1 / V. ^[26] Однако ключевое отличие состоит в том, что алгоритм двойного субградиента обычно анализируется при ограничительных предположениях о строгой выпуклости, которые необходимы для сходимости прямых переменных x ( t ). Есть много важных случаев, когда эти переменные не сходятся к оптимальному решению и даже не приближаются к оптимальному решению (это так для большинства линейных программ , как показано ниже). С другой стороны, алгоритм смещения плюс штраф не требует строгих предположений о выпуклости. Это гарантирует, что среднее времяпростых чисел сходятся к решению, которое находится в пределах O (1 / V ) от оптимальности, с ограничениями O ( V ) для размеров очереди (можно показать, что это переводится в ограничение O ( 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 ), ( a _in ), ( b ₁ ,…, b _K ). Затем приведенный выше алгоритм сводится к следующему: каждый слот t и для каждой переменной n в {1,…, N } выберите x _n ( t ) в [ x _{min, n} , x _{max, n} ], чтобы минимизировать выражение:

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

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

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

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

Ссылки по теме [ править ]

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

Ссылки [ править ]

Первоисточники [ править ]

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