Оптимизация по Ляпунову

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

Введение [ править ]

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

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

Ляпуновский дрифт для сетей массового обслуживания [ править ]

Рассмотрим сеть массового обслуживания, которая развивается в дискретном времени с нормализованными временными интервалами. Предположим, что в сети есть очереди, и определите вектор невыполненных очередей во времени следующим образом:${\ displaystyle t \ in \ {0,1,2, \ ldots \}.}$${\ displaystyle N}$${\ displaystyle t}$

${\ Displaystyle Q (t) = (Q_ {1} (t), \ ldots, Q_ {N} (t))}$

Квадратичные функции Ляпунова [ править ]

Для каждого слота определите:${\ displaystyle t,}$

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

Эта функция является скалярной мерой общего количества невыполненных очередей в сети. Она называется квадратичной функцией Ляпунова по состоянию очереди. Определим дрейф Ляпунова как изменение этой функции от одного слота к другому:

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

Граница Ляпуновского дрейфа [ править ]

Предположим, что объем невыполненной работы очереди изменяется с течением времени в соответствии со следующим уравнением:

${\displaystyle Q_{i}(t+1)=\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}}$

где и - поступления и возможности обслуживания, соответственно, в очереди на слоте. Это уравнение можно использовать для вычисления границы дрейфа Ляпунова для любого слота t:${\displaystyle a_{i}(t)}$${\displaystyle b_{i}(t)}$${\displaystyle i}$${\displaystyle t.}$

${\displaystyle Q_{i}(t+1)^{2}=\left(\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}\right)^{2}\leqslant \left(Q_{i}(t)+a_{i}(t)-b_{i}(t)\right)^{2}}$

Переставив это неравенство, суммируя все и разделив на 2, получаем:${\displaystyle i,}$

${\displaystyle \Delta L(t)\leqslant B(t)+\sum _{i=1}^{N}Q_{i}(t)(a_{i}(t)-b_{i}(t))\qquad (Eq.1)}$

куда:

${\displaystyle B(t)={\frac {1}{2}}\sum _{i=1}^{N}\left(a_{i}(t)-b_{i}(t)\right)^{2}}$

Предположим, что вторые моменты поступления и обслуживания в каждой очереди ограничены, так что существует конечная константа, такая, что для всех и всех возможных векторов очереди выполняется следующее свойство:${\displaystyle B>0}$${\displaystyle t}$${\displaystyle Q(t)}$

${\displaystyle \mathbb {E} [B(t)|Q(t)]\leqslant B}$

Принятие условных ожиданий (уравнение 1) приводит к следующей оценке условного ожидаемого сноса Ляпунова :

${\displaystyle \mathbb {E} [\Delta L(t)|Q(t)]\leqslant B+\sum _{i=1}^{N}Q_{i}(t)\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\qquad (Eq.2)}$

Основная теорема Ляпунова о сносе [ править ]

Во многих случаях сеть можно контролировать так, чтобы разница между поступлением и обслуживанием в каждой очереди удовлетворяла следующему свойству для некоторого действительного числа :${\displaystyle \varepsilon >0}$

${\displaystyle \mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\leqslant -\varepsilon }$

Если вышесказанное верно для одного и того же эпсилона для всех очередей, всех слотов и всех возможных векторов, то (уравнение 2) сводится к условию сноса, используемому в следующей теореме о сносе Ляпунова. Приведенную ниже теорему можно рассматривать как вариацию теоремы Фостера для цепей Маркова . Однако для этого не требуется структура цепи Маркова.${\displaystyle i,}$${\displaystyle t,}$${\displaystyle Q(t),}$

Теорема (дрейф Ляпунова). ^{[5] [7]} Предположим, что существуют такие константы , что для всех и всех возможных векторов условный снос Ляпунова удовлетворяет:${\displaystyle B\geqslant 0,\varepsilon >0}$${\displaystyle t}$${\displaystyle Q(t)}$

