Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Efficient Solution of A, x ( k )?= b ( k ) Using A ?1

In this work, we consider the problem of solving , , where b ^(k+1) = f(x ^(k)). We show that when A is a full matrix and , where depends on the specific software and hardware setup, it is faster to solve for by explicitly evaluating the inverse matrix A ⁻¹ rather than through the LU decomposition of A. We also show that the forward error is comparable in both methods, regardless of the condition number of A.     

Efficient temporal counting with bounded error

This paper studies aggregate search in transaction time databases. Specifically, each object in such a database can be modeled as a horizontal segment, whose y-projection is its search key, and its x-projection represents the period when the key was valid in history. Given a query timestamp q _t and a key range , a count-query retrieves the number of objects that are alive at q _t , and their keys fall in . We provide a method that accurately answers such queries, with error less than , where N _alive(q _t ) is the number of objects alive at time q _t , and ɛ is any constant in (0, 1]. Denoting the disk page size as B, and n =  N / B, our technique requires O(n) space, processes any query in O(log _B n) time, and supports each update in O(log _B n) amortized I/Os. As demonstrated by extensive experiments, the proposed solutions guarantee query results with extremely high precision (median relative error below 5%), while consuming only a fraction of the space occupied by the existing approaches that promise precise results.     

The structured controllability radius of linear delay systems

In this article, we shall deal with the problem of calculation of the controllability radius of a delay dynamical systems of the form x′(t)?=?A ₀ x(t)?+?A ₁ x(t???h ₁)?+?···?+?A _k x(t???h _k )?+?Bu(t). By using multi-valued linear operators, we are able to derive computable formulas for the controllability radius of a controllable delay system in the case where the system's coefficient matrices are subjected to structured perturbations. Some examples are provided to illustrate the obtained results.     

Enclosing Solutions of Singular Interval Systems Iteratively

Richardson splitting applied to a consistent system of linear equations Cx = b with a singular matrix C yields to an iterative method x^k+1 = Ax^k + b where A has the eigenvalue one. It is known that each sequence of iterates is convergent to a vector x^* = x^* (x⁰) if and only if A is semi-convergent. In order to enclose such vectors we consider the corresponding interval iteration with (|[A]|) = 1 where |[A]| denotes the absolute value of the interval matrix [A]. If |[A]| is irreducible we derive a necessary and sufficient criterion for the existence of a limit of each sequence of interval iterates. We describe the shape of and give a connection between the convergence of ( ) and the convergence of the powers of [A].Dedicated to Professor G. Mae on the occasion of his 65^th birthday     

Processing fuzzy set membership functionals as vectors

A framework is presented for processing fuzzy sets for which the universe of discourse X = {x} is a separable Hilbert Space, which, in particular, may be a Euclidian Space. In a given application, X would constitute a feature space. The membership functions of sets in such X are then “membership functionals”, that is, mappings from a vector space to the real line. This paper considers the class Φ of fuzzy sets A, the membership functionals μ _A of which belong to a Reproducing Kernel Hilbert Space (RKHS) F(X) of bounded analytic functionals on X, and satisfy the constraint . These functionals can be expanded in abstract power series in x, commonly known as Volterra functional series in x. Because of the one-to-one relationship between the fuzzy sets A and their respective μ _A , one can process the sets A as objects using their μ _A as intermediaries. Thus the structure of the uncertainty present in the fuzzy sets can be processed in a vector space without descending to the level of processing of vectors in the feature space as usually done in the literature in the field. Also, the framework allows one to integrate human and machine judgments in the definition of fuzzy sets; and to use concepts analogous to probabilistic concepts in assigning membership values to combinations of fuzzy sets. Some analytical and interpretive consequences of this approach are presented and discussed. A result of particular interest is the best approximation of a membership functional μ _A in F(X) based on interpolation on a training set {(v ⁱ , u ⁱ ),i = 1, . . . , q} and under the positivity constraint. The optimal analytical solution comes out in the form of an Optimal Interpolative Neural Network (OINN) proposed by the author in 1990 for best approximation of pattern classification systems in a F(X) space setting. An example is briefly described of an application of this approach to the diagnosis of Alzheimer’s disease.     

