Optimización de Lyapunov

En este artículo se describe la optimización de Lyapunov para sistemas dinámicos y se ofrece un ejemplo de aplicación para el control óptimo en redes de colas .

Introducción

La optimización de Lyapunov se refiere al uso de una función de Lyapunov para controlar de manera óptima un sistema dinámico. Las funciones de Lyapunov se utilizan ampliamente en la teoría de control para garantizar diferentes formas de estabilidad del sistema. El estado de un sistema en un momento determinado suele describirse mediante un vector multidimensional. Una función de Lyapunov es una medida escalar no negativa de este estado multidimensional. Por lo general, la función se define para que crezca cuando el sistema se mueve hacia estados indeseables. La estabilidad del sistema se logra tomando medidas de control que hagan que la función de Lyapunov se desvíe en la dirección negativa hacia cero.

La deriva de Lyapunov es fundamental para el estudio del control óptimo en redes de colas. Un objetivo típico es estabilizar todas las colas de la red mientras se optimiza algún objetivo de rendimiento, como minimizar la energía promedio o maximizar el rendimiento promedio. Minimizar la deriva de una función de Lyapunov cuadrática conduce al algoritmo de enrutamiento de contrapresión para la estabilidad de la red, también llamado algoritmo de peso máximo . ^{[1] [2]} Agregar un término de penalización ponderado a la deriva de Lyapunov y minimizar la suma conduce al algoritmo de deriva más penalización para la estabilidad conjunta de la red y la minimización de la penalización. ^{[3] [4] [5]} El procedimiento de deriva más penalización también se puede utilizar para calcular soluciones a programas convexos y programas lineales . ^[6]

Deriva de Lyapunov para redes de colas

Considere una red de colas que evoluciona en tiempo discreto con intervalos de tiempo normalizados. Supongamos que hay colas en la red y definamos el vector de atrasos en las colas en el tiempo mediante: ${\displaystyle t\in \{0,1,2,\ldots \}.}$ ${\displaystyle N}$ ${\displaystyle t}$

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

Funciones de Lyapunov cuadráticas

Para cada ranura defina: ${\displaystyle t,}$

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

Esta función es una medida escalar de la acumulación total de colas en la red. Se denomina función de Lyapunov cuadrática sobre el estado de la cola. Defina la deriva de Lyapunov como el cambio en esta función de una ranura a la siguiente:

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

Limitando la deriva de Lyapunov

Supongamos que los retrasos en las colas cambian con el tiempo según la siguiente ecuación:

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

donde y son las llegadas y las oportunidades de servicio, respectivamente, en la cola en el espacio. Esta ecuación se puede utilizar para calcular un límite en la deriva de Lyapunov para cualquier espacio 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}}$

Reordenando esta desigualdad, sumando todo y dividiendo por 2, obtenemos: ${\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)}$

dónde:

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

Supongamos que los segundos momentos de llegadas y servicio en cada cola están acotados, de modo que existe una constante finita tal que para todos y cada uno de los posibles vectores de cola se cumple la siguiente propiedad: ${\displaystyle B>0}$ ${\displaystyle t}$ ${\displaystyle Q(t)}$

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

Tomando expectativas condicionales de (Ec. 1) se llega al siguiente límite en la deriva de Lyapunov esperada condicional :

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

Un teorema básico de deriva de Lyapunov

En muchos casos, la red se puede controlar para que la diferencia entre llegadas y servicio en cada cola satisfaga la siguiente propiedad para algún número real : ${\displaystyle \varepsilon >0}$

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

Si lo anterior se cumple para el mismo épsilon para todas las colas, todos los slots y todos los vectores posibles , entonces (Ec. 2) se reduce a la condición de deriva utilizada en el siguiente teorema de deriva de Lyapunov. El teorema siguiente puede verse como una variación del teorema de Foster para cadenas de Markov . Sin embargo, no requiere una estructura de cadena de Markov. ${\displaystyle i,}$ ${\displaystyle t,}$ ${\displaystyle Q(t),}$

Teorema (deriva de Lyapunov). ^{[5] [7]} Supóngase que hay constantes tales que para todos los vectores posibles la deriva de Lyapunov condicional satisface: ${\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).}$

Luego, para todas las ranuras , el tamaño promedio de la cola en la red satisface: ${\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}}.}$

Demostración. Si tomamos las expectativas de ambos lados de la desigualdad de deriva y aplicamos la ley de expectativas iteradas obtenemos:

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

Sumando la expresión anterior y utilizando la ley de sumas telescópicas se obtiene: ${\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 )]}$

Utilizando el hecho de que no es negativo y reordenando los términos en la expresión anterior se demuestra el resultado. ${\displaystyle L(t)}$

Optimización de Lyapunov para redes de colas

Considere la misma red de colas que en la sección anterior. Ahora defina como una penalización de red incurrida en la ranura Suponga que el objetivo es estabilizar la red de colas mientras se minimiza el promedio de tiempo de Por ejemplo, para estabilizar la red mientras se minimiza la potencia promedio de tiempo, se puede definir como la potencia total incurrida por la red en la ranura t. ^[8] Para tratar problemas de maximización del promedio de tiempo de alguna recompensa deseable, la penalización se puede definir Esto es útil para maximizar la red en toda la utilidad sujeta a estabilidad. ^[3] ${\displaystyle p(t)}$ ${\displaystyle t.}$ ${\displaystyle p(t).}$ ${\displaystyle p(t)}$ ${\displaystyle r(t),}$ ${\displaystyle p(t)=-r(t).}$

