An alternative approach to non-linear filtering : jump process observations†

The following non-linear filtering problem is discussed. Consider a process $ determined by the stochastic differential equation $, with the observation process $ given by $, where W is an ?^m-valued Wiener process. Two cases are dealt with. In Case 1 : $, is an Revalued martingale, where $ is a given function. In Case 2: $, where ν is a Poisson random measure on $, and $ is a given function. An observer is required of the form: $, in Case 1, and $ in Case 2, where $. In both cases the ‘ gain matrix ’ G has yet to be determined. Let D be the unit cube in ?^2m+p , and let τ _i be the first time that $ given that (Z_t is the state of the observer; i=1 corresponds to Case 1 and i = 2 corresponds to Case 2). The approach adopted here is to choose a matrix $, of a bang-bang type, in such a manner that the expected value of $ is maximized on a class of admissible gain matrices. Here $ is the Lebesgue measure on the real line and ε>0 is given. For each i = 1, 2, sufficient conditions on the maximizing gain matrix are derived. These conditions can be applied off-line and can be used in the design of the observers. Several examples are solved numerically.     

On input-output linearization of discrete-time nonlinear systems

We consider a nonlinear discrete-time system of the form Σ: x(t+1)=f(x(t), u(t)), y(t) =h(x(t)), where x ε R^N, u ε R^m, y ε R^q and f and h are analytic. Necessary and sufficient conditions for local input-output linearizability are given. We show that these conditions are also sufficient for a formal solution to the global input-output linearization problem. Finally, we show that zeros at infinity of ε can be obtained by the structure algorithm for locally input-output linearizable systems.     

An efficient processing of a chain join with the minimum communication cost in distributed database systems

This paper investigates the optimization problem when executing a join in a distributed database environment. The minimization of the communication cost for sending data through links has been adopted as an optimization criterion. We explore in this paper the approach of judiciously using join operations as reducers in distributed query processing. In general, this problem is computationally intractable. A restriction of the execution of a join in a pre-defined combinatorial order leads to a possible solution in polynomial time. An algorithm for a chain query computation has been proposed in [21]. The time complexity of the algorithm isO(m ² n ²+m ³ n), wheren is the number of sites in the network, andm is the number of relations (fragments) involved in the join. In this paper, we firstly present a proof of the intuitively well understood fact—that the eigenorder of a chain join will be the best pre-defined combinatorial order to implement the algorithm in [21]. Secondly, we show a sufficient and necessary condition for a chain query with the eigenordering to be a simple query. For the process of the class of simple queries, we show a significant reduction of the time complexity fromO(m ² n ²+m ³ n) toO(mn+m ²). It is encouraging that, in practice, the most frequent queries belong to the category of simple queries. Editor: Peter Apers     

H∞ control and filtering with initial uncertainty for infinite dimensional systems

The H_∞-control problem with a non-zero initial condition for infinite dimensional systems is considered The initial conditions are assumed to be in some subspace. First the H_∞ problem with full information is considered and necessary and sufficient conditions for the norm of an input-output operator to be less than a given number are obtained, The characterization of all admissible controllers is also given. This result is then used to solve the general H^∞ control problem and the filtering problem with initial uncertainty. The filtering problem on finite horizon involves the estimate of the state at final time. The set of all suboptimal filters is given both on finite and infinite horizons.     

Achievable H performance in sampled-data smoothing: beyond the -barrier

The lifting technique is a powerful tool for handling the periodically time-varying nature of sampled-data systems. Yet all known solutions of sampled-data H^∞ problems are limited to the case when the feedthrough part of the lifted system, , satisfies , where γ is the required H^∞ performance level. While this condition is always necessary in feedback control, it might be restrictive in signal processing applications, where some amount of delay or latency between measurement and estimation can be tolerated. In this paper, the sampled-data H^∞ fixed-lag smoothing problem with a smoothing lag of one sampling period is studied. The problem corresponds to the a-posteriori filtering problem in the lifted domain and is probably the simplest problem for which a smaller than performance level is achievable. The necessary and sufficient solvability conditions derived in the paper are compatible with those for the sampled-data filtering problem. This result extends the scope of applicability of the lifting technique and paves the way to the application of sampled-data methods in digital signal processing.     

CONTROL LAW FOR QUADRATIC STABILIZATION OF PERTURBED FUZZY TIME‐DELAY LARGE‐SCALE SYSTEMS VIA LMI

