SDP vs. LP relaxations for the moment approach in some performance evaluation problems

Given a Markov process we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence of nonincreasing (resp. nondecreasing) upper (resp. lower) bounds. The results are compared to the linear Hausdorff moment conditions approach considered in the LP-relaxations of Helmes. The SDP relaxations are shown to be more general and more precise than the LP relaxation


Stochastic Models 20 (2004), 439--456.