Implementation of an Algorithm for Finding Analyticity Conditions for a Solution of a Difference Equation

A linear difference operator L with polynomial coefficients and a function F(x) satisfying the equation LF(x) = 0 are considered. The function is assumed to be analytic in the interval (–, d), where > 0. In the paper, an implementation of an algorithm suggested by S.A. Abramov and M. van Hoeij for finding conditions that guarantee analyticity of F(x) on the entire real axis is presented. The analyticity conditions are linear relations for values of F(x) and its derivatives at a given point belonging to the half-interval [0, d). A procedure for computing values of F(x) and its derivatives up to a prescribed order at a given point x ₀ is also implemented. Examples illustrating the program operation are presented.     

Rational Interpolation from Stochastic Data: A New Froissart's Phenomenon

The analytic structure of Rational Interpolants (R.I.) f (z) built from randomly perturbed data is explored; the interpolation nodes x _j , j = 1,...,M, are real points where the function f reaches these prescribed data . It is assumed that the data are randomly perturbed values of a rational function _(n) ^(m) (m / n is the degree of the numerator/denominator). Much attention is paid to the R.I. familyf _(n+1) ^(m–1), in the small stochasticity régime. The main result is that the additional zero and pole are located nearby the root of the same random polynomial, called the Froissart Polynomial (F.P.). With gaussian hypothesis on the noise, the random real root of F.P. is distributed according to a Cauchy-Lorentz law, with parameters such that the integrated probability over the interpolation interval x ₁, x _M is always larger than 1/2; in two cases studied in detail, it reaches 2/3 in one case and almost 3/4 in the other. For the families f _(n+k) ^(m+k), numerical explorations point to similar phenomena; inspection shows that, in the mean, the localization occurs in the complex and/or real vicinity of the interpolation interval.     

Global optimization methods for engineering applications: A review

