On the boundedness of outer polyhedral estimates for reachable sets of linear systems

New properties of outer polyhedral (parallelepipedal) estimates for reachable sets of linear differential systems are studied. For systems with a stable matrix, it is determined what the orientation matrices are for which the estimates possessing the generalized semigroup property are bounded/unbounded on an infinite time interval. In particular, criteria are found (formulated in terms of the eigenvalues of the system’s matrix and the properties of bounding sets) that guarantee for previously mentioned tangent estimates and estimates with a constant orientation matrix that either there are initial orientation matrices for which the corresponding estimate tubes are bounded or all these tubes are unbounded. For linear stationary systems, a system of ordinary differential equations and algebraic relations is derived that determines estimates with constant orientation matrices for reachable sets that have no generalized semigroup property but are tangent and also bounded if the matrix of the system is stable.     

Estimating reachable sets for two-dimensional linear discrete systems

We are concerned with the problem of estimating the reachable set for a two-dimensional linear discrete-time system with bounded controls. Different approaches are adopted depending on whether the system matrix has real or complex eigenvalues. For the complex eigenvalue case, the quasiperiodic nature of minimum time trajectories is exploited in developing a simple, but often accurate, procedure. For the real eigenvalue case, over estimates of reachable sets can be trivially obtained using a decomposition method.The second author was supported by funds supplied by the John M. Bennett Faculty Fellowship, Trinity University, San Antonio, Texas.     

On the closure of reachable sets for control systems

We prove the existence of a dense subsetD of continuous functions such that, forfD, the reachable set for the control system

Hyperplane method for reachable state estimation for linear time-invariant systems

A numerical algorithm is presented for generating inner and outer approximations for the set of reachable states for linear time-invariant systems. The algorithm is based on analytical results characterizing the solutions to a class of optimization problems which determine supporting hyperplanes for the reachable set. Explicit bounds on the truncation error for the finite-time case yield a set of so-called -supporting hyperplanes which can be generated to approximate the infinite-time reachable set within an arbitrary degree of accuracy. At the same time, an inner approximation is generated as the convex hull of points on the boundary of the finite-time reachable set. Numerical results are presented to illustrate the hyperplane method. The concluding section discusses directions for future work and applications of the method to problems in trajectory planning in servo systems.This research was supported in part by Digital Equipment Corporation through the American Electronics Association Fellowship Loan Program and by the National Science Foundation under Grant No. ECS-84-04607.     

Reachable and controllable sets for two-dimensional,linear, discrete-time systems

We consider two-dimensional discrete-time linear systems with constrained controls. We propose a simple polynomial time procedure to give an exact external representation of theN-step reachable set and controllable set. The bounding hyperplanes are explicitly derived in terms of the data of the problem. By using a result in computational geometry, all the calculations are made in polynomial time in contrast to classical methods. The limit case asN is also investigated.     

Outer ellipsoidal approximations of the reachable set at infinity for linear systems

Outer ellipsoidal approximations to the reachable set at infinity for a linear control system with bounded scalar controls are obtained using a new method based on quadratic Lyapunov functions. These outer approximations are compared with those given by an algorithm due to Sabin and Summers, and also with certain tangential outer approximations, obtained using a fixed-point iteration scheme.This research was supported by the Natural Sciences and Engineering Research Council of Canada. The authors gratefully acknowledge the assistance of Mr. Ryan Davies, recipient of an NSERC Undergraduate Research Award.     

Triple integral approach to reachable set bounding for linear singular systems with time‐varying delay

This paper is concerned with the reachable set estimation problem of singular systems with time‐varying delay and bounded disturbance inputs. Based on a novel Lyapunov–Krasovskii functional that contains four triple integral terms, reciprocally convex approach and free‐weighting matrix method, two sufficient conditions are derived in terms of linear matrix inequalities to guarantee that the reachable set of singular systems with time‐varying delay is bounded by the intersection of ellipsoid. Finally, two numerical examples are given to demonstrate the effectiveness and superiority of the proposed method. Copyright © 2016 John Wiley & Sons, Ltd.     

A new algorithm for the solution of the linear minimax approximation problem

This paper introduces an efficient approach to the solution of the linear mini-max approximation problem. The classical nonlinear minimax problem is cast into a linear formulation. The proposed optimization procedure consists of specifying first a feasible point belonging to the feasible boundary surface. Next, feasible directions of decreasing values of the objective function are determined. The algorithm proceeds iteratively and terminates when the absolute minimum value of the objective function is reached. The initial point May be selected arbitrarily or it May be optimally determined through a linear method to speed up algorithmic convergence. The algorithm was applied to a number of approximation problems and results were compared to those derived using the revised simplex method. The new algorithm is shown to speed up the problem solution by at least on order of magnitude.     

Approximate controllability for trajectories of a delay Volterra control system

For the abstract delay Volterra control system,

A linear approach to shape preserving spline approximation

