(411b) Tighter Bounds on Moment Trajectories of Stochastic Processes Via Semidefinite Programming | AIChE

(411b) Tighter Bounds on Moment Trajectories of Stochastic Processes Via Semidefinite Programming


Barton, P. I., Massachusetts Institute of Technology
Over the last decades, stochastic modeling has become an established paradigm in various disciplines including systems biology, operations research, mathematical finance and more. However, while stochastic models often provide more depth and higher utility than their deterministic counterparts, their analysis is generally more involved. In particular, many numerical analysis techniques for stochastic models such as sampling procedures or moment closure approximations are inherently approximate and lack the ability to rigorously quantify errors. This ultimately limits the utility of such approaches for robustness analysis and quantitative engineering applications. To address this deficiency, we focus in this work on a class of methods that we refer to as moment bounding schemes. Moment bounding schemes provide theoretically guaranteed lower and upper bounds for the moments associated with a given stochastic process. This is achieved via optimization of a truncated moment sequence subject to a set of so-called moment conditions reflecting the dynamics of the underlying stochastic process and the support of its distribution. By optimizing over increasingly large moment sequence truncations, the bounds can be tightened.

Moment bounding schemes for stationary as well as exit time and location distributions have been successfully employed in a range of applications including analysis of stochastic reaction networks [3, 8, 10, 5, 2], diffusion processes [11, 7] and the pricing of financial derivatives [6, 9]. In contrast, bounding schemes for moment trajectories are less well-established. In this work, we extend the recently proposed semidefinite programming based bounding scheme for transient moment solutions of the Chemical Master Equation by Dowdy and Barton [4]. The main contribution is a novel hierarchy of linear and semidefinite moment conditions which directly reflects temporal causality of the moment trajectories. These constraints allow to tighten the generated bounds considerably while possessing a favorable scaling behavior (linear vs. combinatorial) when compared to the set of moment conditions employed by Dowdy and Barton [4]. Additionally, we present a new bounding scheme based on a polynomial restriction of a related continuous-time optimal control problem. The resultant infinite dimensional optimization problem is reduced to a finite semidefinite program via a sum-of-squares characterizations of matrix polynomials [1] to enforce semidefinite constraints over the continuum of time. As an aside, we note that all results naturally extend to bounding the transient moments associated with stochastic processes described by Itô differential equations with polynomial drift and diffusion coefficients. We illustrate the results with examples drawn from stochastic chemical kinetics and other fields.

[1] A. A. Ahmadi and B. E. Khadir. Time-varying semidefinite programs. arXiv preprintarXiv:1808.03994, 2018.
[2] M. Backenköhler, L. Bortolussi, and V. Wolf. Bounding First Passage Times in Chemical Reaction Networks. In International Conference on Computational Methods in Systems Biology, pages 379–382. Springer, 2019.
[3] G. R. Dowdy and P. I. Barton. Bounds on stochastic chemical kinetic systems at steady state. The Journal of Chemical Physics, 148(8):084106, 2018.
[4] G. R. Dowdy and P. I. Barton. Dynamic bounds on stochastic chemical kinetic systems using semidefinite programming.The Journal of Chemical Physics, 149(7):074103,2018.
[5] K. R. Ghusinga, C. A. Vargas-Garcia, A. Lamperski, and A. Singh. Exact lower and up-per bounds on stationary moments in stochastic biochemical systems.Physical Biology,14(4):04LT01, 2017.
[6] K. Helmes, S. Röhl, and R. H. Stockbridge. Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming.Operations Research, 49(4):516–530, 2001.
[7] J. Kuntz, M. Ottobre, G.-B. Stan, and M. Barahona. Bounding stationary averages of polynomial diffusions via semidefinite programming. SIAM Journal on Scientific Computing, 38(6):A3891–A3920, 2016.
[8] J. Kuntz, P. Thomas, G.-B. Stan, and M. Barahona. Bounding the stationary distributions of the chemical master equation via mathematical programming.The Journal of Chemical Physics, 151(3):034109, 2019.
[9] J.-B. Lasserre, T. Prieto-Rumeau, and M. Zervos. Pricing a class of exotic options via moments and SDP relaxations. Mathematical Finance, 16(3):469–494, 2006.
[10] Y. Sakurai and Y. Hori. A convex approach to steady state moment analysis for stochastic chemical reactions. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 1206–1211. IEEE, 2017.
[11] E. Schwerer. A linear programming approach to the steady-state analysis of reflected Brownian motion. Stochastic Models, 17(3):341–368, 2001.


This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.


Do you already own this?



AIChE Pro Members $150.00
AIChE Emeritus Members $105.00
AIChE Graduate Student Members Free
AIChE Undergraduate Student Members Free
AIChE Explorer Members $225.00
Non-Members $225.00