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

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

Вступление

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

Ляпуновский дрейф занимает центральное место в изучении оптимального управления в сетях массового обслуживания. Типичной целью является стабилизация всех сетевых очередей при оптимизации некоторых задач производительности, таких как минимизация средней энергии или максимизация средней пропускной способности. Минимизация дрейфа квадратичной функции Ляпунова приводит кмаршрутизация противодавления алгоритм стабильности сети, также называемый алгоритм максимального веса.^[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 (т) = { гидроразрыва {1} {2}} сумма _ {я = 1} ^ {N} Q_ {я} (т) ^ {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 }}

куда ${ Displaystyle а_ {я} (т)}$ и ${ displaystyle b_ {i} (t)}$ находятся в очереди прибытия и возможности обслуживания соответственно ${ displaystyle i}$ на слоте ${ displaystyle t.}$ Это уравнение можно использовать для вычисления границы сноса Ляпунова для любого паза 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}}

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

{ 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 (т)}$ имеет место следующее свойство:

{ Displaystyle mathbb {E} [В (т) | Q (т)] 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} [а_ {я} (т) -b_ {я} (т) | Q (т)] leqslant - varepsilon}

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

Теорема (дрейф Ляпунова).^[5]^[7] Предположим, есть постоянные

{ displaystyle B geqslant 0, varepsilon> 0}

такой, что для всех

{ displaystyle t}

и все возможные векторы

{ Displaystyle Q (т)}

условный ляпуновский дрейф удовлетворяет:

{ 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 тау ин {0,1, ldots, т-1 }}$ и, используя закон телескопических сумм, дает:

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

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

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

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

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

{ Displaystyle Delta L (t) + Vp (t)}

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

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

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

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

Теорема (оптимизация по Ляпунову). Предположим, есть постоянные

{ displaystyle varepsilon> 0, V, B geqslant 0,}

и

{ displaystyle p ^ {*}}

такое, что для всех

{ displaystyle t}

и все возможные векторы

{ Displaystyle Q (т)}

выполняется следующее условие смещения плюс штраф:

{ 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 {align} 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)] конец {выровнен}}}

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

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

Основные источники

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

[tass-radio-nets-1] а ^б Л. Тассиулас и А. Ефремид "Свойства устойчивости систем массового обслуживания с ограничениями и политики планирования для максимальной пропускной способности в многосетевых радиосетях, IEEE Transactions по автоматическому контролю, т. 37, нет. 12. С. 1936-1948, декабрь 1992 г.

[tass-server-allocation-2] а ^б Л. Тассиулас и А. Ефремид "Динамическое распределение сервера по параллельным очередям со случайным образом изменяющимся подключением, "IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, март 1993 г."

[neely-fairness-infocom05-3] а ^б ^c М. Дж. Нили, Э. Модиано и К. Ли "Справедливость и оптимальное стохастическое управление для гетерогенных сетей, "Proc. IEEE INFOCOM, март 2005 г."

[now-4] Л. Георгиадис, М. Дж. Нили и Л. Тассиулас "Распределение ресурсов и межуровневое управление в беспроводных сетях," Основы и тенденции в сети, т. 1, вып. 1. С. 1-149, 2006.

[sno-text-5] а ^б ^c М. Дж. Нили. Стохастическая оптимизация сети с приложением к системам связи и массового обслуживания, Морган и Клейпул, 2010 г.

[neely-dcdis-6] М. Дж. Нили "Распределенное и безопасное вычисление выпуклых программ в сети связанных процессоров, "DCDIS Conf, Гуэлф, Онтарио, июль 2005 г.

[leonardi-7] Э. Леонарди, М. Меллиа, Ф. Нери и М. Аджмоне Марсан "Границы средних задержек и средних значений размера очереди и отклонений в коммутаторах на основе ячеек с очередью ввода ", Proc. IEEE INFOCOM, 2001.

[neely-energy-it-8] а ^б М. Дж. Нили "Оптимальное энергопотребление для беспроводных сетей с изменяющимся временем "Транзакции IEEE по теории информации", том 52, № 7, стр. 2915-2934, июль 2006 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]