This paper deals with the approximation of a given large scattered univariate or bivariate data set that possesses certain shape properties, such as convexity, monotonicity, and/or range restrictions. The data are approximated for instance by tensor-product B-splines preserving the shape characteristics present in the data.Shape preservation of the spline approximant is obtained by additional linear constraints. Constraints are constructed which are local linear sufficient conditions in the unknowns for convexity or monotonicity. In addition, it is attractive if the objective function of the resulting minimisation problem is also linear, as the problem can then be written as a linear programming problem. A special linear approach based on constrained least squares is presented, which in the case of large data reduces the complexity of the problem sets in contrast with that obtained for the usual ₂-norm as well as the -norm.An algorithm based on iterative knot insertion which generates a sequence of shape preserving approximants is given. It is investigated which linear objective functions are suited to obtain an efficient knot insertion method.     

A characterization of vNM-stable sets for linear production games

We discuss linear production games or market games with a continuum of players which are represented as minima of finitely many nonatomic measures.?Within this context we consider vNM-Stable Sets according to von Neumann and Morgenstern. We classify or characterize all solutions of this type which are convex polyhedra, i.e., which are the convex hull of finitely many imputations. Specifically, in each convex polyhedral vNM-Stable Set (and not only in the symmetric ones), the different types of traders must organize themselves into cartels. The vNM-Stable Set is then the convex hull of the utility distributions of the cartels.?Using the results from the continuum, we obtain a similar characterization also for finite glove market games. Received December 1998/Revised version June 1999     

Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation

We propose a family of retrospective optimization (RO) algorithms for optimizing stochastic systems with both integer and continuous decision variables. The algorithms are continuous search procedures embedded in a RO framework using dynamic simplex interpolation (RODSI). By decreasing dimensions (corresponding to the continuous variables) of simplex, the retrospective solutions become closer to an optimizer of the objective function. We present convergence results of RODSI algorithms for stochastic “convex” systems. Numerical results show that a simple implementation of RODSI algorithms significantly outperforms some random search algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).     

Ellipsoidal Bounds on Reachable Sets of Dynamical Systems with Matrices Subjected to Uncertain Perturbations1

Linear dynamical systems described by finite-difference or ordinary differential equations are considered. The matrix of the system is uncertain or subject to disturbances, and only the bounds on admissible perturbations of the matrix are known. Outer ellipsoidal estimates of reachable sets of the system are obtained and equations describing the evolution of the approximating ellipsoids are derived. An example is presented.     

Stability of the linear inequality method for rational Chebyshev approximation

The linear inequality method is an algorithm for discrete Chebyshev approximation by generalized rationals. Stability of the method with respect to uniform convergence is studied. Analytically, the method appears superior to all others in reliability.     

Application of wavelet bases in linear and nonlinear approximation to functions from Besov spaces

Linear and nonlinear approximations to functions from Besov spaces B _{p, q} ^σ ([0, 1]), σ > 0, 1 ≤ p, q ≤ ∞ in a wavelet basis are considered. It is shown that an optimal linear approximation by a D-dimensional subspace of basis wavelet functions has an error of order D ^{-min(σ, σ + 1/2 ? 1/p)} for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). An original scheme is proposed for optimal nonlinear approximation. It is shown how a D-dimensional subspace of basis wavelet functions is to be chosen depending on the approximated function so that the error is on the order of D ^?σ for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). The nonlinear approximation scheme proposed does not require any a priori information on the approximated function.     

Semiconvergence in distribution of random closed sets with application to random optimization problems

The paper considers upper semicontinuous behavior in distribution of sequences of random closed sets. Semiconvergence in distribution will be described via convergence in distribution of random variables with values in a suitable topological space. Convergence statements for suitable functions of random sets are proved and the results are employed to derive stability statements for random optimization problems where the objective function and the constraint set are approximated simultaneously. The author is grateful to two anonymous referees for helpful suggestions.     

Exact stability sets for a linear difference system with diagonal delay

This paper is devoted to the stability analysis of a delay difference system of the form xn+1=axn−k+byn, yn+1=cxn+ayn−k, where a, b and c are real numbers and k is a positive integer. We establish some exact conditions for the zero solution of the system to be asymptotically stable.     

An approximation of feasible sets in semi-infinite optimization

The paper deals with the feasible setM of a semi-infinite optimization problem, i.e.M is a subset of the finite-dimensional Euclidean space and is basically defined by infinitely many inequality constraints. Assuming that the extended Mangasarian-Fromovitz constraint qualification holds at all points fromM, it is shown that the quadratic distance function with respect toM is continuously differentiable on an open neighborhood ofM. If, in addition,M is compact, then the set , which is described by this quadratic distance function, is shown to be an appropriate approximation ofM and the setsM and can be topologically identified via a homeomorphism.     

An asymptotic minimax risk bound for estimation of a linear functional relationship

We consider estimation of the parameter B in a multivariate linear functional relationship X_i=ξ_i+ξ_1i, Y_i=Bξ_i+ξ_2i, i=1,…,n, where the errors (ζ_1i^′, ζ_2i^′) are independent standard normal and (ξ_i, i ) is a sequence of unknown nonrandom vectors (incidental parameters). If there are no substantial a priori restrictions on the infinite sequence of incidental parameters then asymptotically the model is nonparametric but does not fit into common settings presupposing a parameter from a metric function space. A special result of the local asymptotic minimax type for the m.1.e. of B is proved. The accuracy of the normal approximation for the m.l.e. of order n^−1/2 is also established.