×

Exact and approximate approaches to the identification of stochastic MAX-plus-linear systems. (English) Zbl 1302.93146

Summary: Stochastic max-plus linear systems, i.e., perturbed systems that are linear in the max-plus algebra, belong to a special class of discrete-event systems that consists of systems with synchronization but no choice. In this paper, we study the identification problem for such systems, considering two different approaches. One approach is based on exact computation of the expected values and consists in recasting the identification problem as an optimization problem that can be solved using gradient-based algorithms. However, due to the structure of stochastic max-plus linear systems, this method results in a complex optimization problem. The alternative approach discussed in this paper, is an approximation method based on the higher-order moments of a random variable. This approach decreases the required computation time significantly while still guaranteeing a performance that is comparable to the one of the exact solution.

MSC:

93C65 Discrete event control/observation systems
93E03 Stochastic systems in control theory (general)
93E12 Identification in stochastic control theory
93C05 Linear systems in control theory
90C52 Methods of reduced gradient type

Software:

UMDES
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramowitz MA, Stegun I (1964) Handbook of mathematical functions. National Bureau of Standards, US Government Printing Office, Washington DC · Zbl 0171.38503
[2] Akian M (2007) Representation of stationary solutions of Hamilton-Jacobi-Bellman equations: a max-plus point of view. In: Proceedings of the international workshop “Idempotent and Tropical Mathematics and Problems of Mathematical Physics”. Moscow, Russia
[3] Baccelli F, Cohen G, Olsder GJ, Quadrat JP (1992) Synchronization and linearity. Wiley, New York · Zbl 0824.93003
[4] Başar T, Bernhard P (1995) H∞-optimal control and related minimax design problems, 2nd edn. Birkhauser, Boston, Massachusetts
[5] Bemporad A, Borrelli F, Morari M (2003) Min-max control of constrained uncertain discrete-time linear systems. IEEE Trans Automat Contr 48(9):1600-1606 · Zbl 1364.93181 · doi:10.1109/TAC.2003.816984
[6] Boimond JL, Hardouin L, Chiron P (1995) A modeling method of SISO discrete-event systems in max-algebra. In: Proceedings of the 3rd European control conference. Rome, Italy, pp 2023-2026 · Zbl 1081.62034
[7] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, London, UK · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[8] Büeler, B.; Enge, A.; Fukuda, K.; Kalai, G. (ed.); Ziegler, G. (ed.), Exact volume computation for convex polytopes: a practical study, 131-154 (2000), Basel, Switzerland · Zbl 0960.68162
[9] Cassandras CG, Lafortune S (1999) Introduction to discrete event systems. Kluwer Academic Publishers, Boston, Massachusetts · Zbl 0934.93001 · doi:10.1007/978-1-4757-4070-7
[10] Cuninghame-Green RA (1979) Minimax algebra. Springer-Verlag, Berlin, Germany · Zbl 0399.90052 · doi:10.1007/978-3-642-48708-8
[11] Davis PJ, Rabinowitz P (1984) Methods of numerical integration, 2nd edn. Academic Press, New York · Zbl 0537.65020
[12] De Schutter B, van den Boom T, Verdult V (2002) State space identification of max-plus-linear discrete event systems from input-output data. In: Proceedings of the 41st IEEE conference on decision and control. Las Vegas, Nevada, pp 4024-4029
[13] Dekking FM, Kraaikamp C, Lopuhaä HP, Meester LE (2005) A modern introduction to probability and statistics. Springer, London, UK · Zbl 1079.60002
[14] Farahani SS, van den Boom T, van der Weide H, De Schutter B (2010) An approximation approach for model predictive control of stochastic max-plus linear systems. In: Proceedings of the 10th international workshop on discrete event systems (WODES’10). Berlin, Germany, pp 386-391
[15] Gallot F, Boimond JL, Hardouin L (1997) Identification of simple elements in max-algebra: application to SISO discrete event systems modelisation. In: Proceedings of the European control conference (ECC’97). Brussels, Belgium, paper 488
[16] Golub GH, Van Loan CF (1996) Matrix computations, 3rd edn. The John Hopkins University Press, Baltimore, Maryland · Zbl 0865.65009
[17] Goodwin GC, Payne RL (1977) Dynamic system identification: experiment design and data analysis. Academic Press, New York · Zbl 0578.93060
[18] Graham R, Knuth D, Patashnik O (1994) Concrete mathematics: a foundation for computer science, 2nd edn. Addison-Wesley, Boston, Massachusetts · Zbl 0836.00001
[19] Heidergott B, Olsder GJ, van der Woude J (2006) Max plus at work. Princeton University Press, Princeton, New Jersey
[20] Ho YC (ed) (1992) Discrete event dynamic systems: analyzing complexity and performance in the modern world. IEEE Press, Piscataway, New Jersey
[21] Ivelić S, Pečarić JE (2011) Remarks on “on a converse of Jensen’s discrete inequality” of S. Simić. Hindawi Publishing Corporation, Journal of Inequalities and Applications Article ID 309565 · Zbl 1217.26046
[22] Kalos MH, Whitlock PA (2008) Monte Carlo methods. Wiley-VCH, Weinheim, Germany · Zbl 1170.65302 · doi:10.1002/9783527626212
[23] Lasserre JB (1998) Integration on a convex polytope. Proc Am Math Soc 126(8):2433-2441 · Zbl 0901.65012 · doi:10.1090/S0002-9939-98-04454-2
[24] Ljung L (1999) System identification: theory for the user, 2nd edn. Prentice-Hall, Upper Saddle River, New Jersey · Zbl 0615.93004
[25] Mairesse, J., Stochastic linear systems in the (max,+) algebra, No. 199, 257-265 (1994), London, UK · Zbl 0823.68078 · doi:10.1007/BFb0033555
[26] Mattheiss TH, Rubin DS (1980) A survey and comparison of methods for finding all vertices of convex polyhedral sets. Math Oper Res 5(2):167-185 · Zbl 0442.90050 · doi:10.1287/moor.5.2.167
[27] McEneaney WM (2004) Max-plus eigenvector methods for nonlinear H-infinity problems: error analysis. SIAM J Control Optim 43:379-412 · Zbl 1101.93032 · doi:10.1137/S0363012902414688
[28] Menguy E, Boimond JL, Hardouin L, Ferrier JL (2000) A first step towards adaptive control for linear systems in max algebra. Discret Event Dyn Syst: Theory Appl 10(4):347-367 · Zbl 0976.93057 · doi:10.1023/A:1008363704766
[29] Olsder GJ, Resing JAC, de Vries RE, Keane MS, Hooghiemstra G (1990) Discrete event systems with stochastic processing times. IEEE Trans Automat Contr 35(3):299-302 · Zbl 0707.93068 · doi:10.1109/9.50340
[30] Papoulis A (1991) Probability, random variables, and stochastic processes. McGraw-Hill, Singapore · Zbl 0191.46704
[31] Pardalos PM, Resende MGC (eds) (2002) Handbook of applied optimization. Oxford University Press, Oxford, UK · Zbl 0996.90001
[32] Peterson JL (1981) Petri net theory and the modeling of systems. Prentice-Hall, Englewood Cliffs, New Jersey
[33] Pečarić JE, Beesack PR (1987) On knopp’s inequality for convex functions. Can Math Bull 30(3):267-272 · Zbl 0628.26012 · doi:10.4153/CMB-1987-038-1
[34] Resing JAC, de Vries RE, Hooghiemstra G, Keane MS, Olsder GJ (1990) Asymptotic behavior of random discrete event systems. Stoch Process Their Appl 36(2):195-216 · Zbl 0719.60071 · doi:10.1016/0304-4149(90)90091-6
[35] Rudin W (1987) Real and complex analysis, 3rd edn. McGraw-Hill Series in Higher Mathematics, McGraw-Hill, New York · Zbl 0925.00005
[36] Schullerus G, Krebs V (2001a) Diagnosis of batch processes based on parameter estimation of discrete event models. In: Proceedings of the European control conference 2001 (ECC’01). Porto, Portugal, pp 1612-1617
[37] Schullerus G, Krebs V (2001b) Input signal design for discrete event model based batch process diagnosis. In: Proceedings of the 4th IFAC workshop on on-line fault detection and supervision in the chemical process industries. Seoul, Korea · Zbl 1364.93181
[38] Schullerus G, Krebs V, De Schutter B, van den Boom T (2003) Optimal input signal design for identification of max-plus-linear systems. In: Proceedings of the 2003 European control conference (ECC’03). Cambridge, UK, paper 026 · Zbl 1117.93349
[39] Simić S (2009a) On a converse of Jensen’s discrete inequality. J Inequal Appl 2009(1):153080 · Zbl 1185.26053 · doi:10.1155/2009/153080
[40] Simić S (2009b) On an upper bound for Jensen’s inequality. Journal of Inequalities in Pure and Applied Mathematics 10(2), Article 60 · Zbl 1167.26310
[41] Somasundaram KK, Baras JS (2011) Solving multi-metric network problems an interplay between idempotent semiring rules. Linear Algebra Appl 435(7):1494-1512 · Zbl 1221.68034 · doi:10.1016/j.laa.2011.02.055
[42] van den Boom T, De Schutter B (2004) Model predictive control for perturbed max-plus-linear systems: a stochastic approach. Int J Control 77(3):302-309 · Zbl 1073.93040 · doi:10.1080/00207170310001656047
[43] van den Boom TJJ, De Schutter B, Verdult V (2003) Identification of stochastic max-plus-linear systems. In: Proceedings of the 2003 European control conference (ECC’03). Cambridge, UK, paper 104
[44] Willink R (2005) Normal moments and Hermite polynomials. Stat Probab Lett 73(3):271-275 · Zbl 1081.62034 · doi:10.1016/j.spl.2005.03.015
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.