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 dynamical 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 Suppose there are queues in the network, and define the vector of queue backlogs at time by:
Quadratic Lyapunov functions
For each slot define:
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:
Bounding the Lyapunov drift
Suppose the queue backlogs change over time according to the following equation:
where and are arrivals and service opportunities, respectively, in queue on slot This equation can be used to compute a bound on the Lyapunov drift for any slot t:
Rearranging this inequality, summing over all and dividing by 2 leads to:
where:
Suppose the second moments of arrivals and service in each queue are bounded, so that there is a finite constant such that for all and all possible queue vectors the following property holds:
Taking conditional expectations of (Eq. 1) leads to the following bound on the conditional expected Lyapunov drift:
A basic Lyapunov drift theorem
In many cases, the network can be controlled so that the difference between arrivals and service at each queue satisfies the following property for some real number :
If the above holds for the same epsilon for all queues all slots and all possible vectors then (Eq. 2) reduces to the drift condition used in the following Lyapunov drift theorem. The theorem below can be viewed as a variation on Foster's theorem for Markov chains. However, it does not require a Markov chain structure.
Theorem (Lyapunov Drift). Suppose there are constants such that for all and all possible vectors the conditional Lyapunov drift satisfies:
Then for all slots the time average queue size in the network satisfies:
Proof. Taking expectations of both sides of the drift inequality and using the law of iterated expectations yields:
Summing the above expression over and using the law of telescoping sums gives:
Using the fact that is non-negative and rearranging the terms in the above expression proves the result.
Lyapunov optimization for queueing networks
Consider the same queueing network as in the above section. Now define as a network penalty incurred on slot Suppose the goal is to stabilize the queueing network while minimizing the time average of For example, to stabilize the network while minimizing time average power, can be defined as the total power incurred by the network on slot t. To treat problems of maximizing the time average of some desirable reward the penalty can be defined This is useful for maximizing network throughout utility subject to stability.
To stabilize the network while minimizing the time average of the penalty network algorithms can be designed to make control actions that greedily minimize a bound on the following drift-plus-penalty expression on each slot :