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

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

Введение

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

Дрейф Ляпунова занимает центральное место в изучении оптимального управления в сетях массового обслуживания. Типичная цель — стабилизировать все сетевые очереди при одновременной оптимизации некоторых показателей производительности, например минимизации среднего энергопотребления или максимизации средней пропускной способности. Минимизация дрейфа квадратичной функции Ляпунова приводит к Алгоритм маршрутизации противодавления для стабильности сети, также называемый алгоритмом максимального веса . Добавление взвешенного штрафного члена к дрейфу Ляпунова и минимизация суммы приводит к алгоритму «дрейф плюс штраф» для совместной устойчивости сети и минимизации штрафа. Процедура «дрейф плюс штраф» также может использоваться для вычисления решений выпуклых и линейных программ .

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

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

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

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

Для каждого слота $t,$ определять:

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

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

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

Ограничение штрека Ляпунова

Предположим, что очереди в очереди меняются со временем согласно следующему уравнению:

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

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

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

Переставляя это неравенство, суммируя по всем $i,$ и деление на 2 приводит к:

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

где:

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

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

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

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

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

Основная теорема о сносе Ляпунова

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим ту же сеть массового обслуживания, что и в предыдущем разделе. Теперь определите $p(t)$ как сетевой штраф, наложенный на слот $t.$ Предположим, что цель состоит в том, чтобы стабилизировать сеть массового обслуживания, минимизируя при этом среднее время $p(t).$ Например, чтобы стабилизировать сеть при минимизации средней мощности за время, $p(t)$ может быть определен как общая мощность сети в слоте t. Для решения проблем максимизации среднего по времени некоторого желаемого вознаграждения. $r(t),$ наказание может быть определено $p(t)=-r(t).$ Это полезно для максимизации сети во всем коммунальном хозяйстве при условии стабильности.

Стабилизировать сеть, минимизируя среднее время штрафа. $p(t),$ сетевые алгоритмы могут быть разработаны для выполнения управляющих действий, которые жадно минимизируют границу следующего выражения дрейф плюс штраф для каждого слота $t$:

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

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

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

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

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

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

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

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

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

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

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

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

Суммируя вышесказанное по сравнению с первым $t$ слотов и использование закона телескопирования сумм дает:

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

Деление на $Vt$ а перестановка условий доказывает границу среднего по времени штрафа. Аналогичный аргумент доказывает ограничение среднего по времени размера очереди.

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

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

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

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