On the intersection of controllable and reachable sets

In this paper, we prove that the intersection of the controllable set to and the reachable set from a point target is connected, and that points within the intersection have the same controllable and reachable sets. We further demonstrate that the intersection is positive invariant whenever the intersection is not a single point. We then introduce the concept of a maneuverable set which allows us to generalize the results by replacing the point target with a maneuverable set. Use of the theory is illustrated.This paper is based on research supported by NSF Grant INT-82-10803 and the University of Western Australia (Visiting Fellowship, Department of Mathematics, 1983).     

Generalized tangent cone and an optimization problem in a normed space

Most abstract multiplier rules in the literature are based on the tangential approximation at a point to some set in a Banach space. The present paper is concerned with the study of a generalized tangent cone, which is a tangential approximation to that set at a common point of two sets. The new notion of tangent cone generalizes previous concepts of tangent cones. This generalized tangent cone is used to characterize the optimality conditions for a simultaneous maximization and minimization problem. The paper is of theoretical character; practical applications are not found so far.     

Indicating cones and the intersection principle for tangential approximants in abstract multiplier rules

Most abstract Lagrange multiplier rules in the literature are expressions of the separability of a family of two or more convex cones, each of which is some sort of tangential approximation at a point to some set in ⁿ . Broadly speaking, the approximation should be good enough to ensure that the approximants are inseparable only if the sets themselves have nontrivial intersection; the intersection principle is a precise statement of this requirement. This paper establishes the partial ordering by generality among several specific notions of tangential approximation in the literature; it unifies the theory through the introduction of a new notion, called an indicating cone, which still satisfies the intersection principle. For solid cones, all notions of tangential approximant considered coincide.This work was partially supported by a grant from Control Data.     

Reachable Set Bounding for Linear Discrete-Time Systems with Delays and Bounded Disturbances

This paper addresses the problem of reachable set bounding for linear discrete-time systems that are subject to state delay and bounded disturbances. Based on the Lyapunov method, a sufficient condition for the existence of ellipsoid-based bounds of reachable sets of a linear uncertain discrete system is derived in terms of matrix inequalities. Here, a new idea is to minimize the projection distances of the ellipsoids on each axis with different exponential convergence rates, instead of minimization of their radius with a single exponential rate. A smaller bound can thus be obtained from the intersection of these ellipsoids. A numerical example is given to illustrate the effectiveness of the proposed approach.     

Reflection-Projection Method for Convex Feasibility Problems with an Obtuse Cone

The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in the mathematical and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections.In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive-semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies the method of cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection.This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative [resp. positive semidefinite] solution to linear constraints in ⁿ [resp. in , the space of symmetric n×n matrices] and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well.     

A CSP Versus a Zonotope-Based Method for Solving Guard Set Intersection in Nonlinear Hybrid Reachability

Computing the reachable set of hybrid dynamical systems in a reliable and verified way is an important step when addressing verification or synthesis tasks. This issue is still challenging for uncertain nonlinear hybrid dynamical systems. We show in this paper how to combine a method for computing continuous transitions via interval Taylor methods and a method for computing the geometrical intersection of a flowpipe with guard sets, to build an interval method for reachability computation that can be used with truly nonlinear hybrid systems. Our method for flowpipe guard set intersection has two variants. The first one relies on interval constraint propagation for solving a constraint satisfaction problem and applies in the general case. The second one computes the intersection of a zonotope and a hyperplane and applies only when the guard sets are linear. The performance of our method is illustrated on examples involving typical hybrid systems.     

On the attainability problem under state constraints with piecewise smooth boundary

The paper is devoted to the problem of approximating reachable sets for a nonlinear control system with state constraints given as a solution set of a finite system of nonlinear inequalities. Each of these inequalities is given as a level set of a smooth function, but their intersection may have nonsmooth boundary. We study a procedure of eliminating the state constraints based on the introduction of an auxiliary system without constraints such that the right-hand sides of its equations depend on a small parameter. For state constraints with smooth boundary, it was shown earlier that the reachable set of the original system can be approximated in the Hausdorff metric by the reachable sets of the auxiliary control system as the small parameter tends to zero. In the present paper, these results are extended to the considered class of systems with piecewise smooth boundary of the state constraints.     

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.     

具非线性控制变量的非自治松驰系统时间最优追踪控制问题中的若干结果

本文讨论了一类广义非自治离散松驰系统的时间最优控制问题，将R^n中点曲线的目标约束推广为凸集值函数的超曲线约束．在证明了松驰系统与原系统可达集相等的基础上，得到了最优控制的存在性．由凸集分离定理及终端时间闺值函数方程，我们获得了最大值原理及最优控制时间的确定方法．较之Hamilton方法，本文的条件更一般．离散松驰系统的相关结论可以用于分散控制．     

External Ellipsoidal Estimation of the Union of Two Concentric Ellipsoids and Its Applications

