Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Interval parameter estimation under model uncertainty

Interval parameter estimation under model uncertainty Mathematical and Computer Modelling of Dynamical Systems Vol. 11, No. 2, June 2005, 225 – 237 SERGEY A. NAZIN AND BORIS T. POLYAK* Institute of Control Services, Russian Academy of Sciences, Profsoyuznaya str. 65, 117997, Moscow, Russia This paper is devoted to the estimation of parameters of linear multi-output models with uncertain regressors and additive noise. The uncertainty is assumed to be described by intervals. Outer-bounding interval approximations of the non-convex feasible parameter set for uncertain systems are obtained. The method is based on the calculation of the interval solution for an interval system of linear algebraic equations and provides parameter estimators for models with a large number of measurements. Keywords: Interval uncertainty, interval equations, uncertain model, parameter estimation, parameter bounding 1. Introduction The set-membership estimation framework for uncertain systems has attracted much attention during the past few decades. It is an alternative to the stochastic approach where some prior information on the statistical distribution of errors is needed, because only bounds on uncertainty in system parameters and signals are required. This assumption is often much more acceptable in practice. Various types of compact sets (intervals, polytopes, ellipsoids, etc.) are usually used to characterize these bounds. They are called the membership set constraints on uncertain variables. The parameter estimation problem for uncertain dynamic systems is one of the most natural in this context. The problem is to determine bounds or set constraints on system parameters based on output measurements, the model structure and bounds on uncertain variables. In this paper we focus on the so-called interval type of uncertainty. This means that each component of an uncertain vector or matrix is assumed to belong to a known finite interval. Although the description is natural and simple [1], combinatorial difficulties may become so severe as to make estimation intractable especially in the multidimensional case. The goal of the paper is to construct an *Corresponding author. E-mail: boris@ipu.rssi.ru Mathematical and Computer Modelling of Dynamical Systems ISSN 1387-3954 print/ISSN 1744-5051 online ª 2005 Taylor & Francis Group Ltd http://www.tandf.co.uk/journals DOI: 10.1080/138950500069243 226 S. Nazin and B. Polyak effective interval parameter estimator for an uncertain multi-output static system that can be used with large sets of data. Consider a linear regression model under interval uncertainty y ¼ Cx þ w; ð1Þ n m where x 2 R is an unknown parameter vector, y 2 R denotes a vector of results of mn m measurements, C 2 R is a matrix of regressors and w 2 R is an unknown vector of measurement errors. The classical parameter bounding approach is based on the assumption that the matrix C is known precisely, while the vector w is bounded and lies in the box w 2½w; w where w and w are known. This inclusion is understood componentwise. For instance, the set of all feasible parameter vectors x compatible with a single measurement y 2 R is the strip between two hyperplanes n T S ¼ x 2 R : y  w  c x  y  w : ð2Þ i i i i i The sequence of measurements y , ..., y then provides a convex polytope S .A 1 m i i¼1 number of methods has been developed to characterize this polytope or to construct outer-bounding approximations of it (see [2,3,4,5,6]). The present paper deals with the more general problem of where the matrix of mn regressors is also uncertain, i.e. C2C, and C is an interval matrix (C 2 IR ). This situation arises in many real-life problems when we do not have complete information concerning the plant. Furthermore, weakly non-linear systems can be treated in the same manner if non-linearity is replaced by uncertainty. Particular cases of this problem have been considered in the literature [3,7,8]. Any matrix or vector is said to belong to the interval family if its elements are from some real intervals [a;b], a 4 b. mn The standard notation IR indicates the space of all interval (m6 n) -matrices and IR is the space of all n-dimensional interval vectors. The presence of matrix uncertainty in the model leads to serious difficulties due to the non-convexity of the resulting set constraints. In [9,10] ellipsoidal techniques were applied to state and parameter estimation for linear models with matrix uncertainty where non-convexity of reachable and feasible parameter sets was pointed out. The main purpose of this article is to apply an interval technique to parameter estimation. The basic tool for this is the interval solution of linear interval systems of equations. The paper is organized as follows. Section 2 states the problem in detail. The scalar- measurement case is considered in section 3. In the multi-dimensional case the idea is to split a given linear model into a number of interval systems of linear algebraic equations. A simple method for solving these systems is proposed, which easily computes an optimal interval solution for moderate-scale problems (section 4.2) whereas for large-scale problems effective interval over-bounding solutions are obtained (section 4.3). The resulting method for parameter bounding is finally described in section 5. 2. Problem statement Consider a multi-output model with measurement noise and uncertainty in the matrix of regressors y ¼ðC þ DCÞ x þ w; ð3Þ Interval Parameter Estimation under Model Uncertainty 227 n m mn m where x 2 R , y 2 R , C 2 R and w 2 R . The number of measurements is usually much larger than the dimension of the parameter vector, so m  n. Assume jjDCjj  E; jjwjj  d: ð4Þ 1 1 The infinity norms of matrices and vectors are equal to the maximal absolute value of their elements, i.e. jjDCjj ¼ max jðDCÞ j ; jjwjj ¼ max jw j: ð5Þ 1 ij 1 1im; 1jn 1im Inequality (4) describes a particular case of interval uncertainty when all components of DC or w have the same bounds. The matrix C, vector y and scalars E, d are assumed to be known. All vectors x 2 R satisfying (3) under the constraints (4) form the feasible parameter set X ¼ x 2 R : y ¼ðC þ DCÞx þ w; jjDCjj  E; jjwjj  d : ð6Þ 1 1 Assume that x2X , where X 2 IR . The initial approximation X should be taken 0 0 0 large enough to guarantee inclusion of all parameter vectors of interest. The problem is to construct a more accurate outer-bounding interval approximation for the vector x in accordance with the large number of measurements {y , ..., y } and model structure 1 m (3) – (4). In other words, we look for an interval vector X 2 IR (preferably of minimal size) containing the intersection X \ X. 3. Scalar observation The single-measurement case (m = 1) is a good particular example of the parameter estimation. Set X for the scalar model y ¼ðc þ DcÞ x þ w ð7Þ where x 2 R ; y 2 R;jjDcjj  E and jwj d can be explicitly rewritten as n T X ¼fx 2 R : jy  c xj Ejjxjj þ dg; ð8Þ where jjxjj ¼ jx j. Figure 1 depicts a typical shape of X , which is non-convex for i 1 1 i¼1 any E4 0 (the region between two solid polygonal lines). This set reduces to a strip as n k E?0. However it is convex in each orthant of R . Let E be the k-th orthant of the n k vector space, k=1, ..., 2 .If x2E for any fixed number k, the right-hand side of the inequality in (8) becomes a linear function and therefore X \ E is a convex set. Assume x2X . Then the smallest interval vector X containing X \ X can be found 0 0 1 by solving a linear programming problem in each orthant of R . Indeed, the vector k k k k s = sign x for x2E is uniquely defined with elements s such that js j¼ 1. Thus i i () k T k X \ E ¼ x 2 R : jy  c xj E x s þ d ð9Þ 1 i i¼1 is a convex set given by linear constraints. Denote by e the j-th unit coordinate vector of R , j=1, ..., n. Then the j-th lower and upper bounds on the intersection X \ X \ E are calculated by linear programming as 0 1 228 S. Nazin and B. Polyak k j j x ¼ arg min ðe ; xÞ; x ¼ arg max ðe ; xÞ; ð10Þ j j k k x2X \X \E x2X \X \E 0 1 0 1 k k k k k where (,) denotes the scalar product. Hence X ¼ð½x ; x ; ... ;½x ; x Þ gives an 1 1 n n interval vector that is the minimal box containing X \ X \ E . 0 1 Notice however that the intersection of the set X \ X with some orthants may be 0 1 empty. The calculations in these orthants can obviously be omitted as long as the linear programming problem (10) turns out to become infeasible. Further, let K ¼fk : X \ X \ E 6¼;g. Then {E :k2K} represents a family of 0 1 orthants containing X \ X . Checking all orthants E such that k2K we obtain the 0 1 inclusion X \ X X . Finally, take 0 1 k2K no no x ¼ min x ; x ¼ max x ; i ¼ 1; ... ; n: ð11Þ i i i i k2K k2K X ¼ð½x ; x ; ... ;½x ; x Þ gives the optimal interval approximation of X \ X . 1 1 n n 0 1 T T Example 1. Let X =([7 1,4],[7 0.5,5]) and y=0, c = (1,1) , E = d = 0.5. The set X ¼f x 2 R : 2jx þ x jjx jþ jx jþ 1g is shown in figure 2 (shaded region). The 1 1 2 1 2 auxiliary interval vectors X are found via linear programming according to (10) in k T each orthant E , k = 1, . . ., 4 (bold boxes). Then X=([7 1,2.5],[7 0.5,4]) . In the multi-output case, one can consider the scalar observations recursively and apply the above linear programming procedure. However this technique becomes unsuitable for models with a large number of measurements (m  n). The main idea of the present paper is to consider blocks of n measurement equations in (3) and to treat each of them as a system of linear algebraic equations under interval uncertainties. A Figure 1. Feasible parameter set (single measurement). Interval Parameter Estimation under Model Uncertainty 229 simple algorithm to obtain an interval solution for this system is described in the following section. 4. Interval system of linear algebraic equations nn Let C 2 R , i.e. the number of parameters is equal to the number of observations. Then rewrite (3) in the form ðA þ DAÞ x ¼ b þ Db ð12Þ with A = C, b = y, DA =DC and Db=– w such that jjDAjj 4E, jjDbjj 4d. ? ? The calculation of the interval solution for the interval system of equations (12) is a challenging problem in numerical analysis and robust linear algebra. This problem was first considered in the 1960s by Oettli and Prager [11]. Since then, the problem has attracted much attention and was developed in the context of the modelling of uncertain systems. nn Assume that the matrix family A ¼fA þ DA : jjDAjj  Eg2 IR is non-singular (it contains no singular matrix) and that the interval vector is b ¼fb þ Db : jjDbjj  dg2 IR . Then for any A 2 A and any b 2 b the ordinary linear system Ax = b has a unique solution. We are interested in a set X of all these solutions of the interval system: X ¼fg x 2 R : Ax ¼ b; A 2 A; b 2 b : ð13Þ Our main objective is to find an interval solution of the linear interval system (12), that is, to determine the smallest interval vector X containing all possible solutions Figure 2. Single-output interval parameter bounding. 230 S. Nazin and B. Polyak (13). In other words, we want to embed the solution set X into the minimal box in R . This problem is known to be NP-hard [12] and complicated from a computational viewpoint for large-scale systems. Paper [11] shows how multiple linear programming can be used to obtain X ; this line of research was continued in [13,14]. Iterative approaches have been established at this context as well as direct numerical methods that provide an over-bounding of X ; see the monographs [15,16] and papers [17,18]. In this section we briefly describe a simple approach proposed in [19] for interval approximation of the solution set. Instead of employing linear programming in each orthant it is suggested to deal with a scalar equation. This method is based on Rohn’s result [17] and simplifies his algorithm. In order to find the optimal interval estimate X ^ ^ of the solution set X, all vertices of its convex hull Conv X should be obtained. The search of each vertex is via the solution of a scalar equation. In the case of large-scale systems we also provide a simple and fast procedure for over-bounding of the optimal interval solution. 4.1. The solution set A detailed description of the solution set for the linear interval systems was given in the pioneering work by Oettli and Prager [11] for a general situation of interval uncertainty. In our case their result is reduced as follows. Lemma 1 (Oettli & Prager [11]) The set of all admissible solutions of the system (12) is a non-convex polytope: X ¼fx 2 R : jjAx  bjj  Ejjxjj þ dg: ð14Þ 1 1 This result also follows from (8). The set X remains bounded as long as the interval matrix A is regular. This regularity is characterized by a non-singularity radius. For the interval family A this radius is equal to rðAÞ¼ ; ð15Þ jjA jj 1;1 see [20] for details. Recall that for any matrix G its (?,1) -norm is defined as jjGjj ¼ max jjGxjj : ð16Þ 1;1 1 jjxjj 1 Note also that the calculation of this norm is NP-hard. ^ ^ While E5 r(A), A remains regular and X is bounded. If the solution set X lies in a given orthant of R , then it becomes convex, and the search for its interval approximation reduces to convex optimization. However this is no longer the case in most situations, and the problem then meets combinatorial difficulties. 4.2. Optimal interval estimates of the solution set The problem is to determine exact lower x and upper x bounds on each component x i i i of the vector x 2 R under the assumption that x 2 X. The approach is focused on Interval Parameter Estimation under Model Uncertainty 231 ^ ^ searching for vertices of the convex hull Conv X of the solution set X instead of employing linear programming in each orthant. The main base for this technique is the paper by Rohn [17], where a key result defining Conv X was proved. Let S be the set of vertices of the unit cube S ¼fs 2 R : js j¼ 1; i ¼ 1; ... ; ng. Consider a system of equations ða x  b Þ s ¼ Ejjxjj þ d; i ¼ 1; ... ; n; ð17Þ i i i 1 for some s2S, where a is the i-th row of the matrix A. Lemma 2 (Rohn [17]). For a given nominal matrix A, let the interval family A ¼fA þ DA : jjDAjj  Egð18Þ be regular, i.e. all matrices in A are non-singular. Then the non-linear system of equations (17) has exactly one solution x 2 X for every fixed vector s2S, and Conv X ¼ Conv fx : s 2 Sg. To simplify the search for vertices x , introduce y ^ ¼ Ax  b. After change of the variables equalities (17) are converted to y ^ s ¼ðEjjA ðy ^þ bÞjj þ dÞ; i ¼ 1; ... ; n: ð19Þ i 1 Recall that s = + 1; Vi. The transformed solution set Y ¼f y ^ : jjy ^jj ^ ^ ^ EjjA ðy ^þ bÞjj þ dg is the affine image of X that is Y ¼ A X  b. Note that ^ ^ ^ Conv Y ¼ A Conv X  b. For any positive value E the intersection of Y with each orthant of R is non-empty. Following Lemma 2 each orthant contains only one vertex of Conv Y that gives the solution of the system of equations (19) while the vector s ¼ðs ; ... ; s Þ ¼ sign y ^ specifies the choice of the orthant under consideration. 1 n Taking all vectors s from S we find all vertices for Conv Y. Moreover, (19) is equivalent to one scalar equation t ¼ jðtÞ; ð20Þ where t ¼ y ^ s , y ^ ¼ t=s ¼ ts and jðtÞ¼ EjjA ðts þ bÞjj þ d. The function f(t)is i i i i i 1 defined for all t5 0 and it is a convex piecewise linear function of t. nn Lemma 3 (see [19]) For any regular interval family A 2 IR and any fixed vector s2S the scalar equation (20) has a unique solution over [0,?). The solution t* of (20) can be obtained using a simple iterative scheme, for example, Newton iterations jðt Þ t k k t ¼ t þ ; ð21Þ kþ1 k 1  j ðt Þ where we use the notation [a] = max {0,a}. Procedure (21) converges to t* for any initial t 5 0 in a finite (no more than n) iterations. Finally, we can formulate the following theorem. Theorem 1 The set Conv X has 2 vertices. Each vertex x can be found by solving the scalar equation (20) for a given vector s2S by algorithm (21). Then x ¼ A ðy ^ðt Þþ bÞ, where y ^ðtÞ¼ ts and t* is the solution of (20). s 232 S. Nazin and B. Polyak With these vertices we find the optimal lower and upper bounds for each component of x in the solution set X x ¼ minf x g; x ¼ maxf x g; i ¼ 1; ... ; n; ð22Þ s i s i i i s2S s2S and finally X ¼ð½x ; x ; ... ;½x ; x Þ . 1 n 1 n 11 1 Example 2. For A ¼ , b ¼ , and E = d = 0.25 the solution set X is a bounded 01 0:5 and non-convex polytope depicted in figure 3. Its image after the affine transformation y ^ ¼ Ax  b is shown in figure 4. All vertices of the convex hull Conv Y of the solution set with the variables y ^ are represented by the vector s with elements s ¼1 and the 1 T 2 T 3 T 4 value of t from (20): y = (2/3, 2/3) , y = ( – 1,1) , y = (1, – 1) and y = ( – 0.4, – 0.4) . By inverse transformation x ¼ A ðy þ bÞ the vertices of Conv X are obtained, and then it is trivial to find the interval bounds on X using (22). Finally X* = ([ – 1.5, 2.5], [ – 0.5, 1.5]) . 4.3. Interval over-bounding technique As already mentioned, the calculation of the optimal interval solution X* may be hard for large-dimensional problems. Hence, its simple interval over-bounding is of interest. This over-bounding is often said to be an interval solution of the interval system of equations as well. We provide below two such estimates. According to the inequality jjy ^jj  EjjA ðy ^þ bÞjj þ d for the set Y we write 1 1 1 1  1 jjA ðy ^þ bÞjj jjA y ^jj þjjx jj jjA jj jjy ^jj þjjx jj ; ð23Þ 1 1 1 1;1 1 1 Figure 3. The original solution set X. Interval Parameter Estimation under Model Uncertainty 233 Figure 4. The transformed solution set Y. –1 where x*= A b. Therefore Ejjx jj þ d jjy ^jj  g ¼ : ð24Þ 1  EjjA jj 1;1 All vectors y ^ that belong to Y thus also lie inside the ball in ?-norm of radius g. This ball is the first over-bounding interval estimate. In most cases (24) is the minimal cube centred at the origin containing Y. The main difficulty here is to –1 calculate the (?,1) norm of A ; this is again an NP-hard problem. There exist tractable upper bounds for this norm; we use the simplest one: for any given matrix G with entries g (i, j=1, ..., n) the value of jjGjj can always be approximated by ij 1;1 a 1-norm: n  n  n X X X jjGjj ¼ max jjGxjj ¼ max  g x   jg jj ¼ jjGjj : ð25Þ ij j ij 1;1 1 1 jjxjj 1 jjxjj 1 1 1 i¼1 j¼1 i;j¼1 Hence, the inequality (24) is replaced by Ejjx jj þ d jjyjj  ; ð26Þ 1  EjjA jj where E should be less than 1=jjA jj . An interval estimate for Y implies an interval estimate for X. Indeed, x is an affine function of y ^ : x ¼ x þ A y ^ and component-wise optimization for x on a cube can be performed explicitly. Then we arrive at the following result. 234 S. Nazin and B. Polyak Theorem 2 The interval vector X ¼ð½x ; x ; .. . ;½x ; x Þ with 1 n 1 n x ¼ x  gjjg jj ; x ¼ x þ gjjg jj ; i ¼ 1; ... ; n ð27Þ i i i i i 1 i 1 –1 contains the solution set X, where g is the i-th row of G = A while g is the right-hand side of (24) or (26). Thus the calculation of X X given by (26), (27) is not involved, it does not lead to any combinatorial difficulties and does not require the solution of linear programming problems. Numerous examples confirm that this over-bounding solution is close to optimal. One such example is considered in [19] for the linear system Hx = b with H being a Hilbert matrix. Hilbert matrices are poorly conditioned even for small dimensions and for this reason it is a good test example in the framework of interval uncertainty. It was demonstrated in [19] that the over-bounding estimates (26), (27) and (24), (27) coincide in this case and give a very precise approximation of the smallest interval solution. 5. Large-scale interval parameter bounding n m Assume now that x 2 R , y 2 R and m  n. The interval vector X is taken to be a prior approximation containing the parameter vector x. Let c be the i-th row of C. Below, we describe two recursive algorithms for an outer-bounding interval approximation of the intersection X \ X . In Algorithm 1, for simplicity, we assume m=Kn, where K is an integer. Algorithm 1 Let k = 1. Assume X ¼ X as an initial interval approximation. . Step 1: Consider the interval system of linear equations from (3) that corresponds to the regressors c , ..., c . Compute the non-singularity radius r for the (kn-n+1) kn k nominal matrix A of this system. If E5 r , then find its interval solution X , else k k (in particular, if A is singular) X is assumed to be infinitely large and go to step ~ ~ . Step 2: Find the smallest interval vector X containing X \ X . Put X ¼ X. . Step 3: If k = K, then terminate, else set k = k + 1 and go to step 1. The interval solution X in step 1 can be calculated as described in section 2. For large- scale systems (e.g., n4 15) it can be obtained as a simple interval over-bounding, see section 3. The interval vector X computed by Algorithm 1 contains X . The main k¼0 benefit of Algorithm 1 is its relatively low complexity. It requires the solution of K = m/n interval systems of equations. Algorithm 2 Let k = 1. Assume X = X as an initial interval approximation. . Step 1: Consider the interval system of linear equations from (3) corresponding to the regressors c , ... c . Compute the non-singularity radius r for the k k + n–1 k nominal matrix A of this system. If E5 r , then find its interval solution X , else k k go to step 3. ~ ~ . Step 2: Find the smallest interval vector X containing X \ X . Put X ¼ X. . Step 3: If k =m–n + 1, then terminate, else set k = k + 1 and go to step 1. Interval Parameter Estimation under Model Uncertainty 235 Algorithm 2 requires the solution of m–n + 1 interval systems of equations instead of m/n for Algorithm 1, but it provides a more accurate interval estimate. Example 3 Let n=2, m=40 and x = (1,1) be the parameter vector to be estimated, i.e. there are two parameters and 40 measurements in the model. The data are generated as follows. Take C be a (m6 n) -matrix with rows c , which are samples of uniformly distributed vectors on the unit sphere. Interval uncertainty is defined by E = 0.2 and d = 0.5, and then DC=2e(rand(m,n) – 0.5) and w=2d(rand(m,1) – 0.5). The measurement vector y 2 R is taken to be y=(C +DC)x + w. These measure- ments are compatible with model (3) and given parameter vector x. Our purpose is to estimate x under given C, y. Algorithm 1 considers K = m/n = 20 linear interval systems. Let the initial interval approximation be X = ([ – 5,5],[ – 5,5]) . The interval estimator is constructed as an intersection of the optimal interval solutions for the linear interval systems; see figure 5. Algorithm 1 provides X (dashed line box in figure 6) while Algorithm 2 computes a more precise interval approximation X of the non- convex feasible parameter set X as the intersection of m–n + 1 = 39 optimal interval solutions for linear interval systems (solid line box in figure 6). Notice that the decrease in size of interval approximations in both recursive algorithms slows down after an initial rapid decrease. This effect often appears in parameter estimation. 6. Conclusions In this paper we considered the parameter estimation problem for linear multi-output models under interval uncertainty. The model uncertainty involves additive measure- ment noise vector and a bounded uncertain regressor matrix. Outer-bounding interval Figure 5. Interval parameter estimator. 236 S. Nazin and B. Polyak Figure 6. Interval approximations of X. approximations of the non-convex feasible parameter set for this uncertain model are obtained. The algorithms described are based on the computation of interval solutions for square interval systems of linear equations. This approach allows computational difficulties to be avoided and provides a parameter estimator for models with a large number of measurements. Acknowledgements This work was supported in part by grant RFBR-02-01-00127. The work of S. A. Nazin was additionally supported by grant INTAS YSF 2002-181. References [1] Jaulin, L., Kieffer, M., Didrit, O. and Walter, E., 2001, Applied Interval Analysis (London: Springer). [2] Walter, E. and Piet-Lahanier, H., 1989, Exact recursive polyhedral description of the feasible parameter set for bounded-error models. IEEE Transactions on Automatic Control, AC-34, 911 – 914. [3] Walter, E. (Ed.), 1990, Special Issue on Parameter Identification with Error Bound. Mathematics and Computing in Simulation, 32. [4] Norton, J. P. (Ed.), 1994, Special Issue on Bounded-Error Estimation, 1. International Journal of Adaptive Control and Signal Processing, 8 (1). [5] Norton, J. P. (Ed.), 1995, Special Issue on Bounded-Error Estimation, 2. International Journal of Adaptive Control and Signal Processing, 9 (2). [6] Milanese, M., Norton, J., Piet-Lahanier, H. and Walter E. (Eds), 1996, Bounding Approaches to System Identification (New York: Plenum). [7] Cerone, V., 1993, Feasible parameter set for linear models with bounded errors in all variables. Automatica, 29, 1551 – 1555. Interval Parameter Estimation under Model Uncertainty 237 [8] Norton, J. P., 1999, Modal robust state estimator with deterministic specification of uncertainty. In: A. Garulli, A. Tesi, A. Vicino (Eds) Robustness in Identification and Control (London: Springer), pp. 62 – 71. [9] Chernousko, F. L. and Rokityanskii, D. Ya., 2000, Ellipsoidal bounds on reachable sets of dynamical systems with matrices subjected to uncertain perturbations. Journal of Optimization Theory and Applications, 104, 1 – 19. [10] Polyak, B. T., Nazin, S. A., Durieu, C. and Walter, E., 2004, Ellipsoidal parameter or state estimation under model uncertainty. Automatica, 40, 1171 – 1179. [11] Oettli, W. and Prager, W., 1964, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numerical Mathematics, 6, 405 – 409. [12] Kreinovich, V., Lakeev, A. V. and Noskov, S. I., 1993, Optimal solution of interval linear systems is intractable (NP-hard). Interval Computations, 1, 6 – 14. [13] Cope, J. E. and Rust, B. W., 1979, Bounds on solutions of linear systems with inaccurate data. SIAM Journal of Numerical Analysis, 16, 950 – 963. [14] Rust, B. W. and Burrus, W. R., 1972, Mathematical Programming and the Numerical Solution of Linear Equations (New York: Elsevier). [15] Neumaier, A., 1990, Interval Methods for Systems of Equations (Cambridge: Cambridge University Press). [16] Higham, N. J., 1996, Accuracy and Stability of Numerical Algorithms (Philadelphia: SIAM). [17] Rohn, J., 1989, Systems of linear interval equations. Linear Algebra and Its Applications, 126, 39 – 78. [18] Shary, S. P., 1995, On optimal solution of interval linear equations. SIAM Journal of Numerical Analysis, 32, 610 – 630. [19] Polyak, B. T. and Nazin, S. A., Interval solution for interval algebraic equations. Mathematics and Computing in Simulation, 66, 207 – 217. [20] Polyak, B. T., 2003, Robust linear algebra and robust aperiodicity. In: A. Rantzer and C. Byrnes (Eds) Directions in Mathematical System Theory and Optimization (Berlin: Springer), pp. 249 – 260. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Mathematical and Computer Modelling of Dynamical Systems Taylor & Francis

