Материал из Википедии — свободной энциклопедии

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

Материал из Википедии — свободной энциклопедии

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

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

Содержание

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

Ссылки

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

Ссылки

1.

 L. Тассиулас и А. Эфремидес, " Свойства стабильности систем массового обслуживания с ограниченными возможностями и политики планирования для максимальной пропускной способности в многосетевых радиосетях ", IEEE "Транзакции по автоматическому управлению", том 37, № 12, стр. 1936-1948, декабрь 1992.

  Л. Тассиулас и А. Эфремидес, " Динамическое распределение серверов для параллельных очередей со случайным изменением подключения ", IEEE Transactions по теории информации, том 39, № 2, стр. 466-478, март 1993.

  M. J. Нили, Э. Модиано и С. Ли, " Справедливость и оптимальное стохастическое управление для гетерогенных сетей ", Proc. IEEE INFOCOM, март 2005 г.

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

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

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

  E. Леонарди, М. Меллия, Ф. Нери и М. Аджмоне Марсан, " Оценки средних задержек и средних размеров очередей и отклонений в коммутаторах на основе ячеек с входными очередями ", Proc. IEEE INFOCOM, 2001.

8.  М. Дж. Нили, " Оптимальное управление энергией для изменяющихся во времени беспроводных сетей ", IEEE Transactions по теории информации, том 52, № 7, стр. 2915-2934, июль 2006.

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

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

Категории:

• Сетевые алгоритмы
• Теория массового обслуживания

https://en.wikipedia.org/wiki/Lyapunov_optimization

Функция Ляпунова

Содержание

• 1 Определение
• 1.1 Дальнейшее обсуждение терминов, возникающих в определении
• 2 Основные теоремы Ляпунова для автономных систем
• 2.1 Локально асимптотически устойчивое равновесие
• 2.2 Устойчивое равновесие
• 2.3 Глобально асимптотически устойчивое равновесие
• 3 Пример
• 4 См. также
• 5 Ссылок
• 6 Внешние ссылки

Определение

Стабильное равновесие

Если V {\displaystyle V} это функция Ляпунова, то равновесие устойчиво по Ляпунову. Обратное также верно и было доказано Дж. Л. Массерой.

Пример

Рассмотрим следующее дифференциальное уравнение с решением x {\displaystyle x} на R {\displaystyle \mathbb {R} }:

x ˙ = − x. {\displaystyle {\dot {x}}=-x.}

Учитывая, что x 2 {\displaystyle x^{2}} это всегда положительно в отношении происхождения, это естественный кандидат на роль функции Ляпунова, которая поможет нам в изучении x {\displaystyle x}. Так что давай V (x) = x 2 {\displaystyle V(x)=x^{2}} R {\displaystyle \mathbb {R} }. Затем,

V ˙ (x) = V ′ (x) x ˙ = 2 x ⋅ (− x) = − 2 x 2 < 0. {\displaystyle {\dot {V}}(x)=V'(x){\dot {x}}=2x\cdot (-x)=-2x^{2}<0.}

Это правильно показывает, что приведенное выше дифференциальное уравнение x, {\displaystyle x,} асимптотически устойчиво относительно начала координат. Обратите внимание, что, используя того же кандидата Ляпунова, можно показать, что равновесие также глобально асимптотически устойчиво.

См. также

• Стабильность Ляпунова
• Обыкновенные дифференциальные уравнения
• Управление-функция Ляпунова
• Функция Четаева
• Теорема Фостера
• Оптимизация по Ляпунову

Ссылки

• Вайнштейн, Эрик У. "Функция Ляпунова". Математический мир.
• Халил, Х. К. (1996). Нелинейные системы. Прентис-Холл, Аппер-Седл-Ривер, Нью-Джерси.
• La Salle, Joseph; Lefschetz, Solomon (1961). Устойчивость прямым методом Ляпунова: С приложениями. Нью-Йорк: Академическая пресса.
• Эта статья включает материал из функции Ляпунова на PlanetMath, которая лицензирована по лицензии Creative Commons Attribution/Share-Alike.

Внешние ссылки

• Пример определения устойчивости равновесного решения системы ОДУ с функцией Ляпунова

Контроль полномочий

Общая информация