A linear programming approach to online set membership parameter estimation for linear regression models
Corresponding Author
M. Casini
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Correspondence to: M. Casini, Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche Università di Siena, Via Roma 56, 53100 Siena, Italy.
E-mail: [email protected]
Search for more papers by this authorA. Garulli
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Search for more papers by this authorA. Vicino
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Search for more papers by this authorCorresponding Author
M. Casini
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Correspondence to: M. Casini, Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche Università di Siena, Via Roma 56, 53100 Siena, Italy.
E-mail: [email protected]
Search for more papers by this authorA. Garulli
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Search for more papers by this authorA. Vicino
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, Via Roma 56, Siena, 53100 Italy
Search for more papers by this authorSummary
This paper presents a new technique for online set membership parameter estimation of linear regression models affected by unknown-but-bounded noise. An orthotopic approximation of the set of feasible parameters is updated at each time step. The proposed technique relies on the solution of a suitable linear program, whenever a new measurement leads to a reduction of the approximating orthotope. The key idea for preventing the size of the linear programs from steadily increasing is to propagate only the binding constraints of these optimization problems. Numerical studies show that the new approach outperforms existing recursive set approximation techniques, while keeping the required computational burden within the same order of magnitude. Copyright © 2016 John Wiley & Sons, Ltd.
References
- 1Ljung L System Identification: Theory for the User (2nd ed.) Prentice Hall: Upper Saddle River, NJ, 1999.
10.1002/047134608X.W1046 Google Scholar
- 2Åström KJ, Wittenmark B Adaptive Control. Courier Corporation: Chelmsford, 2013.
- 3Isermann R Fault-Diagnosis Systems: An Introduction from Fault Detection to Fault Tolerance. Springer Science & Business Media: Berlin, 2006.
10.1007/3-540-30368-5 Google Scholar
- 4Bertsekas DP, Rhodes IB. Recursive state estimation for a set-membership description of uncertainty. IEEE Transactions on Automatic Control 1971; 16: 117–128.
- 5Schweppe FC Uncertain Dynamic Systems. Prentice Hall: Englewood Cliffs, NJ, 1973.
- 6Kurzhanski AB, Identification – a theory of guaranteed estimates. In From Data to Model, JC Willems (ed.). Springer: Berlin, 1989; 135–214.
10.1007/978-3-642-75007-6_4 Google Scholar
- 7Walter E, Piet-Lahanier H. Estimation of parameter bounds from bounded-error data: a survey. Mathematics in Computer and Simulation 1990; 32: 449–468.
- 8Milanese M, Vicino A. Estimation theory for nonlinear models and set membership uncertainty. Automatica 1991; 27: 403–408.
- 9Special issue on: Bounded-error estimation – part 1. International Journal of Adaptive Control and Signal Processing 1994; 8(1): 1–118.
- 10Special issue on: Bounded-error estimation – part 2. International Journal of Adaptive Control and Signal Processing 1995; 9(1): 1–132.
- 11Milanese M, Norton JP, Piet-Lahanier H, Walter E Bounding Approaches to System Identification. Plenum Press: New York, 1996.
10.1007/978-1-4757-9545-5 Google Scholar
- 12Special issue on: The set membership modelling of uncertainties in dynamical systems. Mathematical and Computer Modelling of Dynamical Systems 2005; 11(2): 123–249.
- 13Special issue on: Bounding methods for state and parameter estimation. International Journal of Adaptive Control and Signal Processing 2011; 25(3): 189–294.
- 14Cheng Y, Wang Y, Sznaier M, Ozay N, Lagoa C A convex optimization approach to model (in)validation of switched ARX systems with unknown switches. Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, Maui (Hawaii), 2012; 6284–6290.
- 15Ozay N, Sznaier M, Lagoa C. Convex certificates for model (in)validation of switched affine systems with unknown switches. IEEE Transactions on Automatic Control 2014; 59(11): 2921–2932.
- 16Ozay N, Lagoa C, Sznaier M. Set membership identification of switched linear systems with known number of subsystems. Automatica 2015; 51: 180–191.
- 17Cerone V, Piga D, Regruto D. Bounded error identification of Hammerstein systems through sparse polynomial optimization. Automatica 2012; 48(10): 2693–2698.
- 18Cerone V, Piga D, Regruto D. Computational load reduction in bounded error identification of Hammerstein systems. IEEE Transactions on Automatic Control 2013; 58(5): 1317–1322.
- 19Cerone V, Lasserre JB, Piga D, Regruto D. A unified framework for solving a general class of conditional and robust set-membership estimation problems. IEEE Transactions on Automatic Control 2014; 59(11): 2897–2909.
- 20Casini M, Garulli A, Vicino A. Input design in worst-case system identification with quantized measurements. Automatica 2012; 48(12): 2997–3007.
- 21Casini M, Garulli A, Vicino A. Feasible parameter set approximation for linear models with bounded uncertain regressors. IEEE Transactions on Automatic Control 2014; 59(11): 2910–2920.
- 22Cerone V, Piga D, Regruto D. A convex relaxation approach to set-membership identification of LPV systems. Automatica 2013; 49(9): 2853–2859.
- 23Pshenichnyi BN, Pokotilo VG. Minimax approach to the estimation of linear regression parameters. Engineering Cybernetics 1983; 21(2): 77–85.
- 24Belforte G, Tay TT. Two new estimation algorithms for linear models with unknown but bounded measurement noise. IEEE Transactions on Automatic Control 1993; 38(8): 1273–1279.
- 25Cerone V, Piga D, Regruto D. Improved parameters bounds for set-membership EIV problems. International Journal of Adaptive Control and Signal Processing 2011; 25(3): 208–227.
- 26Fogel E, Huang F. On the value of information in system identification – bounded noise case. Automatica 1982; 18: 229–238.
- 27Belforte G, Bona B, Cerone V. Parameter estimation algorithms for a set-membership description of uncertainty. Automatica 1990; 26: 887–898.
- 28Deller JR, Nayeri M, Liu MS. Unifying the landmark developments in optimal bounding ellipsoid identification. International Journal of Adaptive Control and Signal Processing 1994; 8(1): 43–60.
- 29Vicino A, Zappa G. Sequential approximation of feasible parameter sets for identification with set membership uncertainty. IEEE Transactions on Automatic Control 1996; 41: 774–785.
- 30Chisci L, Garulli A, Vicino A, Zappa G. Block recursive parallelotopic bounding in set membership identification. Automatica 1998; 34(1): 15–22.
- 31Kostousova EK. State estimation for dynamic systems via parallelotopes optimization and parallel computations. Optimization Methods and Software 1998; 9(4): 269–306.
- 32Bravo JM, Alamo T, Camacho EF. Bounded error identification of systems with time-varying parameters. IEEE Transactions on Automatic Control 2006; 51(7): 1144–1150.
- 33Blesa J, Puig V, Saludes J. Identification for passive robust fault detection using onotope-based set-membership approaches. International Journal of Adaptive Control and Signal Processing 2011; 25(9): 788–812.
- 34Casini M, Garulli A, Vicino A. On worst-case approximation of feasible system sets via orthonormal basis functions. IEEE Transactions on Automatic Control 2003; 48(1): 96–101.
- 35Ferreres G, M'Saad M. Estimation of output error models in the presence of unknown but bounded disturbances. International Journal of Adaptive Control and Signal Processing 1997; 11(2): 115–140.
- 36Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica 1984; 4(4): 373–395.
- 37Boyd S, Vandenberghe L Convex Optimization. Cambridge University Press: Cambridge (UK), 2004.
10.1017/CBO9780511804441 Google Scholar
- 38Casini M, Garulli A, Vicino A A constraint selection technique for recursive set membership identification. Proc. of 19th IFAC World Congress, Cape Town, South Africa, 2014 August; 1790–1795.
- 39Broman V, Shensa MJ. A compact algorithm for the intersection and approximation of n-dimensional polytopes. Mathematics and Computers in Simulation 1990; 32: 469–480.
- 40Blesa J, Puig V, Saludes J. Robust fault detection using polytope-based set-membership consistency test. IET Control Theory Applications 2012; 6(12): 1767–1777.
- 41 IBM. IBM ILOG Cplex Optimizer. Available from: http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ [Access on June 23, 2016].
- 42Casini M, Garulli A, Vicino A A constraint selection technique for set membership estimation of time-varying parameters. Proc. of 53rd IEEE Conference on Decision and Control, Los Angeles, CA, 2014 December; 1029–1034.