A review of the methods for global optimization reveals that most methods have been developed for unconstrained problems. They need to be extended to general constrained problems because most of the engineering applications have constraints. Some of the methods can be easily extended while others need further work. It is also possible to transform a constrained problem to an unconstrained one by using penalty or augmented Lagrangian methods and solve the problem that way. Some of the global optimization methods find all the local minimum points while others find only a few of them. In any case, all the methods require a very large number of calculations. Therefore, the computational effort to obtain a global solution is generally substantial. The methods for global optimization can be divided into two broad categories: deterministic and stochastic. Some deterministic methods are based on certain assumptions on the cost function that are not easy to check. These methods are not very useful since they are not applicable to general problems. Other deterministic methods are based on certain heuristics which may not lead to the true global solution. Several stochastic methods have been developed as some variation of the pure random search. Some methods are useful for only discrete optimization problems while others can be used for both discrete and continuous problems. Main characteristics of each method are identified and discussed. The selection of a method for a particular application depends on several attributes, such as types of design variables, whether or not all local minima are desired, and availability of gradients of all the functions.Notation Number of equality constraints - () ^T A transpose of a vector - A A hypercubic cell in clustering methods - Distance between two adjacent mesh points - Probability that a uniform sample of sizeN contains at least one point in a subsetA ofS - A(v, x) Aspiration level function - A The set of points with cost function values less thanf(x _G ^* ) +. Same asA _f () - A _f () A set of points at which the cost function value is within off(x _G ^* ) - A () A set of points x with[f(x)] smaller than - A _N The set ofN random points - A _q The set of sample points with the cost function value f _q - _Q The contraction coefficient; –1 _Q 0 - _R The expansion coefficient; _E > 1 - _R The reflection coefficient; 0 < _R 1 - A _x () A set of points that are within the distance from x _G ^* - D Diagonal form of the Hessian matrix - det() Determinant of a matrix - d _j A monotonic function of the number of failed local minimizations - d _t Infinitesimal change in time - d _x Infinitesimal change in design - A small positive constant - (t) A real function called the noise coefficient - ₀ Initial value for(t) - exp() The exponential function - f ^(c) The record; smallest cost function value over X^(C) - [f(x)] Functional for calculating the volume fraction of a subset - Second-order approximation tof(x) - f(x) The cost function - An estimate of the upper bound of global minimum - f ^E The cost function value at x^E - f ^L The cost function value at x^L - f _opt The current best minimum function value - f ^P The cost function value at x ^P - f ^Q The cost function value at x ^Q - f _q A function value used to reduce the random sample - f ^R The cost function value at x ^R - f ^S The cost function value at x^S - f _{T F min} A common minimum cost function value for several trajectories - f _{TF opt} The best current minimum value found so far forf _{TF min} - f ^W The cost function value at x ^W - G Minimum number of points in a cell (A) to be considered full - The gamma function - A factor used to scale the global optimum cost in the zooming method - Minimum distance assumed to exist between two local minimum points - gi(x) Constraints of the optimization problem - H The size of the tabu list - H(x^*) The Hessian matrix of the cost function at x^* - h _j Half side length of a hypercube - h _m Minimum half side lengths of hypercubes in one row - I The unity matrix - ILIM A limit on the number of trials before the temperature is reduced - J The set of active constraints - K Estimate of total number of local minima - k Iteration counter - The number of times a clustering algorithm is executed - L Lipschitz constant, defined in Section 2 - L The number of local searches performed - _i The corresponding pole strengths - log () The natural logarithm - LS Local search procedure - M Number of local minimum points found inL searches - m Total number of constraints - m(t) Mass of a particle as a function of time - m() TheLebesgue measure of thea set - Average cost value for a number of random sample of points inS - N The number of sample points taken from a uniform random distribution - n Number of design variables - n(t) Nonconservative resistance forces - n _c Number of cells;S is divided inton _c cells - NT Number of trajectories - Pi (3.1415926) - P _i ^(j) Hypersphere approximating thej-th cluster at stagei - p(x ⁽ⁱ⁾⁾ Boltzmann-Gibbs distribution; the probability of finding the system in a particular configuration - pg A parameter corresponding to each reduced sample point, defined in (36) - Q An orthogonal matrix used to diagonalize the Hessian matrix - _i (i = 1, K) The relative size of thei-th region of attraction - r _i ^(j) Radius of thej-th hypersp here at stagei - R _x ^* Region of attraction of a local minimum x^* - r _j Radius of a hypersphere - r A critical distance; determines whether a point is linked to a cluster - R ⁿ A set ofn tuples of real numbers - A hyper rectangle set used to approximateS - S The constraint set - A user supplied parameter used to determiner - s The number of failed local minimizations - T The tabu list - t Time - T(x) The tunneling function - T _c (x) The constrained tunneling function - T _i The temperature of a system at a configurationi - TLIMIT A lower limit for the temperature - TR A factor between 0 and 1 used to reduce the temperature - u(x) A unimodal function - V(x) The set of all feasible moves at the current design - v(x) An oscillating small perturbation. - V(y⁽ⁱ⁾) Voronoi cell of the code point y⁽ⁱ⁾ - v^–1 An inverse move - v _k A move; the change from previous to current designs - w(t) Ann-dimensional standard. Wiener process - x Design variable vector of dimensionn - x^# A movable pole used in the tunneling method - x⁽⁰⁾ A starting point for a local search procedure - X^(c) A sequence of feasible points {x⁽¹⁾, x⁽²⁾,,x^(c)} - x(t) Design vector as a function of time - X^* The set of all local minimum points - x^* A local minimum point forf(x) - x^*(i) Poles used in the tunneling method - x _G ^* A global minimum point forf(x) - Transformed design space - The velocity vector of the particle as a function of time - Acceleration vector of the particle as a function of time - x ^C Centroid of the simplex excluding x ^L - x ^c A pole point used in the tunneling method - x ^E An expansion point of x ^R along the direction x ^C x ^R - x ^L The best point of a simplex - x ^P A new trial point - x ^Q A contraction point - x ^R A reflection point; reflection of x ^W on x ^C - x ^S The second worst point of a simplex - x ^W The worst point of a simplex - The reduced sample point with the smallest function value of a full cell - Y The set of code points - y ⁽ⁱ⁾ A code point; a point that represents all the points of thei-th cell - z A random number uniformly distributed in (0,1) - Z ^(c) The set of points x where [f ^(c) – ] is smaller thanf(x) - []₊ Max (0,) - | | Absolute value - The Euclidean norm - f[x(t)] The gradient of the cost function     

Alternating time versus deterministic time: A separation

Paulet al. [12] proved that deterministic Turing machines can be speeded up by a factor of log*t (n) using four alternations; that is, DTIME(t(n) log*t(n)) σ₄(t(n)). Balcázaret al. [1] noted that two alternations are sufficient to achieve this speed-up of deterministic Turing machines; that is, DTIME(t(n) log*t(n)) Σ₂(t (n)). We supply a proof of this speed-up and using that show that for each time-constructible functiont(n), DTIME(t(n)) ⊂ Σ₂(t(n)); that is, two alternations are strictly more powerful than deterministic time. An important corollary is that at least one (or both) of the immediate generalizations of the result DTIME(n) ⊂ NTIME(n) [12] must be true: NTIME(n) ≠ co-NTIME(n) or, for each time-constructible functiont(n), DTIME(t (n)) ⊂ NTIME(t (n)). This work was supported in part by NSF Grant CCR-8909071. The preliminary version of the work was done when the author was a graduate student at The Ohio State University.     

On the non-existence of stationary diffusions which satisfy the Bene condition

The one-dimensional diffusion x_t satisfying dx_t = f(x_t)dt + dw_t, where w_t is a standard Brownian motion and f(x) satisfies the Bene condition f′(x) + f²(x) = ax² + bx + c for all real x, is considered. It is shown that this diffusion does not admit a stationary probability measure except for the linear case f(x) = αx + β, α < 0.     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence     

Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

Two specific mappings called doubler f _d and linearizer are introduced to bridge between two kinds of languages. Specifically, f _d maps string languages into (double-stranded) molecular languages, while performs the opposite mapping. Using these mappings, we obtain new characterizations for the families of sticker languages and of Watson-Crick languages, which lead to not only a unified view of the two families of languages but also provide a helpful view on the computational capability of DNA complementarity. Furthermore, we introduce a special type of a projection f _pr which is composed of f _d and a projection in the usual sense. We show that any recursively enumerable language L can be expressed as f _pr (L _m ) for a minimal linear language L _m . This result can be strengthened to L = f _pr (L _s ), for a specific form of minimal linear language L _s , which provides a simple morphic characterization for the family of recursively enumerable languages. A preliminary version of this article appeared in Onodera and Yokomori (2006).     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

A simple population protocol for fast robust approximate majority

We describe and analyze a 3-state one-way population protocol to compute approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x’s, y’s and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability n agents reach consensus in O(n log n) interactions and the value chosen is the majority provided that its initial margin is at least . This protocol has the additional property of tolerating Byzantine behavior in of the agents, making it the first known population protocol that tolerates Byzantine agents.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Optimal regulators for linear systems with no control cost

This article is concerned with the theory of optimal feedback regulator for the linear system =Ax +Bu with the cost functional given byJ(u) = 1/2(Mx(T),x(T)). Due to absence of the usual positive definite quadratic cost for controls, this is a nonstandard problem.Two sets of results are presented: one for bounded and one for unbounded controls. For bounded controls, the control law is given by solving a system of coupled nonlinear differential equations of the Riccati type; and for unbounded controls, the optimal control law is determined by solving a parameterized family of matrix Riccati differential equations.