This article describes Lyapunov optimization for dynamical systems. It gives an example application to optimal control in queueing networks.
Introduction Lyapunov optimization refers to the use of a Lyapunov function to optimally control a dynamic system. Lyapunov functions are used extensively in control theory to ensure different forms of system stability. The state of a system at a particular time is often described by a multi-dimensional vector. A Lyapunov function is a nonnegative scalar measure of this multi-dimensional state. Typically, the function is defined to grow large when the system moves towards undesirable states. System stability is achieved by taking control actions that make the Lyapunov function drift in the negative direction towards zero. Lyapunov drift is central to the study of optimal control in queueing networks. A typical goal is to stabilize all network queues while optimizing some performance objective, such as minimizing average energy or maximizing average throughput. Minimizing the drift of a quadratic Lyapunov function leads to the backpressure routing algorithm for network stability, also called the max-weight algorithm. Adding a weighted penalty term to the Lyapunov drift and minimizing the sum leads to the drift-plus-penalty algorithm for joint network stability and penalty minimization. The drift-plus-penalty procedure can also be used to compute solutions to convex programs and linear programs.
Lyapunov drift for queueing networks Consider a queueing network that evolves in discrete time with normalized time slots t ∈ { 0 , 1 , 2 , … } . {\displaystyle t\in \{0,1,2,\ldots \}.} Suppose there are N {\displaystyle N} queues in the network, and define the vector of queue backlogs at time t {\displaystyle t} by:
Q ( t ) = ( Q 1 ( t ) , … , Q N ( t ) ) {\displaystyle Q(t)=(Q_{1}(t),\ldots ,Q_{N}(t))}
Quadratic Lyapunov functions For each slot t , {\displaystyle t,} define:
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}}
This function is a scalar measure of the total queue backlog in the network. It is called quadratic Lyapunov function on the queue state. Define the Lyapunov drift as the change in this function from one slot to the next:
Δ L ( t ) = L ( t + 1 ) − L ( t ) {\displaystyle \Delta L(t)=L(t+1)-L(t)}
Bounding the Lyapunov drift Suppose the queue backlogs change over time according to the following equation:
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\}}
where a i ( t ) {\displaystyle a_{i}(t)} and b i ( t ) {\displaystyle b_{i}(t)} are arrivals and service opportunities, respectively, in queue i {\displaystyle i} on slot t . {\displaystyle t.} This equation can be used to compute a bound on the Lyapunov drift for any slot t:
… excerpt ends here. Continue reading the full article.
