Linko(cid:127)ping Studies in Science and Technology. Dissertations No. 802 Local and Piecewise A(cid:14)ne Approaches to System Identi(cid:12)cation Jacob Roll Department of Electrical Engineering Linko(cid:127)ping University, SE{581 83 Linko(cid:127)ping, Sweden Linko(cid:127)ping 2003 Local and Piecewise A(cid:14)ne Approaches to System Identi(cid:12)cation (cid:13)c 2003 Jacob Roll [email protected] http://www.control.isy.liu.se Division of Automatic Control Department of Electrical Engineering Linko(cid:127)ping University SE{581 83 Linko(cid:127)ping Sweden ISBN 91-7373-608-2 ISSN 0345-7524 Printed by Bokakademin, Linko(cid:127)ping, Sweden 2003 Abstract Identi(cid:12)cation of nonlinear systems is a multifaceted research area, with many di- verse approaches and methods. This thesis considers two di(cid:11)erent approaches: (nonparametric) local modelling, and identi(cid:12)cation of piecewise a(cid:14)ne systems. Local models and methods predict the system behavior by constructing func- tion estimates from observations in a local neighborhood of the point of interest. For many local methods, it turns out that the function estimates are in practice weighted sums of the observations, so a central question is how to choose the weights. Manyoftheexistingmethodsaredesignedusingasymptotic(inthenum- ber of observations) arguments, which may lead to problems when only few data are available. To avoid this, an approach named direct weight optimization is pro- posed, where an upper bound on the worst-case mean squared error is minimized directly with respect to the weights of a linear or a(cid:14)ne estimator. It is shown that the estimator will have a (cid:12)nite bandwidth, and that it keeps several of the properties of an asymptotically optimal estimator. The case when bounds on the estimated function and its derivatives are known a priori is also studied, and it is shown that one can sometimes, but not always, bene(cid:12)tfromthisextrainformation. Theproblemofestimatingthefunctionderiva- tives is also considered. Another way of approaching the nonlinear system identi(cid:12)cation problem is to use a parameterized model class. Piecewise a(cid:14)ne systems are an interesting class forthispurpose. Theyhaveuniversalapproximationproperties,andarealsoclosely related to hybrid systems. Here, an overview of di(cid:11)erent approaches appearing in the literature is presented, and a new identi(cid:12)cation method based on mixed- integer programming is proposed. One notable property of the latter method is thattheglobaloptimumisguaranteedtobefoundwithina(cid:12)nitenumberofsteps. The complexity of the mixed-integer programming approach is discussed, and its relationstoexistingapproachesarepointedout. Thespecialcaseofidenti(cid:12)cationof Wiener models is considered in detail, since this model structure makes it possible to reduce the computational complexity. Some suboptimal modi(cid:12)cations of the mixed-integer programming approach are also investigated. Asforhybridsystemsingeneral,therehasbeenagrowinginterestforpiecewise a(cid:14)ne systems in recent years, and they occur in many application areas. In many cases, safety is an important issue, and there is a need for tools that prove that certainstatesareneverreached,orthatsomestatesarereachedin(cid:12)nitetime. The processofprovingthesekindsofstatementsiscalledveri(cid:12)cation. Manyveri(cid:12)cation tools for hybrid systems have emerged in the last ten years. They all depend on a model of the system, which will in practice be an approximation of the real system. Therefore, it would be desirable to learn how large the model errors can be,beforetheveri(cid:12)cationisnotvalidanymore. Inthisthesis,averi(cid:12)cationmethod forpiecewisea(cid:14)nesystemsispresented,whereboundsontheallowedmodelerrors are given along with the veri(cid:12)cation. i Acknowledgments Acknowledgments usually follow a rather standardized pattern. The main reason for this is probably that it is di(cid:14)cult to always (cid:12)nd new ways of expressing one’s gratitude. This acknowledgment is no exception. Nevertheless, even if the phrases are used many times before, I do mean all of them. With this in mind, (cid:12)rst of all I would like to thank my supervisor Professor Lennart Ljung, for excellent guidance and support during my time here at the Division of Automatic Control. I would also like to thank Professor Alexander Nazin, for a fruitful collaboration with many nice and interesting discussions, and for many valuable remarks on preliminary versions of the thesis. Also Dr. Alberto Bemporad deserves many thanks, for a nice and rewarding collaboration and for letting me visit the control group in the wonderful city of Siena. ThethesishasbeenproofreadbyMartinEnqvist, MarkusGerdin, DavidLind- gren, and Fredrik Tja(cid:127)rnstro(cid:127)m, for which I am extremely grateful. Earlier versions of the text have also been read by Ola Ha(cid:127)rkeg(cid:23)ard, Frida Gunnarsson, and Johan L(cid:127)ofberg. Your comments and remarks have been of great value and without doubt improved the quality of the thesis considerably. I would also like to thank M(cid:23)ans O(cid:127)string, Gustaf Hendeby, Rickard Karlsson, and Mikael Norrlo(cid:127)f for help with LATEX problems and similar issues. Ulla Salaneck has always been helpful when it comes to administrative and practical problems, and deserves much gratitude. Ola Ha(cid:127)rkeg(cid:23)ard and Fredrik Tja(cid:127)rnstro(cid:127)m also deserve special thanks for putting up with all kinds of questions with a never-ending en- thusiasm. In addition, many other people have been helpful during various phases of my work, and I thank all of you for your assistance. This work has been supported by the ECSEL graduate school in Linko(cid:127)ping, which is gratefully acknowledged. The spirit and atmosphere in the Control and Communication group is a great source of inspiration, not to be forgotten, and I would like to thank everyone in the group for being a part of this. Finally, I would like to thank Karin, for all the happiness we share and for always being there when I need you. You are the most valuable part of my life. Linko(cid:127)ping, March 2003 Jacob Roll iii iv Contents Notation xi 1 Introduction 1 1.1 Nonlinear Systems and Models . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Linear Models . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Some Speci(cid:12)c Nonlinear Model Classes. . . . . . . . . . . . . 4 1.1.3 Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 System Identi(cid:12)cation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Prediction Error Methods . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Identi(cid:12)cation of Piecewise A(cid:14)ne Systems . . . . . . . . . . . 8 1.2.3 Nonparametric Methods and Local Modelling . . . . . . . . . 9 1.3 Veri(cid:12)cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 Robust Veri(cid:12)cation . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 I Local Modelling Using Direct Weight Optimization 19 2 Nonparametric Methods and Local Modelling 21 v vi Contents 2.1 Introduction and Problem Formulation . . . . . . . . . . . . . . . . . 22 2.2 Kernel Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Local Polynomial Modelling . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Di(cid:11)erent Performance Criteria . . . . . . . . . . . . . . . . . . . . . 30 2.4.1 The MSE and MISE Criteria . . . . . . . . . . . . . . . . . . 30 2.4.2 The Mean Squared Prediction Error and Risk Function . . . 32 2.4.3 Classical Methods . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.4 Direct Plug-In Methods . . . . . . . . . . . . . . . . . . . . . 35 2.4.5 The Worst-Case MSE Criterion . . . . . . . . . . . . . . . . . 36 2.5 Kernel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1 Optimal Kernels . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6 Gaussian Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.7 A Direct Weight Optimization Approach . . . . . . . . . . . . . . . . 40 3 Local DWO Modelling of Univariate Functions 43 3.1 The DWO Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.1.1 Minimizing an Upper Bound on the Worst-Case MSE . . . . 45 3.2 Some Properties of the Approach . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Automatic Finite Bandwidth and Boundary Adaptation . . . 48 3.2.2 Explicit Expressions for the Optimal Weights . . . . . . . . . 56 3.2.3 Expressions for Nonnegative Weights . . . . . . . . . . . . . . 57 3.2.4 Relation to Local Polynomial Modelling . . . . . . . . . . . . 59 3.2.5 Asymptotic Behavior . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.6 The Estimated Function . . . . . . . . . . . . . . . . . . . . . 62 3.2.7 Global Models . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4 Proof of the Asymptotic Expressions in Theorem 3.4 . . . . . . . . . 67 4 Local DWO Modelling of Multivariate Functions 71 4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5 Using Prior Knowledge 79 5.1 The Univariate Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.1.1 Class F =F (L;(cid:14);(cid:1)) . . . . . . . . . . . . . . . . . . . . . . 81 2 5.1.2 Class F =F (L;(cid:1)) . . . . . . . . . . . . . . . . . . . . . . . 83 2 5.1.3 Class F =F (L;0) . . . . . . . . . . . . . . . . . . . . . . . . 85 2 5.1.4 Class F =F (L) . . . . . . . . . . . . . . . . . . . . . . . . . 86 2 5.1.5 QP Formulations . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.1.6 Proofs of Theorems 5.2 and 5.4 . . . . . . . . . . . . . . . . . 89 5.1.7 Adjusting the Estimate . . . . . . . . . . . . . . . . . . . . . 94 5.2 Estimating Multivariate Functions . . . . . . . . . . . . . . . . . . . 95 5.3 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Contents vii 6 Other Extensions 99 6.1 Estimating the Derivative . . . . . . . . . . . . . . . . . . . . . . . . 99 6.1.1 Class F =F (L;(cid:14);(cid:1)) . . . . . . . . . . . . . . . . . . . . . . 100 2 6.1.2 Class F =F (L;(cid:1)) . . . . . . . . . . . . . . . . . . . . . . . 102 2 6.1.3 Class F =F (L) . . . . . . . . . . . . . . . . . . . . . . . . . 104 2 6.1.4 QP Formulations . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.1.5 CanWeUsetheDerivativeEstimatetoImprovetheFunction Estimate? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.2 Minimizing the Exact Worst-Case MSE . . . . . . . . . . . . . . . . 106 6.2.1 Maximizing the MSE for Given Weights . . . . . . . . . . . . 108 6.2.2 Properties of the Exact Worst-Case MSE Solution . . . . . . 109 6.3 Other Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7 Conclusions 113 7.1 Using the DWO Approach for Dynamic Systems . . . . . . . . . . . 115 7.2 Adaptive Bandwidth Selection . . . . . . . . . . . . . . . . . . . . . 116 7.3 Structure of the Regression Vector . . . . . . . . . . . . . . . . . . . 118 7.4 Algorithmic and Implementation Issues . . . . . . . . . . . . . . . . 118 II Identi(cid:12)cation of Piecewise A(cid:14)ne Systems 121 8 Prediction Error Methods for System Identification 123 8.1 Prediction Error Methods . . . . . . . . . . . . . . . . . . . . . . . . 123 8.2 Numerical Minimization . . . . . . . . . . . . . . . . . . . . . . . . . 124 8.3 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 9 Piecewise Affine Systems 127 9.1 Continuous Time Models . . . . . . . . . . . . . . . . . . . . . . . . 127 9.1.1 Switched Systems . . . . . . . . . . . . . . . . . . . . . . . . 128 9.2 Discrete Time Models . . . . . . . . . . . . . . . . . . . . . . . . . . 129 9.2.1 Models in Regression Form . . . . . . . . . . . . . . . . . . . 129 9.2.2 Chua’s Canonical Representation and Hinging Hyperplane Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 9.2.3 Representations with Fixed Regions . . . . . . . . . . . . . . 133 9.3 State Jumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.4 Control and Analysis of Piecewise A(cid:14)ne Systems . . . . . . . . . . . 134 10 Identification of Piecewise Affine Systems 135 10.1 Existing Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.1.1 Identifying All Parameters Simultaneously . . . . . . . . . . . 138 10.1.2 Adding One Partition at a Time . . . . . . . . . . . . . . . . 138 10.1.3 Finding Regions and Models in Several Steps . . . . . . . . . 142 10.1.4 Using Predetermined Regions . . . . . . . . . . . . . . . . . . 145 10.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 viii Contents 11 PWA Identification Using MILP/MIQP 149 11.1 Formulating the Identi(cid:12)cation Problem as an MILP/MIQP Problem 151 11.1.1 Reformulating the Criterion Function . . . . . . . . . . . . . 152 11.1.2 Reformulating the Constraints . . . . . . . . . . . . . . . . . 153 11.1.3 Restricting the Search Space . . . . . . . . . . . . . . . . . . 156 11.1.4 Some Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 157 11.2 Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 11.2.1 Unknown Number of Positive Max Functions . . . . . . . . . 161 11.2.2 Discontinuous Hinging Hyperplane Models . . . . . . . . . . 164 11.2.3 Robust Hinging Hyperplane Models . . . . . . . . . . . . . . 166 11.2.4 General PWARX Systems . . . . . . . . . . . . . . . . . . . . 167 11.3 Computational Complexity and Theoretical Aspects . . . . . . . . . 169 11.3.1 Number of Feasible (cid:14) Combinations . . . . . . . . . . . . . . 169 11.4 Piecewise A(cid:14)ne Wiener Models . . . . . . . . . . . . . . . . . . . . . 172 11.4.1 Reformulating the Identi(cid:12)cation Problem . . . . . . . . . . . 173 11.4.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . 178 11.5 Using Suboptimal MILP/MIQP Solutions . . . . . . . . . . . . . . . 179 11.6 Using Change Detection to Reduce Complexity . . . . . . . . . . . . 184 11.6.1 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 11.6.2 Approximating General Nonlinear Systems . . . . . . . . . . 188 11.7 Related Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 III Robust Veri(cid:12)cation 193 12 Robust Verification 195 12.1 Some Notation and Assumptions . . . . . . . . . . . . . . . . . . . . 196 12.2 Problem Formulation for Known Systems . . . . . . . . . . . . . . . 197 12.3 The Problem of Robust Veri(cid:12)cation . . . . . . . . . . . . . . . . . . 199 12.4 Solutions to the Robust Veri(cid:12)cation Problems . . . . . . . . . . . . . 201 12.4.1 (cid:1)(v)=0, (cid:13) =0, (cid:14)(v) is Varied . . . . . . . . . . . . . . . . . 202 12.4.2 (cid:13) =0, (cid:1)(v) and (cid:14)(v) are Varied . . . . . . . . . . . . . . . . 202 12.4.3 Multiple Requirements . . . . . . . . . . . . . . . . . . . . . . 204 12.4.4 (cid:1)=0, (cid:14) and (cid:13) are Varied . . . . . . . . . . . . . . . . . . . . 204 12.4.5 (cid:1), (cid:14) and (cid:13) are Varied . . . . . . . . . . . . . . . . . . . . . . 206 12.5 Interpretations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.6 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . 207 12.7 Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 12.7.1 Inner Approximations . . . . . . . . . . . . . . . . . . . . . . 208 12.7.2 Switched Systems . . . . . . . . . . . . . . . . . . . . . . . . 210 12.8 An Example: A Chemical Reactor . . . . . . . . . . . . . . . . . . . 210 12.8.1 System Model. . . . . . . . . . . . . . . . . . . . . . . . . . . 211 12.8.2 What to Verify . . . . . . . . . . . . . . . . . . . . . . . . . . 212 12.8.3 Deriving Bounds for Parameter Uncertainties . . . . . . . . . 213