Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint-propagation techniques

We investigate solution techniques for numerical constraint-satisfaction problems and validated numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in the presence of uncertainty. To use interval simulation tools with higher-dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an analytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as numerical constraint-satisfaction problems, which are solved using global search methods based on branch-and-prune algorithms, interval analysis and consistency techniques. The method is illustrated with hybrid systems with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.     

含约束非线性动力系统的分岔分类

讨论含约束非线性动力系统分岔的分类.研究表明,约束分岔的转迁集,除分岔集、滞后集和双极限点集外,还有三种转迁集是它特有的.在此基础上提出了一种约束分岔问题的奇异性分类方法.     

Energy interaction between linear and nonlinear oscillators (energy transfer through the subsystems in a hybrid system)

The analysis of the energy transfer between subsystems coupled in a hybrid system is an urgent problem for various applications. We present an analytic investigation of the energy transfer between linear and nonlinear oscillators for the case of free vibrations when the oscillators are statically or dynamically connected into a double-oscillator system and regarded as two new hybrid systems, each with two degrees of freedom. The analytic analysis shows that the elastic connection between the oscillators leads to the appearance of a two-frequency-like mode of the time function and that the energy transfer between the subsystems indeed exists. In addition, the dynamical linear constraint between the oscillators, each with one degree of freedom, coupled into the hybrid system changes the dynamics from single-frequency modes into two-frequency-like modes. The dynamical constraint, as a connection between the subsystems, is realized by a rolling element with inertial properties. In this case, the analytic analysis of the energy transfer between linear and nonlinear oscillators for free vibrations is also performed. The two Lyapunov exponents corresponding to each of the two eigenmodes are expressed via the energy of the corresponding eigentime components. Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 6, pp. 796–814, June, 2008.     

Computing reachable sets for uncertain nonlinear monotone systems

We address nonlinear reachability computation for uncertain monotone systems, those for which flows preserve a suitable partial orderings on initial conditions. In a previous work Ramdani (2008) [22], we introduced a nonlinear hybridization approach to nonlinear continuous reachability computation. By analysing the signs of off-diagonal elements of system’s Jacobian matrix, a hybrid automaton can be obtained, which yields component-wise bounds for the reachable sets. One shortcoming of the method is induced by the need to use whole sets for addressing mode switching. In this paper, we improve this method and show that for the broad class of monotone dynamical systems, component-wise bounds can be obtained for the reachable set in a separate manner. As a consequence, mode switching no longer needs to use whole solution sets. We give examples which show the potentials of the new approach.     

The Exact Traveling Wave Solutions to Two Integrable KdV6 Equations

The exact explicit traveling solutions to the two completely integrable sixthorder nonlinear equations KdV6 are given by using the method of dynamical systems and Cosgrove's work.It is proved that thes...     

小参数时变非线性系统的技术稳定性

分析一类含小参数的时变非线性系统关于给定状态约束集合的技术稳定性.根据向量微分比较原理和基本的单调性准则,利用向量V函数方法给出由系统系数表达的技术稳定性判据.并讨论了基于派生系统和线性化方法研究非线性系统技术稳定性的条件.另外,对于派生时变线性系统的指数稳定性给出了简单的代数判据.最后给出示例说明文中方法.     

一类稀疏约束非线性规划的约束规格

研究一类带有闭凸集约束的稀疏约束非线性规划问题,这类问题在变量选择、模式识别、投资组合等领域具有广泛的应用.首先引进了限制性Slater约束规格的概念,证明了该约束规格强于限制性M-F约束规格,然后在此约束规格成立的条件下,分析了其局部最优解成立的充分和必要条件.最后,对约束集合的两种具体形式,指出限制性Slater约束规格必满足,并给出了一阶必要性条件的具体表达形式.     

On the convergence of Han's method for convex programming with quadratic objective

