×

Application of normal cones to the computation of solutions of the nonlinear Kolmogorov backward equation. (English) Zbl 07879227

Summary: A numerical approach to computing solutions of a generalized Kolmogorov backward equation is proposed, in which the stochastic matrix is replaced by a nonlinear operator obtained as the lower bound of a set of stochastic matrices. The equation is central to the theory of imprecise Markov chains in continuous time, which has made rapid progress in recent years. One of the obstacles to its implementation remains the high computational complexity, with the prevailing existing approaches relying on a discretization of the time interval. In order to achieve sufficient accuracy of the approximations, the grid must typically contain a large number of points on which optimization steps are performed, usually using linear programming. The main goal of this work is to develop a new, more efficient approach by significantly reducing the number of optimization steps required to achieve the prescribed accuracy of the solutions. Our approach is based on the Lipschitz continuity of the solutions of the equation with respect to time, which results in the optimization problems occurring at nearby points of the time interval having similar optimal solutions. This property is exploited using the theory of normal cones of convex polytopes. If the solution vectors remain within the same normal cone of a polytope corresponding to the nonlinear operator in a given interval, the optimization problem to be solved becomes linear, which allows much faster computations. This paper is primarily concerned with providing the theoretical basis for the new technique. However, initial tests show that it significantly outperforms existing methods in most cases.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
Full Text: DOI

References:

