Optimización de Lyapunov

Este artículo describe la optimización de Lyapunov para sistemas dinámicos . Proporciona una aplicación de ejemplo 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 del 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. Normalmente, se define que la función crece cuando el sistema avanza hacia estados indeseables. La estabilidad del sistema se logra tomando acciones de control que hacen que la función de Lyapunov se desvíe en 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 y al mismo tiempo optimizar algún objetivo de rendimiento, como minimizar la energía promedio o maximizar el rendimiento promedio. Minimizar la deriva de una función cuadrática de Lyapunov 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 de la red conjunta 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 de 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. Suponga que hay colas en la red y defina el vector de los retrasos en las colas en el momento mediante: ${\displaystyle t\in \{0,1,2,\ldots \}.}$ ${\displaystyle N}$ ${\displaystyle t}$

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

Funciones cuadráticas de Lyapunov

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 del total de colas atrasadas en la red. Se llama función cuadrática de Lyapunov en 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 la cola cambian con el tiempo de acuerdo con 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 llegadas y oportunidades de servicio, respectivamente, en 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 se obtiene: ${\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}$

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

${\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 la deriva de Lyapunov

En muchos casos, la red se puede controlar de modo 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, todas las ranuras 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 siguiente teorema puede verse como una variación del teorema de Foster para las 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]} Supongamos que existen constantes tales que para todos y cada uno de los vectores posibles la deriva condicional de Lyapunov 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 de cola promedio en el tiempo 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}}.}$

Prueba. Tomando las expectativas de ambos lados de la desigualdad de deriva y usando la ley de expectativas iteradas se obtiene:

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

Sumando la expresión anterior y usando 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 )]}$

Usar el hecho de que no es negativo y reordenar los términos en la expresión anterior 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 el slot Supongamos que el objetivo es estabilizar la red en cola mientras se minimiza el tiempo promedio de Por ejemplo, para estabilizar la red mientras se minimiza el tiempo de potencia promedio, se puede definir como la potencia total incurrida por la red en el slot t. ^[8] Para tratar los problemas de maximizar el promedio de tiempo de alguna recompensa deseable , se puede definir la penalización. 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 y al mismo tiempo minimizar 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 una compensación de rendimiento. Una característica clave de este enfoque es que normalmente no requiere conocimiento de las probabilidades de eventos aleatorios de la red (como llegadas de trabajos aleatorias o realizaciones de canales). La elección se reduce a minimizar un límite en la deriva de 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]} Usar y definir como uso de energía de la red en la ranura conduce al algoritmo de deriva más penalización para minimizar la energía promedio sujeta a la estabilidad de la red desarrollado por Neely. ^[8] Usar y utilizar como 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 la 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 una generalización del teorema de la deriva de Lyapunov de la sección anterior. Para simplificar la exposición, supongamos que está limitado 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 sanción siempre no es negativa. Sea un parámetro utilizado para ponderar la importancia de alcanzar el objetivo. El siguiente teorema muestra que si se cumple una condición de deriva más penalización, entonces la penalización promedio de 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 de tiempo esté tan cerca (o por debajo) del objetivo como se desee, con la correspondiente compensación 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 hay constantes y tales que para todos y cada uno de 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)}$

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

Prueba. Tomando las expectativas de ambos lados de la deriva más penalización postulada y usando 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 en las primeras ranuras y usando 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}}}$

Dividir y reorganizar los términos demuestra el límite de la penalización promedio en el tiempo. Un argumento similar demuestra el límite del tamaño de cola promedio en el tiempo. ${\displaystyle Vt}$

Enlaces relacionados

• Deriva más penalización
• Enrutamiento de 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, págs. 1936-1948, diciembre. 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, núm. 2, págs. 466-478, marzo de 1993.
3. MJ Neely, E. Modiano y C. Li, "Equidad 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", Fundamentos y tendencias en redes , vol. 1, núm. 1, págs. 1-149, 2006.
5. MJ Neely. Optimización estocástica de redes con aplicación a sistemas de comunicación y colas, Morgan & Claypool, 2010.
6. MJ Neely, "Computación distribuida y segura de programas convexos a través de una red de procesadores conectados", DCDIS Conf, Guelph, Ontario, julio de 2005
7. E. Leonardi, M. Mellia, F. Neri y M. Ajmone Marsan, "Límites de retrasos promedio y promedios y variaciones del tamaño de la cola en conmutadores basados ​​en celdas en 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, núm. 7, págs. 2915-2934, julio de 2006.

Fuentes primarias

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