We present an iterative method for minimizing strictly convex quadratic functions over the intersection of a finite number of convex sets. The method consists in computing projections onto the individual sets simultaneously and the new iterate is a convex combination of those projections. We give convergence proofs even for the inconsistent case, i.e. when the intersection of the sets is empty.Work of this author was partially supported by CNPq under grant No. 301280/86-MA.     

Stability of uniform attractors of impulsive multi-valued semiflows

In this paper we investigate stability of uniformly attracting sets for semiflows generated by impulsive infinite-dimensional dynamical systems without uniqueness. Obtained abstract results are applied to weakly nonlinear parabolic system, whose trajectories have jumps at moments of intersection with certain surface in the phase space.     

On mixing sets arising in chance-constrained programming

The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single chance constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems.     

Finding safety in partially controllable chaotic systems

Many discrete-time dynamical systems have a region Q from which all or almost all trajectories leave, or at least they leave in the presence of perturbations that we call disturbances. We partially control systems so that despite disturbances the trajectories of a dynamical system stay in the region Q at least for some initial points in Q. The disturbances can be thought of as either noise or as purposeful, hostile efforts of an enemy to drive the trajectory out of the region. Our goal is to keep trajectories inside Q despite the disturbances and our partial control of chaos method succeeds.Surprisingly this goal can be achieved with a control whose maximum allowable size is smaller than the maximum allowed disturbance. A fundamental step towards this goal is to compute a set called the safe set that had, until now, been found only in certain very special situations.This paper provides a general algorithm for computing safe sets. The algorithm is able to compute the safe sets for a specified region in phase space, the maximum disturbance value, and the maximum allowed control. We call it the Sculpting Algorithm. Its operation is analogous to removing material while sculpting a statue. The algorithm sculpts the safe sets. Our Sculpting Algorithm is independent of the dimension and is fast for one- and two-dimensional dynamical systems. As examples, we apply the algorithm to two paradigmatic nonlinear dynamical systems, namely, the Hénon map and the Duffing oscillator.     

A philosophy for the modelling of realistic nonlinear systems

A nonlinear dynamical system is modelled as a nonlinear mapping from a set of input signals into a corresponding set of output signals. Each signal is specified by a set of real number parameters, but such sets may be uncountably infinite. For numerical simulation of the system each signal must be represented by a finite parameter set and the mapping must be defined by a finite arithmetical process. Nevertheless the numerical simulation should be a good approximation to the mathematical model. We discuss the representation of realistic dynamical systems and establish a stable approximation theorem for numerical simulation of such systems.

     

Enclosure of the Zero Set of Multivariate Exponential Interval Polynomials

The zero set of one general multivariate exponential polynomial with interval coefficients is enclosed by unions and intersections of closed half-spaces. Tighter enclosures are derived in the bivariate case. Common zeros of polynomial systems can be located by an appropriate intersection of these enclosure sets in an appropriate space. The resulting domains are directly brought into polynomial equation solvers.     

Constraint propagation,relational arithmetic in AI systems and mathematical programs

This paper explores the interrelationships between methods developed in mathematical programming to discover the structure of constraint (feasibility) sets and constraint propagation over networks used by some AI systems to perform inferences about quantities. It is shown that some constraint set problems in mathematical programming are equivalent to inferencing problems for constraint networks with interval labels. This makes the inference and query capabilities associated with AI systems that use logic programming, directly accessible to mathematical programming systems. On the other hand, traditional and newer methods which mathematical programming uses to obtain information about its associated feasibility set can be used to determine the propagation of constraints in a network of nodes of an AI system. When viewed from this point of view, AI problems can access additional mathematical programming analytical tools including new ways to incorporate qualitative data into constraint sets via interval and fuzzy arithmetic.This work was partially supported by the Industrial Consortium to Develop an Intelligent Mathematical Programming System — Amoco Oil Company, General Research Corporation, Ketron Management Science, Shell Oil Company, MathPro, and US West Advanced Technologies.     

Asymptotic behavior for solutions of a one-dimensional parabolic equation with homogeneous Neumann boundary conditions

