Convex Necessary and Sufficient Conditions for Density Safety Constraints in Markov Chain Synthesis

This paper introduces a new approach for the synthesis of Markov chains with density safety constraints. Specific safety constraints considered are: (i) Density upper bound constraints; (ii) Bound on the rate of change of density. The proposed approach is based on a new mathematical result that formulates these constraints as linear, and hence convex, inequality constraints. The main contribution of the paper is that the new convex constraints are proved to be equivalent, necessary and sufficient, to the original constraints. This result enables the formulation of the Markov chain synthesis problem as a Linear Matrix Inequality (LMI) optimization problem with additional constraints on the steady state probability distribution, ergodicity, and feasible state transitions. The LMI formulation presents a necessary and sufficient design condition for reversible Markov chains, that is, it is not conservative. When the reversibility is not required, the LMI condition is only sufficient due to the ergodicity constraint. Since LMI problems can be solved to global optimality in polynomial time by using Interior Point Method algorithms, the proposed LMI-based design approach is numerically tractable.