In this paper, the perturbed continuous‐time large‐scale system with time delays is represented by an equivalent Takagi‐Sugeno type fuzzy model. First, two types of decentralized state feedback controllers are considered in this paper. Based on the Riccati‐type inequality, the Razumikhin theorem, and the delay‐dependent Lyapunov functional approach, some controller design approaches are proposed to stabilize the whole fuzzy time‐delay system asymptotically. In these design methods, both the delay‐independent and delay‐dependent stabilization criteria are derived. By Schur complement, these sufficient conditions can be easily transformed into the problem of LMI's. Moreover, the systems with all the time‐delays τ^l_ij (t) are the same for all rules (i.e., τ^l_ij (t) = τ^m_ij (t) = τ_ij for all l =m); the authors also propose a simpler and less conservative stabilizing criteria. A numerical example is given to illustrate the control design and its effectiveness.     

Using massively parallel computations for absolutely precise solution of the linear programming problems

Consideration was given to the approaches to solve the linear programming problems with an absolute precision attained through rational computation without roundoff in the algorithms of the simplex method. Realization of the modified simplex method with the use of the inverse matrix was shown to have the least spatial complexity. The main memory area sufficient to solve the linear programming problem with the use of rational computations without roundoff is at most 4lm ⁴ + O(lm ³), where m is the minimal problem size and l is the number of bits sufficient to represent one element of the source data matrix. The efficiency of parallelization, that is, the ratio of acceleration to the number of processors, was shown to be asymptotically close to 100%. Computing experiments on practical problems with the sparse matrix corroborated high efficiency of parallelization and demonstrated the advantage of the parallel method of inverse matrix.     

Feedback transformations on tori

Here we investigate the problem of transforming a nonlinear system on the torusT ⁿ by using global feedback and global changes of coordinates into an invariant system (i.e., a control system of whichf andg _i are (left and right) invariant vector fields whenT ² is considered as a Lie group). We provide a complete answer whenn=2 and give a sufficient condition and necessary conditions in the more general case.     

Linear control with incomplete state feedback and known initial-state statistics†

A method is proposed for the design of a linear, time-invariant state feedback control for a linear, time-invariant, finite-dimensional system with infinite duration of control (regulator problem), which makes use of only those state variables which are available for measurement, providing that these are sufficient to render the system stable. The expected value vector and the covariance matrix for the initial state are presumed to be known.

The cost function is quadratic and is expressed in terms of the initial state statistics and the cost-weighting matrix. The necessary conditions are derived for the minimization of the expected value of the cost. The minimization results in a set of m simultaneous polynomial equations in m unknowns where m is the product of the number of the available state variables and the number of control signals formed out of these. The theory is illustrated by a simple example of a third-order system.     

Exact model-matching control of three-dimensional systems using state and output feedback

For a general state space model of three-dimensional (3-D) systems, the exact model-matching control problem via state and output feedback ia considered. A frequency domain approach is employed in which the 3-D prototype system (model) is given in transfer function matrix of the form G _m(p, w, z). The approach is based on equating the closed-loop transfer matrix function G _c(p, w, z) to G _m(p, w, z) and solving for the required feedback matrix gains through an application of Kronecker matrix product concept. We start with the static feedback case, and then treat the dynamic feedback problem for the important case of proportional plus integral plus derivative (PID) control. The approach leads to a set of linear algebraic equations, which involve the necessary and sufficient conditions for the exact model matching problem to have a solution. Two simple, but non-trivial examples, are computed.     

Exact determination of a Lyapunov function and the asymptotic stability domain

The problem of the necessary and sufficient conditions for an exact direct determination of both a Lyapunov function υ and the asymptotic stability domain D of the zero state is solved for time-invariant non-linear continuous-time systems with continuous unique motions. The conditions provide a complete algorithm for their simultaneous determination. They permit arbitrary selection of a positive definite function p for which D ⁺υ = ?p has a solution υ in order to generate a system Lyapunov function υ from D ⁺υ = ?p as for linear time-invariant systems. This expresses their substantial difference from Lyapunov's original results and their developments so far. The latter are expressed in terms of the existence of a system Lyapunov function but the former are not. The theorems of the paper establish a new insight into, and a methodology for, a study of Lyapunov stability properties and other qualitative features of nonlinear dynamic systems. Simple examples illustrate the theorems and the procedure for their application.     

