Riccati Difference Equations To Non Linear Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this paper Riccati and filter difference equations are obtained as an approximate solution to a reverse-time optimal control problem defining the set-valued state estimator. In order to obtain a solution to the set-valued state estimation problem, the discrete-time system dynamics are modeled backwards in time. Also a new discrete time robust extended Kalman filter for uncertain systems with uncertainties are described in terms of sum quadratic constraints and integral quadratic constraints. The robust filter is an approximate set-valued state estimator which is robust in the sense that it can handle any uncertainties. A new approach through the re-organization of measurements is proposed to improve the efficiency of computation. A sufficient condition for the existence of a robust Kalman filter is derived.

Key Words - Time-varying system, Extended Kalman filters, robustness, Riccati Difference Equation.

AMS Subject Classification: 39A10, 39A11, 39A20.


The Kalman filter is most widely used methods for tracking and estimation due to its simplicity, optimality, tractability and robustness. However the application of the Kalman filter to non linear systems can be difficult. The most common approach is to use the extended Kalman filter which simply linearize all non linear models [14] so that the traditional linear Kalman filter can be applied [6]. The problem of state estimation which includes filtering, prediction and smoothing has been one of the key research topics of control community. The Kalman filter, which addresses the minimization of the filtering error covariance, emerged as a major tool of state estimation in 1960’s and references therein. A Kalman filter is an optimal estimator i-e it infers parameters of interest from indirect, inaccurate and uncertain observations. It is recursive so that new measurements can be processed as they arrive. The standard Kalman filtering assumes that the system model and the statistics of the noises are known exactly [2]. However, it may not be realistic in practice. When the uncertainty exists within the system parameters and/or the statistics of the noises, the performance of the standard Kalman filtering could be greatly degraded [7]. This has motivated many studies of robust filtering for systems with uncertainties [8]. The problem of robust estimation of systems with norm-bounded parameter uncertainties under the performance was first studied under the notion of guaranteed cost filtering. The problems of parameter and state estimation can be found in many fields of engineering and science. In modeling of real systems, it is not always possible to estimate all necessary system parameters only by knowledge of their physical base. In this case the parameters and states must be estimated by appropriate identification methods [3]. Many general analytical and experimental methods are suitable for identification of linear system, but in the case of nonlinear system we need to choose more sophisticated methods. The Kalman filter and its modifications are very suitable for methods of signal processing, optimization, system identification and parameter estimation [10]. The guaranteed cost filtering is concerned with the design of a filter to ensure an upper bound on the estimation error variances for all admissible parameter uncertainties. More research references on this topic can be found for uncertain continuous-time systems and uncertain discrete-time systems [1]. Necessary and sufficient condition for the existence of a robust quadratic filter is given in terms of two robust difference equations. The optimization of the filter involves searching for appropriate scaling parameters. The traditional system augmentation [6] can be applied to address the delay problem, which may result in a system of much higher dimension, especially when the delay is large. To improve the computational efficiency, we propose a new approach without resorting to system augmentation. A number of state estimation techniques are available for both linear as well as nonlinear systems, of which the Kalman filter and its variants such as the extended Kalman filter (EKF) have found wide areas of application. In spite of their ease of implementation, Kalman filters are known to diverge in some cases under the influence of nonlinearities and uncertainties [2]. In order to overcome this problem, robust versions of the Kalman filter have been derived for various clauses of uncertainty description. Among the many approaches developed for state estimation [13], the set membership state estimation approach of [9] provides a deterministic interpretation of the Kalman filter in terms of a set-valued state estimator. The set-valued state estimation problem involves finding the set of all states consistent with given output measurements for a time-varying system with norm bounded noise input. Also we extended the set membership state estimation approach in order to accommodate linear uncertain continuous systems with an integral quadratic constraint. A majority of the state estimation methods used in practical engineering problems are based on the use of discrete-time processes and measurements owing to the use of digital sensors and digital signal processing. This has motivated continued efforts in the literature directed towards developing suitable linear as well as nonlinear filters for discrete time systems.

In this paper we describe the problem formulation of the reverse-time discrete-time nonlinear uncertain system and introduce the concept of set-valued state estimation which is based on sum quadratic constraint and integral quadratic constraints in Section 2. This set-valued state estimation problem is then expressed in terms of corresponding optimal control problems which are discussed in Section 3. Section 4 and 5 provides an approximate solution to the optimal control problem which leads to the Riccati and filter difference equations that define the discrete-time robust extended Kalman filter. The feasibility and convergence are reached through algebraic Riccati equation. The sufficient condition for the uncertain systems is also derived through algebraic and filter difference equations. We provide the simulation results in Section 6 and Section 7 concludes the paper.

2 Problem Formulation