We investigate a nonlinear autonomous parabolic partial differential equation in one space variable subject to Neumann boundary conditions on a compact interval. The object of our study is to determine the asymptotic behavior of solutions. Our methods are borrowed from the Liapunov theory of stability for dynamical systems. We give conditions under which a solution has a nonempty ω-limit set. We show that any such ω-limit set consists solely of equilibrium solutions. We render criteria for asymptotic stability and for instability of an equilibrium solution. We examine the possibility of escape behavior.     

Epsilon Dominance and Constraint Partitioning in Multiple Objective Problems

In this paper we consider efficient sets of multiple objective problems, in which the feasible action set is the intersection of two other sets, and where one of these sets has a special structure, such as an assignment or transportation structure. The objective is to find the efficient set of the special structure set, and its intersection with the other set, and to examine how good an approximation this set is to the desired efficient set. The approximation set is called an -efficient solution set. Some theoretical partition results are given for a special constraint structure with upper bounds on the objective function levels. For the case of 0-efficient solution sets, and finite explicit sets, a computational cost analysis of two computational sequences is given. We also consider two other 0-efficient solution set cases. Then -efficiency is considered for linear problems. Finally, the approach is illustrated by a special multiple objective transportation problem.     

Computation of spectral sets for uncertain linear fractional-order systems

The present paper proposes an algorithm to compute the spectral set of a family of fractional-order pseudo-polynomials. The algorithm makes use of interval constraint propagation technique to find out all the structural roots of the given uncertain fractional-order systems in the given search domain. It is first shown that the problem of finding the spectral set can be formulated as an interval constraint satisfaction problem and then solved using branch and prune algorithm. The algorithm guarantees that all the points of the spectral set are computed to prescribed accuracy. The proposed algorithm is demonstrated on a plant with nonlinear parametric dependencies and also on a practical application of a gas turbine plant.     

A numerical approach to design control invariant sets for constrained nonlinear discrete-time systems with guaranteed optimality

A numerical approach to design control invariant sets for constrained nonlinear discrete-time systems with guaranteed optimality is proposed in this paper. The addressed approach is based on the fact that zonotopes are more flexible for representing sets than boxes in interval analysis. Then the solver of set inversion via interval analysis is extended to set inversion via zonotope geometry by introducing the novel idea of bisecting zonotopes. The main feature of the extended solver of set inversion is the bisection and the evolution of a zonotope rather than a box. Thus the shape of admissible domains for set inversion can be broadened from boxes to zonotopes and the wrapping effect can be reduced as well by using the zonotope evolution instead of the interval evolution. Combined with global optimization via interval analysis, the extended solver of set inversion via zonotope geometry is further applied to design control invariant sets for constrained nonlinear discrete-time systems in a numerical way. Finally, the numerical design of a control invariant set and its application to the terminal control of the dual-mode model predictive control are fulfilled on a benchmark Continuous-Stirred Tank Reactor example.     

Stability of the intersection of solution sets of semi-infinite systems

Many mathematical programming models arising in practice present a block structure in their constraint systems. Consequently, the feasibility of these problems depends on whether the intersection of the solution sets of each of those blocks is empty or not. The existence theorems allow to decide when the intersection of non-empty sets in the Euclidean space, which are the solution sets of systems of (possibly infinite) inequalities, is empty or not. In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the sets is preserved by sufficiently small perturbations or not. This paper focuses on the stability of the non-empty (empty) intersection of the solutions of some given systems, which can be seen as the images of set-valued mappings. We give sufficient conditions for the stability, and necessary ones as well; in particular we consider (semi-infinite) convex systems and also linear systems. In this last case we discuss the distance to ill-posedness.     

Convergence of the gradient projection method and Newton’s method as applied to optimization problems constrained by intersection of a spherical surface and a convex closed set

The gradient projection method and Newton’s method are generalized to the case of nonconvex constraint sets representing the set-theoretic intersection of a spherical surface with a convex closed set. Necessary extremum conditions are examined, and the convergence of the methods is analyzed.