Interval parameter estimation under model uncertainty

Download PDF
13 pages

Loading next page...
 
/lp/taylor-francis/interval-parameter-estimation-under-model-uncertainty-z8kGLHK0px

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Taylor & Francis
Copyright
Copyright Taylor & Francis Group, LLC
ISSN
1744-5051
eISSN
1387-3954
DOI
10.1080/138950500069243
Publisher site
See Article on Publisher Site

Abstract

Mathematical and Computer Modelling of Dynamical Systems Vol. 11, No. 2, June 2005, 225 – 237 SERGEY A. NAZIN AND BORIS T. POLYAK* Institute of Control Services, Russian Academy of Sciences, Profsoyuznaya str. 65, 117997, Moscow, Russia This paper is devoted to the estimation of parameters of linear multi-output models with uncertain regressors and additive noise. The uncertainty is assumed to be described by intervals. Outer-bounding interval approximations of the non-convex feasible parameter set for uncertain systems are obtained. The method is based on the calculation of the interval solution for an interval system of linear algebraic equations and provides parameter estimators for models with a large number of measurements. Keywords: Interval uncertainty, interval equations, uncertain model, parameter estimation, parameter bounding 1. Introduction The set-membership estimation framework for uncertain systems has attracted much attention during the past few decades. It is an alternative to the stochastic approach where some prior information on the statistical distribution of errors is needed, because only bounds on uncertainty in system parameters and signals are required. This assumption is often much more acceptable in practice. Various types of compact sets (intervals, polytopes, ellipsoids, etc.) are usually used to characterize these bounds. They are called the membership set constraints on uncertain variables. The parameter estimation problem for uncertain dynamic systems is one of the most natural in this context. The problem is to determine bounds or set constraints on system parameters based on output measurements, the model structure and bounds on uncertain variables. In this paper we focus on the so-called interval type of uncertainty. This means that each component of an uncertain vector or matrix is assumed to belong to a known finite interval. Although the description is natural and simple [1], combinatorial difficulties may become so severe as to make estimation intractable especially in the multidimensional case. The goal of the paper is to construct an *Corresponding author. E-mail: boris@ipu.rssi.ru Mathematical and Computer Modelling of Dynamical Systems ISSN 1387-3954 print/ISSN 1744-5051 online ª 2005 Taylor & Francis Group Ltd http://www.tandf.co.uk/journals DOI: 10.1080/138950500069243 226 S. Nazin and B. Polyak effective interval parameter estimator for an uncertain multi-output static system that can be used with large sets of data. Consider a linear regression model under interval uncertainty y ¼ Cx þ w; ð1Þ n m where x 2 R is an unknown parameter vector, y 2 R denotes a vector of results of mn m measurements, C 2 R is a matrix of regressors and w 2 R is an unknown vector of measurement errors. The classical parameter bounding approach is based on the assumption that the matrix C is known precisely, while the vector w is bounded and lies in the box w 2½w; w where w and w are known. This inclusion is understood componentwise. For instance, the set of all feasible parameter vectors x compatible with a single measurement y 2 R is the strip between two hyperplanes n T S ¼ x 2 R : y  w  c x  y  w : ð2Þ i i i i i The sequence of measurements y , ..., y then provides a convex polytope S .A 1 m i i¼1 number of methods has been developed to characterize this polytope or to construct outer-bounding approximations of it (see [2,3,4,5,6]). The present paper deals with the more general problem of where the matrix of mn regressors is also uncertain, i.e. C2C, and C is an interval matrix (C 2 IR ). This situation arises in many real-life problems when we do not have complete information concerning the plant. Furthermore, weakly non-linear systems can be treated in the same manner if non-linearity is replaced by uncertainty. Particular cases of this problem have been considered in the literature [3,7,8]. Any matrix or vector is said to belong to the interval family if its elements are from some real intervals [a;b], a 4 b. mn The standard notation IR indicates the space of all interval (m6 n) -matrices and IR is the space of all n-dimensional interval vectors. The presence of matrix uncertainty in the model leads to serious difficulties due to the non-convexity of the resulting set constraints. In [9,10] ellipsoidal techniques were applied to state and parameter estimation for linear models with matrix uncertainty where non-convexity of reachable and feasible parameter sets was pointed out. The main purpose of this article is to apply an interval technique to parameter estimation. The basic tool for this is the interval solution of linear interval systems of equations. The paper is organized as follows. Section 2 states the problem in detail. The scalar- measurement case is considered in section 3. In the multi-dimensional case the idea is to split a given linear model into a number of interval systems of linear algebraic equations. A simple method for solving these systems is proposed, which easily computes an optimal interval solution for moderate-scale problems (section 4.2) whereas for large-scale problems effective interval over-bounding solutions are obtained (section 4.3). The resulting method for parameter bounding is finally described in section 5. 2. Problem statement Consider a multi-output model with measurement noise and uncertainty in the matrix of regressors y ¼ðC þ DCÞ x þ w; ð3Þ Interval Parameter Estimation under Model Uncertainty 227 n m mn m where x 2 R , y 2 R , C 2 R and w 2 R . The number of measurements is usually much larger than the dimension of the parameter vector, so m  n. Assume jjDCjj  E; jjwjj  d: ð4Þ 1 1 The infinity norms of matrices and vectors are equal to the maximal absolute value of their elements, i.e. jjDCjj ¼ max jðDCÞ j ; jjwjj ¼ max jw j: ð5Þ 1 ij 1 1im; 1jn 1im Inequality (4) describes a particular case of interval uncertainty when all components of DC or w have the same bounds. The matrix C, vector y and scalars E, d are assumed to be known. All vectors x 2 R satisfying (3) under the constraints (4) form the feasible parameter set X ¼ x 2 R : y ¼ðC þ DCÞx þ w; jjDCjj  E; jjwjj  d : ð6Þ 1 1 Assume that x2X , where X 2 IR . The initial approximation X should be taken 0 0 0 large enough to guarantee inclusion of all parameter vectors of interest. The problem is to construct a more accurate outer-bounding interval approximation for the vector x in accordance with the large number of measurements {y , ..., y } and model structure 1 m (3) – (4). In other words, we look for an interval vector X 2 IR (preferably of minimal size) containing the intersection X \ X. 3. Scalar observation The single-measurement case (m = 1) is a good particular example of the parameter estimation. Set X for the scalar model y ¼ðc þ DcÞ x þ w ð7Þ where x 2 R ; y 2 R;jjDcjj  E and jwj d can be explicitly rewritten as n T X ¼fx 2 R : jy  c xj Ejjxjj þ dg; ð8Þ where jjxjj ¼ jx j. Figure 1 depicts a typical shape of X , which is non-convex for i 1 1 i¼1 any E4 0 (the region between two solid polygonal lines). This set reduces to a strip as n k E?0. However it is convex in each orthant of R . Let E be the k-th orthant of the n k vector space, k=1, ..., 2 .If x2E for any fixed number k, the right-hand side of the inequality in (8) becomes a linear function and therefore X \ E is a convex set. Assume x2X . Then the smallest interval vector X containing X \ X can be found 0 0 1 by solving a linear programming problem in each orthant of R . Indeed, the vector k k k k s = sign x for x2E is uniquely defined with elements s such that js j¼ 1. Thus i i () k T k X \ E ¼ x 2 R : jy  c xj E x s þ d ð9Þ 1 i i¼1 is a convex set given by linear constraints. Denote by e the j-th unit coordinate vector of R , j=1, ..., n. Then the j-th lower and upper bounds on the intersection X \ X \ E are calculated by linear programming as 0 1 228 S. Nazin and B. Polyak k j j x ¼ arg min ðe ; xÞ; x ¼ arg max ðe ; xÞ; ð10Þ j j k k x2X \X \E x2X \X \E 0 1 0 1 k k k k k where (,) denotes the scalar product. Hence X ¼ð½x ; x ; ... ;½x ; x Þ gives an 1 1 n n interval vector that is the minimal box containing X \ X \ E . 0 1 Notice however that the intersection of the set X \ X with some orthants may be 0 1 empty. The calculations in these orthants can obviously be omitted as long as the linear programming problem (10) turns out to become infeasible. Further, let K ¼fk : X \ X \ E 6¼;g. Then {E :k2K} represents a family of 0 1 orthants containing X \ X . Checking all orthants E such that k2K we obtain the 0 1 inclusion X \ X X . Finally, take 0 1 k2K no no x ¼ min x ; x ¼ max x ; i ¼ 1; ... ; n: ð11Þ i i i i k2K k2K X ¼ð½x ; x ; ... ;½x ; x Þ gives the optimal interval approximation of X \ X . 1 1 n n 0 1 T T Example 1. Let X =([7 1,4],[7 0.5,5]) and y=0, c = (1,1) , E = d = 0.5. The set X ¼f x 2 R : 2jx þ x jjx jþ jx jþ 1g is shown in figure 2 (shaded region). The 1 1 2 1 2 auxiliary interval vectors X are found via linear programming according to (10) in k T each orthant E , k = 1, . . ., 4 (bold boxes). Then X=([7 1,2.5],[7 0.5,4]) . In the multi-output case, one can consider the scalar observations recursively and apply the above linear programming procedure. However this technique becomes unsuitable for models with a large number of measurements (m  n). The main idea of the present paper is to consider blocks of n measurement equations in (3) and to treat each of them as a system of linear algebraic equations under interval uncertainties. A Figure 1. Feasible parameter set (single measurement). Interval Parameter Estimation under Model Uncertainty 229 simple algorithm to obtain an interval solution for this system is described in the following section. 4. Interval system of linear algebraic equations nn Let C 2 R , i.e. the number of parameters is equal to the number of observations. Then rewrite (3) in the form ðA þ DAÞ x ¼ b þ Db ð12Þ with A = C, b = y, DA =DC and Db=– w such that jjDAjj 4E, jjDbjj 4d. ? ? The calculation of the interval solution for the interval system of equations (12) is a challenging problem in numerical analysis and robust linear algebra. This problem was first considered in the 1960s by Oettli and Prager [11]. Since then, the problem has attracted much attention and was developed in the context of the modelling of uncertain systems. nn Assume that the matrix family A ¼fA þ DA : jjDAjj  Eg2 IR is non-singular (it contains no singular matrix) and that the interval vector is b ¼fb þ Db : jjDbjj  dg2 IR . Then for any A 2 A and any b 2 b the ordinary linear system Ax = b has a unique solution. We are interested in a set X of all these solutions of the interval system: X ¼fg x 2 R : Ax ¼ b; A 2 A; b 2 b : ð13Þ Our main objective is to find an interval solution of the linear interval system (12), that is, to determine the smallest interval vector X containing all possible solutions Figure 2. Single-output interval parameter bounding. 230 S. Nazin and B. Polyak (13). In other words, we want to embed the solution set X into the minimal box in R . This problem is known to be NP-hard [12] and complicated from a computational viewpoint for large-scale systems. Paper [11] shows how multiple linear programming can be used to obtain X ; this line of research was continued in [13,14]. Iterative approaches have been established at this context as well as direct numerical methods that provide an over-bounding of X ; see the monographs [15,16] and papers [17,18]. In this section we briefly describe a simple approach proposed in [19] for interval approximation of the solution set. Instead of employing linear programming in each orthant it is suggested to deal with a scalar equation. This method is based on Rohn’s result [17] and simplifies his algorithm. In order to find the optimal interval estimate X ^ ^ of the solution set X, all vertices of its convex hull Conv X should be obtained. The search of each vertex is via the solution of a scalar equation. In the case of large-scale systems we also provide a simple and fast procedure for over-bounding of the optimal interval solution. 4.1. The solution set A detailed description of the solution set for the linear interval systems was given in the pioneering work by Oettli and Prager [11] for a general situation of interval uncertainty. In our case their result is reduced as follows. Lemma 1 (Oettli & Prager [11]) The set of all admissible solutions of the system (12) is a non-convex polytope: X ¼fx 2 R : jjAx  bjj  Ejjxjj þ dg: ð14Þ 1 1 This result also follows from (8). The set X remains bounded as long as the interval matrix A is regular. This regularity is characterized by a non-singularity radius. For the interval family A this radius is equal to rðAÞ¼ ; ð15Þ jjA jj 1;1 see [20] for details. Recall that for any matrix G its (?,1) -norm is defined as jjGjj ¼ max jjGxjj : ð16Þ 1;1 1 jjxjj 1 Note also that the calculation of this norm is NP-hard. ^ ^ While E5 r(A), A remains regular and X is bounded. If the solution set X lies in a given orthant of R , then it becomes convex, and the search for its interval approximation reduces to convex optimization. However this is no longer the case in most situations, and the problem then meets combinatorial difficulties. 4.2. Optimal interval estimates of the solution set The problem is to determine exact lower x and upper x bounds on each component x i i i of the vector x 2 R under the assumption that x 2 X. The approach is focused on Interval Parameter Estimation under Model Uncertainty 231 ^ ^ searching for vertices of the convex hull Conv X of the solution set X instead of employing linear programming in each orthant. The main base for this technique is the paper by Rohn [17], where a key result defining Conv X was proved. Let S be the set of vertices of the unit cube S ¼fs 2 R : js j¼ 1; i ¼ 1; ... ; ng. Consider a system of equations ða x  b Þ s ¼ Ejjxjj þ d; i ¼ 1; ... ; n; ð17Þ i i i 1 for some s2S, where a is the i-th row of the matrix A. Lemma 2 (Rohn [17]). For a given nominal matrix A, let the interval family A ¼fA þ DA : jjDAjj  Egð18Þ be regular, i.e. all matrices in A are non-singular. Then the non-linear system of equations (17) has exactly one solution x 2 X for every fixed vector s2S, and Conv X ¼ Conv fx : s 2 Sg. To simplify the search for vertices x , introduce y ^ ¼ Ax  b. After change of the variables equalities (17) are converted to y ^ s ¼ðEjjA ðy ^þ bÞjj þ dÞ; i ¼ 1; ... ; n: ð19Þ i 1 Recall that s = + 1; Vi. The transformed solution set Y ¼f y ^ : jjy ^jj ^ ^ ^ EjjA ðy ^þ bÞjj þ dg is the affine image of X that is Y ¼ A X  b. Note that ^ ^ ^ Conv Y ¼ A Conv X  b. For any positive value E the intersection of Y with each orthant of R is non-empty. Following Lemma 2 each orthant contains only one vertex of Conv Y that gives the solution of the system of equations (19) while the vector s ¼ðs ; ... ; s Þ ¼ sign y ^ specifies the choice of the orthant under consideration. 1 n Taking all vectors s from S we find all vertices for Conv Y. Moreover, (19) is equivalent to one scalar equation t ¼ jðtÞ; ð20Þ where t ¼ y ^ s , y ^ ¼ t=s ¼ ts and jðtÞ¼ EjjA ðts þ bÞjj þ d. The function f(t)is i i i i i 1 defined for all t5 0 and it is a convex piecewise linear function of t. nn Lemma 3 (see [19]) For any regular interval family A 2 IR and any fixed vector s2S the scalar equation (20) has a unique solution over [0,?). The solution t* of (20) can be obtained using a simple iterative scheme, for example, Newton iterations jðt Þ t k k t ¼ t þ ; ð21Þ kþ1 k 1  j ðt Þ where we use the notation [a] = max {0,a}. Procedure (21) converges to t* for any initial t 5 0 in a finite (no more than n) iterations. Finally, we can formulate the following theorem. Theorem 1 The set Conv X has 2 vertices. Each vertex x can be found by solving the scalar equation (20) for a given vector s2S by algorithm (21). Then x ¼ A ðy ^ðt Þþ bÞ, where y ^ðtÞ¼ ts and t* is the solution of (20). s 232 S. Nazin and B. Polyak With these vertices we find the optimal lower and upper bounds for each component of x in the solution set X x ¼ minf x g; x ¼ maxf x g; i ¼ 1; ... ; n; ð22Þ s i s i i i s2S s2S and finally X ¼ð½x ; x ; ... ;½x ; x Þ . 1 n 1 n 11 1 Example 2. For A ¼ , b ¼ , and E = d = 0.25 the solution set X is a bounded 01 0:5 and non-convex polytope depicted in figure 3. Its image after the affine transformation y ^ ¼ Ax  b is shown in figure 4. All vertices of the convex hull Conv Y of the solution set with the variables y ^ are represented by the vector s with elements s ¼1 and the 1 T 2 T 3 T 4 value of t from (20): y = (2/3, 2/3) , y = ( – 1,1) , y = (1, – 1) and y = ( – 0.4, – 0.4) . By inverse transformation x ¼ A ðy þ bÞ the vertices of Conv X are obtained, and then it is trivial to find the interval bounds on X using (22). Finally X* = ([ – 1.5, 2.5], [ – 0.5, 1.5]) . 4.3. Interval over-bounding technique As already mentioned, the calculation of the optimal interval solution X* may be hard for large-dimensional problems. Hence, its simple interval over-bounding is of interest. This over-bounding is often said to be an interval solution of the interval system of equations as well. We provide below two such estimates. According to the inequality jjy ^jj  EjjA ðy ^þ bÞjj þ d for the set Y we write 1 1 1 1  1 jjA ðy ^þ bÞjj jjA y ^jj þjjx jj jjA jj jjy ^jj þjjx jj ; ð23Þ 1 1 1 1;1 1 1 Figure 3. The original solution set X. Interval Parameter Estimation under Model Uncertainty 233 Figure 4. The transformed solution set Y. –1 where x*= A b. Therefore Ejjx jj þ d jjy ^jj  g ¼ : ð24Þ 1  EjjA jj 1;1 All vectors y ^ that belong to Y thus also lie inside the ball in ?-norm of radius g. This ball is the first over-bounding interval estimate. In most cases (24) is the minimal cube centred at the origin containing Y. The main difficulty here is to –1 calculate the (?,1) norm of A ; this is again an NP-hard problem. There exist tractable upper bounds for this norm; we use the simplest one: for any given matrix G with entries g (i, j=1, ..., n) the value of jjGjj can always be approximated by ij 1;1 a 1-norm: n  n  n X X X jjGjj ¼ max jjGxjj ¼ max  g x   jg jj ¼ jjGjj : ð25Þ ij j ij 1;1 1 1 jjxjj 1 jjxjj 1 1 1 i¼1 j¼1 i;j¼1 Hence, the inequality (24) is replaced by Ejjx jj þ d jjyjj  ; ð26Þ 1  EjjA jj where E should be less than 1=jjA jj . An interval estimate for Y implies an interval estimate for X. Indeed, x is an affine function of y ^ : x ¼ x þ A y ^ and component-wise optimization for x on a cube can be performed explicitly. Then we arrive at the following result. 234 S. Nazin and B. Polyak Theorem 2 The interval vector X ¼ð½x ; x ; .. . ;½x ; x Þ with 1 n 1 n x ¼ x  gjjg jj ; x ¼ x þ gjjg jj ; i ¼ 1; ... ; n ð27Þ i i i i i 1 i 1 –1 contains the solution set X, where g is the i-th row of G = A while g is the right-hand side of (24) or (26). Thus the calculation of X X given by (26), (27) is not involved, it does not lead to any combinatorial difficulties and does not require the solution of linear programming problems. Numerous examples confirm that this over-bounding solution is close to optimal. One such example is considered in [19] for the linear system Hx = b with H being a Hilbert matrix. Hilbert matrices are poorly conditioned even for small dimensions and for this reason it is a good test example in the framework of interval uncertainty. It was demonstrated in [19] that the over-bounding estimates (26), (27) and (24), (27) coincide in this case and give a very precise approximation of the smallest interval solution. 5. Large-scale interval parameter bounding n m Assume now that x 2 R , y 2 R and m  n. The interval vector X is taken to be a prior approximation containing the parameter vector x. Let c be the i-th row of C. Below, we describe two recursive algorithms for an outer-bounding interval approximation of the intersection X \ X . In Algorithm 1, for simplicity, we assume m=Kn, where K is an integer. Algorithm 1 Let k = 1. Assume X ¼ X as an initial interval approximation. . Step 1: Consider the interval system of linear equations from (3) that corresponds to the regressors c , ..., c . Compute the non-singularity radius r for the (kn-n+1) kn k nominal matrix A of this system. If E5 r , then find its interval solution X , else k k (in particular, if A is singular) X is assumed to be infinitely large and go to step ~ ~ . Step 2: Find the smallest interval vector X containing X \ X . Put X ¼ X. . Step 3: If k = K, then terminate, else set k = k + 1 and go to step 1. The interval solution X in step 1 can be calculated as described in section 2. For large- scale systems (e.g., n4 15) it can be obtained as a simple interval over-bounding, see section 3. The interval vector X computed by Algorithm 1 contains X . The main k¼0 benefit of Algorithm 1 is its relatively low complexity. It requires the solution of K = m/n interval systems of equations. Algorithm 2 Let k = 1. Assume X = X as an initial interval approximation. . Step 1: Consider the interval system of linear equations from (3) corresponding to the regressors c , ... c . Compute the non-singularity radius r for the k k + n–1 k nominal matrix A of this system. If E5 r , then find its interval solution X , else k k go to step 3. ~ ~ . Step 2: Find the smallest interval vector X containing X \ X . Put X ¼ X. . Step 3: If k =m–n + 1, then terminate, else set k = k + 1 and go to step 1. Interval Parameter Estimation under Model Uncertainty 235 Algorithm 2 requires the solution of m–n + 1 interval systems of equations instead of m/n for Algorithm 1, but it provides a more accurate interval estimate. Example 3 Let n=2, m=40 and x = (1,1) be the parameter vector to be estimated, i.e. there are two parameters and 40 measurements in the model. The data are generated as follows. Take C be a (m6 n) -matrix with rows c , which are samples of uniformly distributed vectors on the unit sphere. Interval uncertainty is defined by E = 0.2 and d = 0.5, and then DC=2e(rand(m,n) – 0.5) and w=2d(rand(m,1) – 0.5). The measurement vector y 2 R is taken to be y=(C +DC)x + w. These measure- ments are compatible with model (3) and given parameter vector x. Our purpose is to estimate x under given C, y. Algorithm 1 considers K = m/n = 20 linear interval systems. Let the initial interval approximation be X = ([ – 5,5],[ – 5,5]) . The interval estimator is constructed as an intersection of the optimal interval solutions for the linear interval systems; see figure 5. Algorithm 1 provides X (dashed line box in figure 6) while Algorithm 2 computes a more precise interval approximation X of the non- convex feasible parameter set X as the intersection of m–n + 1 = 39 optimal interval solutions for linear interval systems (solid line box in figure 6). Notice that the decrease in size of interval approximations in both recursive algorithms slows down after an initial rapid decrease. This effect often appears in parameter estimation. 6. Conclusions In this paper we considered the parameter estimation problem for linear multi-output models under interval uncertainty. The model uncertainty involves additive measure- ment noise vector and a bounded uncertain regressor matrix. Outer-bounding interval Figure 5. Interval parameter estimator. 236 S. Nazin and B. Polyak Figure 6. Interval approximations of X. approximations of the non-convex feasible parameter set for this uncertain model are obtained. The algorithms described are based on the computation of interval solutions for square interval systems of linear equations. This approach allows computational difficulties to be avoided and provides a parameter estimator for models with a large number of measurements. Acknowledgements This work was supported in part by grant RFBR-02-01-00127. The work of S. A. Nazin was additionally supported by grant INTAS YSF 2002-181. References [1] Jaulin, L., Kieffer, M., Didrit, O. and Walter, E., 2001, Applied Interval Analysis (London: Springer). [2] Walter, E. and Piet-Lahanier, H., 1989, Exact recursive polyhedral description of the feasible parameter set for bounded-error models. IEEE Transactions on Automatic Control, AC-34, 911 – 914. [3] Walter, E. (Ed.), 1990, Special Issue on Parameter Identification with Error Bound. Mathematics and Computing in Simulation, 32. [4] Norton, J. P. (Ed.), 1994, Special Issue on Bounded-Error Estimation, 1. International Journal of Adaptive Control and Signal Processing, 8 (1). [5] Norton, J. P. (Ed.), 1995, Special Issue on Bounded-Error Estimation, 2. International Journal of Adaptive Control and Signal Processing, 9 (2). [6] Milanese, M., Norton, J., Piet-Lahanier, H. and Walter E. (Eds), 1996, Bounding Approaches to System Identification (New York: Plenum). [7] Cerone, V., 1993, Feasible parameter set for linear models with bounded errors in all variables. Automatica, 29, 1551 – 1555. Interval Parameter Estimation under Model Uncertainty 237 [8] Norton, J. P., 1999, Modal robust state estimator with deterministic specification of uncertainty. In: A. Garulli, A. Tesi, A. Vicino (Eds) Robustness in Identification and Control (London: Springer), pp. 62 – 71. [9] Chernousko, F. L. and Rokityanskii, D. Ya., 2000, Ellipsoidal bounds on reachable sets of dynamical systems with matrices subjected to uncertain perturbations. Journal of Optimization Theory and Applications, 104, 1 – 19. [10] Polyak, B. T., Nazin, S. A., Durieu, C. and Walter, E., 2004, Ellipsoidal parameter or state estimation under model uncertainty. Automatica, 40, 1171 – 1179. [11] Oettli, W. and Prager, W., 1964, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numerical Mathematics, 6, 405 – 409. [12] Kreinovich, V., Lakeev, A. V. and Noskov, S. I., 1993, Optimal solution of interval linear systems is intractable (NP-hard). Interval Computations, 1, 6 – 14. [13] Cope, J. E. and Rust, B. W., 1979, Bounds on solutions of linear systems with inaccurate data. SIAM Journal of Numerical Analysis, 16, 950 – 963. [14] Rust, B. W. and Burrus, W. R., 1972, Mathematical Programming and the Numerical Solution of Linear Equations (New York: Elsevier). [15] Neumaier, A., 1990, Interval Methods for Systems of Equations (Cambridge: Cambridge University Press). [16] Higham, N. J., 1996, Accuracy and Stability of Numerical Algorithms (Philadelphia: SIAM). [17] Rohn, J., 1989, Systems of linear interval equations. Linear Algebra and Its Applications, 126, 39 – 78. [18] Shary, S. P., 1995, On optimal solution of interval linear equations. SIAM Journal of Numerical Analysis, 32, 610 – 630. [19] Polyak, B. T. and Nazin, S. A., Interval solution for interval algebraic equations. Mathematics and Computing in Simulation, 66, 207 – 217. [20] Polyak, B. T., 2003, Robust linear algebra and robust aperiodicity. In: A. Rantzer and C. Byrnes (Eds) Directions in Mathematical System Theory and Optimization (Berlin: Springer), pp. 249 – 260.

Journal

Mathematical and Computer Modelling of Dynamical Systems – Taylor & Francis

Published: Jun 1, 2005

Keywords: Interval uncertainty; interval equations; uncertain model; parameter estimation; parameter bounding

References

  • Special Issue on Parameter Identification with Error Bound
  • Special Issue on Bounded-Error Estimation, 1
  • Special Issue on Bounded-Error Estimation, 2
  • Modal robust state estimator with deterministic specification of uncertainty
  • Robust linear algebra and robust aperiodicity