We consider a reverse-time discrete-time uncertain nonlinear system which is derived from a forward-time uncertain nonlinear system. The uncertainties in the discrete-time non linear system are described by a sum quadratic constraint, which is derived from the corresponding continuous-time uncertainty description in the form of an integral quadratic constraint. Furthermore, the concept of set-valued state estimation is introduced in the form of difference equation which is related to a corresponding optimal control problem.

2.1 Reverse-Time Discrete-Time Uncertain Nonlinear System:

We begin with a forward-time continuous-time uncertain nonlinear system of the form


where is the state estimation, is the known control input, and are the process and measurement uncertainty inputs respectively. Also is the uncertainty output and y is the measured output. Now consider the nonlinear functions and is a matrix function. The uncertainty associated with system (1) can be described in terms of an integral quadratic constraint as defined as,

Where denotes the Euclidean norm. is the initial state value and is the nominal initial state value. Now we have to find a difference between initial state and the nominal initial state. This finite difference is allowed by a non-zero value of the output uncertainty or the constant. If and , then . Also, (.) and (.) represent admissible uncertainties described by,


where is a nonlinear time-varying dynamic uncertainty function and represents the function for all instants of time . Also we can noted that and depend on in (3) indicates that they are allowed to depend dynamically on the system state. Also, N = NT > 0 is a matrix, is a state vector, is a given constant and are given positive-definite, symmetric matrix functions of time. In order to derive a discrete-time robust set-valued state estimator, it is necessary to obtain this continuous-time uncertain system. However, as mentioned in the introduction, the discrete-time set-valued state estimator is most straightforward to derive if this system is discretized in reverse-time rather than in forward-time. This will lead to a nonlinear reverse- time discrete-time uncertain system described by the state equations as,


Where and represent discrete-time nonlinear functions and is a given time-varying matrix. The uncertainty associated with the reverse-time discrete-time system (4) can be obtained by,


and the admissible uncertainties and are described as


and is a nonlinear time-varying dynamic uncertainty function. The uncertain system (4), with the corresponding sum quadratic constraint uncertainty description (5) is used to derive the robust filter and Riccati equations, which define the discrete-time robust Extended Kalman Filter.

3. Optimal Control Problem

Very recently, the control problem in [6] for a class of systems with both stochastic modeling uncertainty and deterministic modeling uncertainty is investigated, where the stochastic uncertainty has been expressed as a multiplicative noise. It should be pointed out that, compared to the control case, the corresponding robust filtering problem for systems with stochastic and deterministic uncertainties has gained much less attention. This situation motivates our present investigation that to carry in a dynamic modeling. As per the dynamic modeling consider to be a fixed measured output and a known control input for the uncertain system (4), (5), for . The set-valued state estimation problem involves finding the set of all possible states at time step T for the system in (4) with initial conditions and uncertainty constraints defined in (5) which is consistent with the measured output sequence and input sequence, then the output sequence, follows from the definition of,


if and only if there exists an uncertain input sequence such that, also the cost functional is derived from the Sum Quadratic Constant (5) as [9]



Here the vector is the solution to the reverse-time discrete- time system (4), with input uncertainty and terminal condition . Hence

The optimization problem


for the system (4), defines a nonlinear optimal control problem with a sign indefinite quadratic cost function. The discrete-time robust Extended Kalman Filter is derived by finding an approximate solution to this optimal control problem.


The corresponding discrete-time equation for this optimal control problem is given by,


with the initial condition

This is the point at which the linearization is performed corresponds to the current estimate as in the case of the standard Extended Kalman Filter. Now substituting the linearized terms to the above equation, an approximate solution to this nonlinear difference equation is obtained as follows,



Comparing the left hand side terms with the right hand side of the above equations, the following recursive equations are obtained.

Riccati Difference Equation


Where .

This solution of the Riccati equation in a time invariant system converges to steady state (finite) covariance which is completely observable. Also we can get the filter state difference equation.

Filter Difference Equation



The Kalman filter is applied to a linearized version of these equations without loss of optimality. The estimate is refined by re-evaluating the filter around the new estimated state operating point. This refinement procedure is iterated until little extra improvement is obtained which is called an iterated EKF.

5. Feasibility and convergence analysis of robust Filter

The feasibility and convergence properties of the solutions of the RDE (Riccati Difference Equation) is associated with ARE (Algebraic Riccati Equation). The difference from the continuous time case and the discrete time case, the non-existence of the robust Fillter over fnite horizon is no longer necessarily associated with the solution of the RDE and it’s becoming an unbounded solution. Hence the existence of the filter requires the fulfillment at each step of a suitable matrix inequality (feasibility condition). In such a case, we are introducing the sum quadratic constraint and integral quadratic constraint for finding the conditions relating to the initial state of uncertainty and the parameter, under which we can ensure feasibility of the solutions of RDEs over an arbitrarily long time interval, and convergence towards the steady state robust Kalman filter in the form of Algebraic Riccati Equation [15].

