×

Identification of piecewise affine systems via mixed-integer programming. (English) Zbl 1037.93023

This paper deals with identification of hybrid dynamical systems, by focusing attention on hinging hyperplanes and Wiener piecewise affine autoregressive exogenous models. The regression space is partitioned into polyhedra with affine submodels for each polyhedron. The authors use algorithms based on mixed-integer linear or quadratic programming converging to a global optimum. A change detection approach is proposed for the special case where the estimation data only seldom switches between the different submodels. In this way it is possible to weigh between optimality and complexity. Numerical examples are treated.

MSC:

93B30 System identification
93B12 Variable structure systems
90C11 Mixed integer programming

Software:

MIQP; XPRESS; BARON; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batruni, R., A multilayer neural network with piecewise-linear structure and back-propagation learning, IEEE Transactions on Neural Networks, 2, 3, 395-403 (1991)
[2] Bemporad, A. (2000). Identification of hybrid systems: Global convergence via mixed-integer programming; Bemporad, A. (2000). Identification of hybrid systems: Global convergence via mixed-integer programming
[3] Bemporad, A.; Ferrari-Trecate, G.; Morari, M., Observability and controllability of piecewise affine and hybrid systems, IEEE Transactions on Automatic Control, 45, 10, 1864-1876 (2000) · Zbl 0990.93010
[4] Bemporad, A., Garulli, A., Paoletti, S., & Vicino, A. (2003). A greedy approach to identification of piecewise affine models. In O. Maler & A. Pnueli (Eds.), Hybrid systems: Computation and control; Bemporad, A., Garulli, A., Paoletti, S., & Vicino, A. (2003). A greedy approach to identification of piecewise affine models. In O. Maler & A. Pnueli (Eds.), Hybrid systems: Computation and control · Zbl 1032.93500
[5] Bemporad, A., Mignone, D., & Morari, M. (1999). Moving horizon estimation for hybrid systems and fault detection. In Proceedings of American control conference; Bemporad, A., Mignone, D., & Morari, M. (1999). Moving horizon estimation for hybrid systems and fault detection. In Proceedings of American control conference
[6] Bemporad, A.; Morari, M., Control of systems integrating logic, dynamics, and constraints, Automatica, 35, 3, 407-427 (1999) · Zbl 1049.93514
[7] Bemporad, A., Roll, J., & Ljung, L. (2000b). Identification of hybrid systems via mixed-integer programming; Bemporad, A., Roll, J., & Ljung, L. (2000b). Identification of hybrid systems via mixed-integer programming · Zbl 1037.93023
[8] Bemporad, A., Roll, J., & Ljung, L. (2001). Identification of hybrid systems via mixed-integer programming. In Proceedings of the 40th IEEE conference on decision and control; Bemporad, A., Roll, J., & Ljung, L. (2001). Identification of hybrid systems via mixed-integer programming. In Proceedings of the 40th IEEE conference on decision and control · Zbl 1037.93023
[9] Bemporad, A., Torrisi, F. D., & Morari, M. (2000c). Optimization-based verification and stability characterization of piecewise affine and hybrid systems. In Hybrid systems: Computation and control; Bemporad, A., Torrisi, F. D., & Morari, M. (2000c). Optimization-based verification and stability characterization of piecewise affine and hybrid systems. In Hybrid systems: Computation and control · Zbl 0939.93523
[10] Branicky, M. S., Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, IEEE Transactions on Automatic Control, 43, 4, 475-482 (1998) · Zbl 0904.93036
[11] Branicky, M. S.; Borkar, V. S.; Mitter, S. K., A unified framework for hybrid controlModel and optimal control theory, IEEE Transactions on Automatic Control, 43, 1, 31-45 (1998) · Zbl 0951.93002
[12] Breiman, L., Hinging hyperplanes for regression, classification, and function approximation, IEEE Transactions on Information Theory, 39, 3, 999-1013 (1993) · Zbl 0793.62031
[13] Choi, C.-H.; Choi, J. Y., Constructive neural networks with piecewise interpolation capabilities for function approximations, IEEE Transactions on Neural Networks, 5, 6, 936-944 (1994)
[14] Chutinan, A.; Krogh, B. H., Computational techniques for hybrid system verification, IEEE Transactions on Automatic Control, 48, 1, 64-75 (2003) · Zbl 1364.93457
[15] Dash Associates (1999). XPRESS-MP user guide; Dash Associates (1999). XPRESS-MP user guide
[16] Ernst, S. (1998). Hinging hyperplane trees for approximation and identification. In Proceedings of the 37th IEEE conference on decision and control; Ernst, S. (1998). Hinging hyperplane trees for approximation and identification. In Proceedings of the 37th IEEE conference on decision and control
[17] Ferrari-Trecate, G.; Muselli, M.; Liberati, D.; Morari, M., A clustering technique for the identification of piecewise affine systems, Automatica, 39, 2, 205-217 (2003) · Zbl 1011.93508
[18] Gad, E. F.; Atiya, A. F.; Shaheen, S.; El-Dessouki, A., A new algorithm for learning in piecewise-linear neural networks, Neural Networks, 13, 4-5, 485-505 (2000)
[19] Gustafsson, F., Adaptive filtering and change detection (2000), Wiley: Wiley New York
[20] Hagenblad, A., & Ljung, L. (2000). Maximum likelihood estimation of Wiener models. In Proceedings of the 39th IEEE conference on decision and control; Hagenblad, A., & Ljung, L. (2000). Maximum likelihood estimation of Wiener models. In Proceedings of the 39th IEEE conference on decision and control
[21] Heemels, W. P.M. H.; De Schutter, B.; Bemporad, A., Equivalence of hybrid dynamical models, Automatica, 37, 7, 1085-1091 (2001) · Zbl 0990.93056
[22] Heredia, E. A.; Arce, G. R., Piecewise linear system modeling based on a continuous threshold decomposition, IEEE Transactions on Signal Processing, 44, 6, 1440-1453 (1996)
[23] Hush, D. R.; Horne, B., Efficient algorithms for function approximation with piecewise linear sigmoidal networks, IEEE Transactions on Neural Networks, 9, 6, 1129-1141 (1998)
[24] ILOG, Inc. (1999). CPLEX 6.5 user manual; ILOG, Inc. (1999). CPLEX 6.5 user manual
[25] Johansson, M.; Rantzer, A., Computation of piecewise quadratic Lyapunov functions for hybrid systems, IEEE Transactions on Automatic Control, 43, 4, 555-559 (1998) · Zbl 0905.93039
[26] Julián, P.; Desages, A.; Agamennoni, O., High level canonical piecewise linear representation using a simplicial partition, IEEE Transactions on Circuits and Systems I, 46, 463-480 (1999) · Zbl 0952.65019
[27] Julián, P.; Jordán, M.; Desages, A., Canonical piecewise-linear approximation of smooth functions, IEEE Transactions on Circuits and Systems—I: Fundamental Theory and Applications, 45, 5, 567-571 (1998) · Zbl 0915.41014
[28] Kahlert, C.; Chua, L. O., The complete canonical piecewise-linear representation—part iThe geometry of the domain space, IEEE Transactions on Circuits and Systems I, 39, 222-236 (1992) · Zbl 0748.94012
[29] Kalafatis, A. D.; Wang, L.; Cluett, W. R., Identification of Wiener-type nonlinear systems in a noisy environment, International Journal on Control, 66, 6, 927-941 (1997) · Zbl 0875.93079
[30] Lin, J.-N.; Unbehauen, R., Canonical piecewise-linear approximations, IEEE Transactions on Circuits and Systems I, 39, 8, 697-699 (1992) · Zbl 0765.41022
[31] Lovera, M.; Gustafsson, T.; Verhaegen, M., Recursive subspace identification of linear and nonlinear Wiener state-space models, Automatica, 36, 11, 1639-1650 (2000) · Zbl 0980.93015
[32] Lunze, J., Diagnosis of quantized systems based on a timed discrete-event model, IEEE Transactions on Systems, Man & Cybernetics, Part A, 30, 3, 322-335 (2000)
[33] Lygeros, J.; Tomlin, C.; Sastry, S., Controllers for reachability specifications for hybrid systems, Automatica, 35, 3, 349-370 (1999) · Zbl 0943.93043
[34] Medeiros, M. C., Resende, M. G. C., & Veiga, A. (1999). Piecewise linear time series estimation with GRASP; Medeiros, M. C., Resende, M. G. C., & Veiga, A. (1999). Piecewise linear time series estimation with GRASP · Zbl 1168.90590
[35] Murray-Smith, R., Johansen, T. A. (Eds.) (1997). Multiple model approaches to modelling and control; Murray-Smith, R., Johansen, T. A. (Eds.) (1997). Multiple model approaches to modelling and control
[36] Pucar, P.; Sjöberg, J., On the hinge-finding algorithm for hinging hyperplanes, IEEE Transactions on Information Theory, 44, 3, 1310-1319 (1998) · Zbl 1105.65308
[37] Roll, J. (2001). Robust verification and identification of piecewise affine systems; Roll, J. (2001). Robust verification and identification of piecewise affine systems
[38] Roll, J. (2003). Local and piecewise affine approaches to system identification; Roll, J. (2003). Local and piecewise affine approaches to system identification
[39] Sahinidis, N. V. (2000). BARON—Branch and reduce optimization navigator; Sahinidis, N. V. (2000). BARON—Branch and reduce optimization navigator
[40] Sjöberg, J.; Zhang, Q.; Ljung, L.; Benveniste, A.; Delyon, B.; Glorennec, P. Y.; Hjalmarsson, H.; Juditsky, A., Nonlinear black-box modeling in system identificationA unified overview, Automatica, 31, 12, 1691-1724 (1995) · Zbl 0846.93018
[41] Skeppstedt, A.; Ljung, L.; Millnert, M., Construction of composite models from observed data, International Journal on Control, 55, 1, 141-152 (1992) · Zbl 0742.93003
[42] Sontag, E. D., Nonlinear regulationThe piecewise linear approach, IEEE Transactions on Automatic Control, 26, 2, 346-358 (1981) · Zbl 0474.93039
[43] Sontag, E. D. (1996). Interconnected automata and linear systems: A theoretical framework in discrete-time. In R. Alur, T. A. Henzinger, & E. D. Sontag (Eds.), Hybrid systems III—verification and control; Sontag, E. D. (1996). Interconnected automata and linear systems: A theoretical framework in discrete-time. In R. Alur, T. A. Henzinger, & E. D. Sontag (Eds.), Hybrid systems III—verification and control
[44] Strömberg, J.-E., Gustafsson, F., & Ljung, L. (1991). Trees as black-box model structures for dynamical systems. In Proceedings of European control conference; Strömberg, J.-E., Gustafsson, F., & Ljung, L. (1991). Trees as black-box model structures for dynamical systems. In Proceedings of European control conference
[45] Wigren, T., Recursive prediction error identification using the nonlinear Wiener model, Automatica, 29, 4, 1011-1025 (1993) · Zbl 0776.93006
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.