Para estabilizar la red mientras se minimiza el tiempo promedio de la red de penalización, se pueden diseñar algoritmos para realizar acciones de control que minimicen con avidez un límite en la siguiente expresión de deriva más penalización en cada ranura : ^[5] ${\displaystyle p(t),}$ ${\displaystyle t}$

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

donde es un peso no negativo que se elige según se desee para afectar un equilibrio de rendimiento. Una característica clave de este enfoque es que normalmente no requiere conocimiento de las probabilidades de los eventos aleatorios de la red (como llegadas de trabajos aleatorios o realizaciones de canal). La elección se reduce a minimizar un límite en la deriva en cada ranura y, para el enrutamiento en redes de colas de múltiples saltos, se reduce al algoritmo de enrutamiento de contrapresión desarrollado por Tassiulas y Ephremides. ^{[1] [2]} El uso y la definición como el uso de potencia de la red en la ranura conduce al algoritmo de deriva más penalización para minimizar la potencia promedio sujeta a la estabilidad de la red desarrollado por Neely. ^[8] El uso y el uso como el negativo de una métrica de utilidad de control de admisión conduce al algoritmo de deriva más penalización para el control de flujo conjunto y el enrutamiento de red desarrollado por Neely, Modiano y Li. ^[3] ${\displaystyle V}$ ${\displaystyle V=0}$ ${\displaystyle V>0}$ ${\displaystyle p(t)}$ ${\displaystyle t}$ ${\displaystyle V>0}$ ${\displaystyle p(t)}$

En este contexto, es importante generalizar el teorema de deriva de Lyapunov de la sección anterior. Para simplificar la exposición, supongamos que está acotado desde abajo: ${\displaystyle p(t)}$

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

Por ejemplo, lo anterior se cumple en los casos en que la penalización siempre es no negativa. Sea un parámetro utilizado para ponderar la importancia de cumplir con el objetivo. El siguiente teorema muestra que si se cumple una condición de deriva más penalización, entonces la penalización promedio en el tiempo es como máximo O(1/V) por encima del objetivo deseado, mientras que el tamaño promedio de la cola es O(V). El parámetro se puede ajustar para hacer que la penalización promedio en el tiempo sea lo más cercana (o inferior) al objetivo que se desee, con una compensación correspondiente en el tamaño de la cola. ${\displaystyle p_{\min }=0}$ ${\displaystyle p(t)}$ ${\displaystyle p^{*}}$ ${\displaystyle p(t).}$ ${\displaystyle V}$ ${\displaystyle V}$

Teorema (Optimización de Lyapunov). Supongamos que existen constantes y tales que para todos los vectores posibles se cumple la siguiente condición de deriva más penalización: ${\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)}$

Entonces, para todo el tiempo, la penalización promedio y el tamaño promedio de la cola satisfacen: ${\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}}}$

Demostración. Tomando las expectativas de ambos lados de la deriva más la penalización planteada y utilizando la ley de expectativas iteradas, tenemos:

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

Sumando lo anterior sobre las primeras ranuras y utilizando la ley de sumas telescópicas se obtiene: ${\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}}}$

Dividiendo por y reordenando los términos se demuestra el límite de penalización promedio en el tiempo. Un argumento similar demuestra el límite de tamaño de cola promedio en el tiempo. ${\displaystyle Vt}$

Enlaces relacionados

• Deriva más penalización
• Enrutamiento por contrapresión
• Función de Lyapunov
• Teorema de Foster
• Función de control-Lyapunov

Referencias

1. L. Tassiulas y A. Ephremides, "Propiedades de estabilidad de sistemas de colas restringidas y políticas de programación para un rendimiento máximo en redes de radio de múltiples saltos", IEEE Transactions on Automatic Control , vol. 37, no. 12, pp. 1936-1948, diciembre de 1992.
2. L. Tassiulas y A. Ephremides, "Asignación dinámica de servidores a colas paralelas con conectividad que varía aleatoriamente", IEEE Transactions on Information Theory, vol. 39, no. 2, págs. 466-478, marzo de 1993.
3. MJ Neely, E. Modiano y C. Li, "Imparcialidad y control estocástico óptimo para redes heterogéneas", Proc. IEEE INFOCOM, marzo de 2005.
4. L. Georgiadis, MJ Neely y L. Tassiulas, "Asignación de recursos y control entre capas en redes inalámbricas", Foundations and Trends in Networking , vol. 1, núm. 1, págs. 1-149, 2006.
5. MJ Neely. Optimización de redes estocásticas con aplicación a sistemas de comunicación y colas, Morgan & Claypool, 2010.
6. MJ Neely, "Computación distribuida y segura de programas convexos en una red de procesadores conectados", Conferencia DCDIS, Guelph, Ontario, julio de 2005
7. E. Leonardi, M. Mellia, F. Neri y M. Ajmone Marsan, "Límites en los retrasos promedio y promedios y variaciones del tamaño de cola en conmutadores basados ​​en celdas con cola de entrada", Proc. IEEE INFOCOM, 2001.
8. MJ Neely, "Control óptimo de energía para redes inalámbricas que varían en el tiempo", IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, julio de 2006.

Fuentes primarias

• MJ Neely. Optimización de redes estocásticas con aplicación a sistemas de comunicación y colas , Morgan & Claypool, 2010.