Feasible solution of a Kalman Filter

A real positive definite solution of of RDE is termed a feasible solution of RDE (Riccati Difference Equation) that if it satisfies the condition at each step. It can be shown using monotonicity results on the algebraic Riccati equation that if a system is quadratically stable, then there exists an such that for any, there exists a stabilizing solution to Algebraic Riccati Equation which leads to a convex optimization solution .

The feasibility and convergence analysis to be studied can be stated as follows: Given an arbitrarily large N, suitable conditions on the initial state such that the solutions and feasible solutions at every step and and converge, respectively to the stabilizing

solutions and as .

We shall now introduce two Lyapunov equations which is to lead a sufficient condition for existing feasibility and convergence of the solution of algebraic difference equation. The first one is,





The definition of is, where and the nonzero eigen values of (the non zero eigenvalues of ) are the positive and negative eigenvalues of M.

The second Lyapunov equation is,


where ,




where is the solution of Lyapunov equations (15) and (16). Mi and are known real matrices as defined in (15) and (16) in such case, are positive semi definite. This is a sufficient condition for ensuring feasibility and convergence of the solutions of RDE over . The solutions of RDE and of RDE (Riccati Difference Equation) are feasible over , and converge to the stabilizing solutions and respectively. As for a sufficiently small scalar , the positive initial state satisfies


where is defined as in (17).

Convergence and feasible solutions of a challenging optimal control problem

Now consider a Riccati filter difference equation for a given, the convergence and feasibility of and depend on the initial state covariance bound and parameter . Because is usually given a priori, it is necessary to study the following problem: Given > 0 and an obtained optimal which minimizes , is it possible to drive and from > 0 to and by means of a suitable time-varying function ?

In order to solve this problem, we shall apply a strategy which varies according to a piecewise-constant pattern. We shall propose a methodology to find a sequence

and a set of switching times such that the solution and with


are feasible and converge to and respectively, and the minimum trace is then obtained. In view of the above sufficient condition, we present the following algorithm for determining -switching strategy.

Step 1: Given a priori initial state and let . If , then stop.

Step 2: Let initial state be and , then find an which satisfies (18) and minimizes | âˆ' |. Then the stable solutions (and (of ARE (Algebraic Riccati Equation) are obtained.

Step 3: Let , and , also iteratively compute and of RDE (Riccati difference equation) until they almost approach to stable solutions and , respectively. We denote Pk() and Sk() at this instant as k() and k(), respectively.

Step 4: If , then stop. Otherwise, go to Step 5.

Step 5: Let k() and k() be new initial states and , respectively and let, then go to Step 2.

The concepts behind the switching strategy can be are as follows. If the initial covariance is sufficiently small and satisfies (18), the optimal value with minimum trace () can be computed directly then the convergence and feasibility conditions are also satisfied over On the other hand, if the initial covariance is very large, we cannot approach immediately. So we must select a suitable which satisfies (18) such that feasibility and convergence are guaranteed with this. Then could approach to through a finite number of steps occurring at suitable instants. The selection of such instants and the changes in must satisfy (18) and the -switching algorithm at any time. This leads to the convergence and the feasibility condition of the uncertain systems.


When all necessary input fields are known and identification problem is feasible, then we can proceed through Matlab identification tool [4,7] . If the script reads all fields from input GUI then the non linear identification tool will automatically generates the functions for problem solving. Then the user defines inputs, real states, known constant parameters and unknown parameters to be estimated [12]. Initial values have to be set for all states and unknown parameters. The additional inputs are the weight matrices Q and R represents, which states have been measured and are included in the input data for identification (Fig 1).

Fig 1. Non linear Identification model tool

User defines text characters representing inputs

, states and values of known parameters are identified (Fig. 2) [5,11].

Fig 2 Input and State values

Unknown parameters of Kalman gain which will be estimated into field estimate parameters (Fig. 3) i-e converted to known parameters.

Fig 3 Initialization of unknown parameter

Input data can be read form the weighted matrix Q and R (Fig 4). State inputs are converted the unknown uncertainties in to known certainties. This leads the efficient computation.

Fig 4 Measured data from plant and weight matrices

7 Conclusion

In this paper an algebraic and Riccati difference equations are derived as an approximate set-valued state estimator solution, obtained from a corresponding optimal control problem. We have analyzed the feasibility and convergence properties of such robust filters through sum quadratic constraints and integral quadratic constraints. A robust Extended Kalman Filter has been designed in this for the uncertain systems with a state estimation. We have reached the sufficient condition for robust Kalman filtering problem for uncertain systems with algebraic and Riccati difference equations.