${\displaystyle \mathbb {E} [\Delta L(t)|Q(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}Q_{i}(t).}$

Тогда для всех слотов средний по времени размер очереди в сети удовлетворяет:${\displaystyle t>0}$

${\displaystyle {\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}.}$

Доказательство. Принимая ожидания обеих сторон неравенства сноса и используя закон повторных ожиданий, получаем:

${\displaystyle \mathbb {E} [\Delta L(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]}$

Суммируя приведенное выше выражение и используя закон телескопических сумм, получаем:${\displaystyle \tau \in \{0,1,\ldots ,t-1\}}$

${\displaystyle \mathbb {E} [L(t)]-\mathbb {E} [L(0)]\leqslant Bt-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]}$

Использование неотрицательного факта и перестановка членов в приведенном выше выражении доказывает результат.${\displaystyle L(t)}$

Оптимизация по Ляпунову для сетей массового обслуживания [ править ]

Рассмотрим ту же сеть очередей, что и в предыдущем разделе. Теперь определите как сетевой штраф, понесенный в слоте. Предположим, цель состоит в том, чтобы стабилизировать сеть массового обслуживания при минимизации среднего времени. Например, для стабилизации сети при минимизации средней мощности по времени, можно определить как общую мощность, понесенную сетью в слоте. т. ^[8] Для решения проблем максимизации среднего времени некоторого желаемого вознаграждения может быть определен штраф. Это полезно для максимизации полезности пропускной способности сети при условии стабильности. ^[3]${\displaystyle p(t)}$${\displaystyle t.}$${\displaystyle p(t).}$${\displaystyle p(t)}$ ${\displaystyle r(t),}$${\displaystyle p(t)=-r(t).}$

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

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

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

В этом контексте важно обобщение теоремы Ляпунова о сносе из предыдущего раздела. Для простоты изложения предположим, что снизу ограничено:${\displaystyle p(t)}$

${\displaystyle p(t)\geqslant p_{\min }\quad \forall t\in \{0,1,2,...\}}$

Например, вышеперечисленное устраивает в случаях, когда штраф всегда неотрицательный. Позвольте представить желаемую цель для среднего значения времени Позвольте быть параметром, используемым для взвешивания важности достижения цели. Следующая теорема показывает, что если выполняется условие смещения плюс штраф, то среднее время штрафа не более чем на O (1 / V) превышает желаемую цель, в то время как средний размер очереди составляет O (V). Параметр может быть настроен , чтобы среднее время штрафа как можно ближе к (или ниже) мишень по желанию, с соответствующим размером очереди компромиссом.${\displaystyle p_{\min }=0}$${\displaystyle p(t)}$${\displaystyle p^{*}}$${\displaystyle p(t).}$${\displaystyle V}$${\displaystyle V}$

Теорема (оптимизация Ляпунова). Предположим, что существуют константы и такие, что для всех и всех возможных векторов выполняется следующее условие смещения плюс штраф:${\displaystyle \varepsilon >0,V,B\geqslant 0,}$${\displaystyle p^{*}}$${\displaystyle t}$${\displaystyle Q(t)}$

${\displaystyle \mathbb {E} [\Delta L(t)+Vp(t)|Q(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}Q_{i}(t)}$

Тогда за все время средний размер штрафа и средний размер очереди удовлетворяют:${\displaystyle t>0}$

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

${\displaystyle {\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B+V(p^{*}-p_{\min })}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}}$

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

${\displaystyle \mathbb {E} [\Delta L(t)]+V\mathbb {E} [p(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]}$

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

${\displaystyle {\begin{aligned}\mathbb {E} [L(t)]-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\\-\mathbb {E} [L(0)]+V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t&&{\text{Since }}L(t),Q_{i}(t)\geqslant 0\\V\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant p^{*}Vt+Bt+\mathbb {E} [L(0)]\end{aligned}}}$

Разделение и перестановка членов доказывают среднюю временную границу штрафа. Аналогичный аргумент доказывает, что средний размер очереди по времени ограничен.${\displaystyle Vt}$

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

• Дрифт плюс штраф
• Маршрутизация противодавления
• Функция Ляпунова
• Теорема Фостера
• Функция Control-Ляпунова

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

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

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