For an arbitrary set representable as the convex hull formed by the union of two concentric ellipsoids we propose a method to construct a family of external undominated ellipsoidal approximations and represent the estimated set as the intersection of all estimates from a given family. A sufficient condition of undominated guaranteed ellipsoidal approximation of a convex compactum is derived. A method is described that for certain classes of sets (such as the intersection of an ellipsoid or a cone with two halfspaces) constructs a family of internal undominated ellipsoidal approximations using the previous formulas for the external estimates of the union of concentric ellipsoids.     

On the range sets of variational inequalities

This paper investigates the closedness and convexity of the range sets of the variational inequality (VI) problem defined by an affine mappingM and a nonempty closed convex setK. It is proved that the range set is closed ifK is the union of a polyhedron and a compact convex set. Counterexamples are given such that the range set is not closed even ifK is a simple geometrical figure such as a circular cone or a circular cylinder in a three-dimensional space. Several sufficient conditions for closedness and convexity of the range set are presented. Characterization for the convex hull of the range set is established in the case whereK is a cone, while characterization for the closure of the convex hull of the range set is established in general. Finally, some applications to stability of VI problems are derived.This work was supported by the Australian Research Council.We are grateful to Professors M. Seetharama Gowda, Olvi Mangasarian, Jong-Shi Pang, and Steve Robinson for references. We are thankful to Professor Jim Burke for discussions on Theorem 2.1 and Counterexample 3.5.     

Separation theorems for nonconvex sets and application in optimization

The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.     

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.     

Determination of Inner and Outer Bounds of Reachable Sets Through Subpavings

The computation of the reachable set of states of a given dynamic system is an important step to verify its safety during operation. There are different methods of computing reachable sets, namely interval integration, capture basin, methods involving the minimum time to reach function, and level set methods. This work deals with interval integration to compute subpavings to over or under approximate reachable sets of low dimensional systems. The main advantage of this method is that, compared to guaranteed integration, it allows to control the amount of over-estimation at the cost of increased computational effort. An algorithm to over and under estimate sets through subpavings, which potentially reduces the computational load when the test function or the contractor is computationally heavy, is implemented and tested. This algorithm is used to compute inner and outer approximations of reachable sets. The test function and the contractors used in this work to obtain the subpavings involve guaranteed integration, provided either by the Euler method or by another guaranteed integration method. The methods developed were applied to compute inner and outer approximations of reachable sets for the double integrator example. From the results it was observed that using contractors instead of test functions yields much tighter results. It was also confirmed that for a given minimum box size there is an optimum time step such that with a greater or smaller time step worse results are obtained.     

On elimination of state constraints in the construction of reachable sets

The paper is devoted to the problem of approximating reachable sets of a nonlinear control system with state constraints given as a solution set of a nonlinear inequality. A state constraint elimination procedure based on the introduction of an auxiliary constraintfree control system is proposed. The equations of the auxiliary system depend on a small parameter. It is shown that the reachable set of the original system can be approximated in the Hausdorff metric by reachable sets of the auxiliary control system as the small parameter tends to zero. Estimates of the convergence rate are given.     

On the suitability of minimum and product operators for the intersection of fuzzy sets

In many papers concerning fuzzy set theory it is assumed that the membership or an element in the intersection of two or more fuzzy sets is given by the minimum of product of the corresponding membership values. To use these operators in modelling aspects of the real world, such as decision making, however, it is necessary to prove their appropriateness empirically. The main question of this study is whether people rating the membership of objects in the intersection of two fuzzy sets behave in accordance with one of these models. An important problem in answering this question is how to measure membership which seems to have the characteristics of an absolute scale. No measurement structure is available at present, but a practical method for scaling is suggested. The results of our experiments indicate that neither the product nor the minimum fit the data sufficiently well, but the latter seems to be preferable.     

Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

Philon's line generalized: An optimization problem from geometry

Consider inn-dimensional Euclidean space the intersection of a convex cone and a hyperplane through a given point. The problem is to minimize the (n-1)-volume of this intersection. A geometric interpretation of the first-order optimality condition is given. The special casen=2 is known as a characteristic property of Philon's line.Editorial Note. Because of Professor Wetterling's death on January 21, 1994, this paper was handled by Dr. F. Twilt, Department of Applied Mathematics University of Twente, Enschede, Netherlands.     

Reachability properties of constrained linear systems

This paper presents reachability results for a linear control system and arbitrary terminal pointsp inR ⁿ with controls constrained within a compact setU containing the origin. The well-known results forp=0 are then a special case of our results.Geometric properties of the reachable set are presented and include: general containment properties which describe conditions that guarantee the inclusion of a reachable set in another reachable set; classification of the set of all pointsp that ensure the equivalence of two (different) reachable sets and the properties of this set.The topological properties of the reachable set to a pointp depends on the control setU, the final pointp, and the location of the spectrum of the system in the complex plane. We characterize the geometric properties of the reachable set when the spectrum lies in the closed right-half plane, the open left-half plane, or a combination of both.This work was supported in part by NSF Grant ECS-86-09586.