Name
Title | ||
|---|---|---|
Convex optimization formulation of density upper bound constraints in Markov chain synthesis |
Abstract | ||
|---|---|---|
This paper introduces a new approach for the synthesis of Markov chains with density upper bound constraints. The proposed approach is based on a new mathematical result that formulates the density upper bound constraints, known also as safety constraints, as linear, and hence convex, inequality constraints. It is proved that the new convex constraints are equivalent, necessary and sufficient, to the density upper bound constraints, which is the main contribution. Next, this result enabled the formulation of the Markov chain synthesis problem as an Linear Matrix Inequality (LMI) optimization problem with additional constraints on the steady state probability distribution, ergodicity, and state transitions. The LMI formulation presents an equivalent design formulation in the case of reversible Markov chains, that is, it is not conservative. When reversibility assumption is relaxed, the LMI condition is only sufficient due to the ergodicity constraint, i.e., it is conservative. Since LMI problems can be solved to global optimality in polynomial time by using interior point method (IPM) algorithms of convex optimization, the proposed LMI-based design approach is numerically tractable. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ACC.2014.6859065 | American Control Conference |
Keywords | Field | DocType |
Markov processes,convex programming,linear matrix inequalities,IPM algorithms,LMI condition,LMI formulation,LMI optimization problem,LMI problems,LMI-based design,Markov chain synthesis problem,convex constraints,convex optimization formulation,density upper bound constraints,equivalent design formulation,ergodicity constraint,global optimality,inequality constraints,interior point method,linear matrix inequality,polynomial time,reversibility assumption,reversible Markov chains,safety constraints,state transitions,steady state probability distribution,LMIs,Markov processes,Optimization | Mathematical optimization,Global optimization,Convex combination,Nonlinear programming,Markov chain,Proper convex function,Convex optimization,Linear matrix inequality,Mathematics,Convex analysis | Conference |
ISSN | Citations | PageRank |
0743-1619 | 4 | 0.43 |
References | Authors | |
1 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nazli Demir | 1 | 4 | 0.43 |
| Behçet Açikmese | 2 | 41 | 15.88 |
| Matthew W. Harris | 3 | 4 | 0.43 |