Sufficient conditions for deceptive and easy binary functions

This paper finds sufficient conditions for fully or partially deceptive binary functions by calculating schema average fitness values. Deception conditions are first derived for functions of unitation (functions that depend only on the number of 1s in the string) and then extended for any binary function. The analysis is also extended to find a set of sufficient conditions for fully easy binary functions. It is found that the computational effort required to investigate full or partial deception in a problem of sizel using these sufficient conditions isO(2 ^l ) and using all necessary conditions of deception isO(4 ^l ). This calculation suggests that these sufficient conditions can be used to quickly test deception in a function. Furthermore, it is found that these conditions may also be systematically used to design a fully deceptive function by performing onlyO(l ²) comparisons and to design a partially deceptive function to orderk by performing onlyO(kl) comparisons. The analysis shows that in the class of functions of unitation satisfying these conditions of deception, an order-k partially deceptive function is also partially deceptive to any lower order. Finally, these sufficient conditions are used to investigate deception in a number of currently-used deceptive problems.     

On the group of automorphisms of strongly connected automata

LetA = (S, I, M) be a strongly connected finite automaton withn states. Weeg has shown that ifA has a group of automorphisms of orderm, then there is a partition of the setS inton/m blocks each withm states. Furthermore ifs _i ands _j are in the same block of, thenT _ii =T _jj , whereT _ii = {x|x ^* and thenM(s _i , x) =s _i }. It will be shown that the partition also must have the substitution property and that these two conditions are sufficient for ann state strongly connected automaton to have a group of automorphisms of orderm.Necessary and sufficient conditions for twon-state strongly connected automata to have isomorphic automorphism groups are given. Also, it is demonstrated that forT _ii to equalT _jj it is necessary to check only a finite number of tapes and consequently provide an algorithm for determining whether or notA has a group of automorphisms of orderm. This research was partially supported by the National Science Foundation under Grant No. G.P. 7077.     

Multivariable interpolation by weighted arithmetic means at arbitrary points

A method is considered for constructing weighted arithmetic means from IR ^m to IR, which possess the interpolation property. Necessary and sufficient conditions are then given in order to solve the convergence problem to a continuous real functionf(ξ), ξ∈IR ^m of such interpolating mean functions. Finally a few formulas are considered as an application of the proposed method. This work has been supported by the Italian Ministry of Scientific and Technological Research (M.U.R.S.T.) and the National Research Council (C.N.R.).     

QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

-Admissible control elements for diagonal semigroups on -spaces

For linear systems described by , where A is a diagonal operator on the state space l^r for some 1r<∞ and bl^r, we develop necessary and sufficient conditions for b to be p-admissible. This extends results by Ho, Russell and Weiss to the case r≠2.     

Flow regularity and optimality conditions with controls inL p

In this paper we study theC ^p regularity of the flow of a nonlinear nonautonomous control system with respect to control maps belonging toL ^p withp≥r. The results obtained are applied to get first- and second-order optimality conditions when the control space isL ^p . The problem which we consider is in the Mayer form and includes endpoint constraints. We present first-order necessary conditions for a wide class of control systems. Moreover, we show that the usual second-order sufficient conditions are effective only if the mapf that defines the control system is a polynomial of degree two in the control variable and the controls belong toL ².     

Factorization of m-D polynomials in linear m-D factors

This paper presents a solution to the factorization problem of high-order m-D polynomials into special m-D factors that are linear in all variables. By special it is meant that the factors have the form of a sum of one independent variable, say z ₁, and a general first-order polynomial not involving z ₁, i.e. z ₁ + a _j2 z ₂ + [tdot] + a _jm z _m (j = 1, 2,[tdot],N ₁). Two theorems providing the necessary and sufficient conditions for this factorization are given, which have an algorithmic form and are thus appropriate for direct computer use. The results are illustrated by means of three examples.     

Robust stabilization for multivariable systems with constrained control: Frequency domain approach

In this paper, robust stabilization conditions based on theH ^∞-norm are derived for multivariable feedback systems under perturbations and constrained control. The parametrized controller of Youlaet al. is employed to treat this problem. In addition, a necessary and sufficient condition is derived for the solvability of the synthesis problem for a controller which achieves robust stability. Finally, a design procedure is proposed for selecting the parameters of the robust controller, and an illustrative example is given.