Переход к навигации Переход к поиску

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

Содержание

• 1 Введение
• 2 Дрейф Ляпунова для сетей массового обслуживания
• 2.1 Квадратичные функции Ляпунова
• 2.2 Ограничение дрейфа Ляпунова
• 2.3 Основная теорема о дрейфе Ляпунова
• 3 Оптимизация по Ляпунову для сетей массового обслуживания
• 4 Ссылки по теме
• 5 Ссылок
• 6 Первичные Источники

Введение

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

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

Дрейф Ляпунова для сетей массового

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

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

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

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

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

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

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

Ограничение дрейфа Ляпунова

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

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

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

Q i (t + 1) 2 = (max { Q i (t) + a i (t) − b i (t), 0 }) 2 ⩽ (Q i (t) + a i (t) − b i (t)) 2 {\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}}

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

Δ L (t) ⩽ B (t) + ∑ i = 1 N Q i (t) (a i (t) − b i (t)) (E q.1) {\displaystyle \Delta L(t)\leqslant B(t)+\sum _{i=1}^{N}Q_{i}(t)(a_{i}(t)-b_{i}(t))\qquad (Eq.1)}

Где:

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

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

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