SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems

Abstract

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 for the LP relaxations in Helmes et al. [Helmes, K., Röhl, S., Stockbridge, R.H. Computing moments of the exit time distribution for Markov processes by linear programming. Oper. Res. 2001, 49, 516–530]. The SDP relaxations are shown to be more general and more precise than the LP relaxations.

Key Words:

• Computational methods for Markov processes
• Semidefinite relaxations
• Linear relaxations

Mathematics Subject Classification:

• Primary 60H35
• 60J25
• Secondary 90C22

Acknowledgement

The authors wish to thank anonymous referees for their remarks and suggestions, that have helped us to improve the initial version of the paper.

Notes

^aMatlab is a trademark of The MathWorks, Inc.