[1] Akrouche, J.; Sallak, M.; Châtelet, E.; Abdallah, F.; Chhadé, H. Haj, An interval approach for the availability optimization of multi-state systems in the presence of aleatory and epistemic uncertainties, ASCE-ASME J. Risk Uncertain. Eng. Syst., Part B: Mech. Eng., 8, 2, 2022
[2] Augustin, T.; Coolen, F. P.; de Cooman, G.; Troffaes, M. C., Introduction to Imprecise Probabilities, 2014, John Wiley & Sons · Zbl 1290.62003
[3] Bruckstein, A. M.; Elad, M.; Zibulevsky, M., Sparse nonnegative solution of a linear system of equations is unique, (2008 3rd International Symposium on Communications, Control and Signal Processing, 2008), 762-767
[4] Crossman, R. J.; Škulj, D., Imprecise Markov chains with absorption, Int. J. Approx. Reason., 51, 1085-1099, 2010 · Zbl 1211.60029
[5] De Bock, J., The limit behaviour of imprecise continuous-time Markov chains, Int. J. Nonlinear Sci., 27, 1, 159-196, 2017 · Zbl 1373.60131
[6] de Cooman, G.; Bock, J. D.; Lopatatzidis, S., Imprecise stochastic processes in discrete time: global models, imprecise Markov chains, and ergodic theorems, Int. J. Approx. Reason., 76, 18-46, 2016 · Zbl 1388.60129
[7] de Cooman, G.; Hermans, F.; Quaeghebeur, E., Imprecise Markov chains and their limit behavior, Probab. Eng. Inf. Sci., 23, 4, 597-635, 2009 · Zbl 1183.60026
[8] Erreygers, A.; De Bock, J., Imprecise continuous-time Markov chains: efficient computational methods with guaranteed error bounds, 2017, arXiv preprint
[9] Erreygers, A.; De Bock, J., Bounding inferences for large-scale continuous-time Markov chains: a new approach based on lumping and imprecise Markov chains, Int. J. Approx. Reason., 115, 96-133, 2019 · Zbl 1468.62331
[10] Erreygers, A.; De Bock, J., Markovian imprecise jump processes: extension to measurable variables, convergence theorems and algorithms, Int. J. Approx. Reason., 147, 78-124, 2022 · Zbl 07554494
[11] Erreygers, A.; Rottondi, C.; Verticale, G.; De Bock, J., Imprecise Markov models for scalable and robust performance evaluation of flexi-grid spectrum allocation policies, IEEE Trans. Commun., 66, 11, 5401-5414, 2018
[12] Gruber, P., Convex and Discrete Geometry, 2007, Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 1139.52001
[13] Krak, T.; De Bock, J.; Siebes, A., Imprecise continuous-time Markov chains, Int. J. Approx. Reason., 88, 452-528, 2017 · Zbl 1427.60164
[14] Krpelík, D.; Coolen, F. P.; Aslett, L. J., On robust Markov analysis for reliability assessment of complex systems using imprecise Markov chains, (2019 International Conference on Information and Digital Technologies (IDT), 2019, IEEE), 245-252
[15] Leela, S., Differential and Integral Inequalities Theory and Applications: Functional, Partial, Abstract and Complex Differential Equations, 1969, Academic Press: Academic Press New York · Zbl 1522.34002
[16] Lu, S.; Robinson, S. M., Normal fans of polyhedral convex sets, Set-Valued Anal., 16, 2, 281-305, 2008 · Zbl 1144.52008
[17] Miranda, E.; de Cooman, G., Marginal extension in the theory of coherent lower previsions, Int. J. Approx. Reason., 46, 1, 188-225, 2007 · Zbl 1148.68045
[18] Naghshbandi, S. N.; Varga, L.; Purvis, A.; Mcwilliam, R.; Minisci, E.; Vasile, M.; Troffaes, M.; Sedighi, T.; Guo, W.; Manley, E., A review of methods to study resilience of complex engineering and engineered systems, IEEE Access, 8, 87775-87799, 2020
[19] Nendel, M., Markov chains under nonlinear expectation, Math. Finance, 31, 1, 474-507, 2021 · Zbl 1522.91281
[20] Nendel, M., On nonlinear expectations and Markov chains under model uncertainty, Int. J. Approx. Reason., 130, 226-245, 2021 · Zbl 1490.60215
[21] Rottondi, C.; Erreygers, A.; Verticale, G.; De Bock, J., Modelling spectrum assignment in a two-service flexi-grid optical link with imprecise continuous-time Markov chains, (DRCN 2017-Design of Reliable Communication Networks; 13th International Conference, 2017, VDE), 1-8
[22] Troffaes, M.; Gledhill, J.; Škulj, D.; Blake, S., Using imprecise continuous time Markov chains for assessing the reliability of power networks with common cause failure and non-immediate repair, (Augustin, T.; Doria, S.; Miranda, E.; Quaeghebeur, E., ISIPTA ’15: Proceedings of the 9th International Symposium on Imprecise Probability: Theories and Applications. ISIPTA ’15: Proceedings of the 9th International Symposium on Imprecise Probability: Theories and Applications, Pescara, Italy, 20-24 July 2015, July 2015), 287-294
[23] Troffaes, M.; Krak, T.; Bains, H., Two-state imprecise Markov chains for statistical modelling of two-state non-Markovian processes, (The Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, vol. 103, 2019, PMLR), 394-403
[24] Škulj, D., Discrete time Markov chains with interval probabilities, Int. J. Approx. Reason., 50, 8, 1314-1329, sep 2009 · Zbl 1195.60100
[25] Škulj, D., A classification of invariant distributions and convergence of imprecise Markov chains, Linear Algebra Appl., 439, 9, 2542-2561, nov 2013 · Zbl 1287.60087
[26] Škulj, D., Efficient computation of the bounds of continuous time imprecise Markov chains, Appl. Math. Comput., 250, 165-180, jan 2015 · Zbl 1328.60180
[27] Škulj, D., Perturbation bounds and degree of imprecision for uniquely convergent imprecise Markov chains, Linear Algebra Appl., 533, 336-356, 2017 · Zbl 1386.60254
[28] Škulj, D., Computing bounds for imprecise continuous-time Markov chains using normal cones, (Vasile, M.; Quagliarella, D., Advances in Uncertainty Quantification and Optimization Under Uncertainty with Aerospace Applications: Proceedings of the 2020 Uqop International Conf, 2020)
[29] Škulj, D., A complete characterization of normal cones and extreme points for p-boxes, (Fuzzy Sets and Systems, 2022)
[30] Škulj, D., Normal cones corresponding to credal sets of lower probabilities, Int. J. Approx. Reason., 150, 35-54, November 2022 · Zbl 07611305
[31] Škulj, D.; Hable, R., Coefficients of ergodicity for Markov chains with uncertain parameters, Metrika, 76, 1, 107-133, dec 2013 · Zbl 1272.60052
[32] Walley, P., Statistical Reasoning with Imprecise Probabilities, 1991, Chapman and Hall: Chapman and Hall London, New York · Zbl 0732.62004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.