A linear programming approach to the steady-state analysis of reflected Brownian motion

We investigate a computational method proposed by Bertsimas, Paschalidis, and Tsitsiklis and by Kumar, Kumar, and Meyn for characterizing the steady-state behavior of Markov processes by means of bounds on the moments of their stationary distributions. In particular, we apply the method to the reflected Brownian motions (RBMs) used to model queueing networks in heavy traffic. In the RBM setting, the bounds are derived from the basic adjoint relationship (BAR), an assertion that in stationarity, the expected value of the differential generator of the RBM applied to a ‘good’ test function is zero. Coupled with appropriate choices of test functions, the BAR characterizes the stationary distribution of the RBM as the solution of a countable set of linear equations. Using polynomials as test functions, we derive a series of linear programs involving the moments of the stationary distribution as decision variables. We discuss the convergence of this series of linear programs and present numerical results for three sample networks.