A new fundamental solution for differential Riccati equations arising in control

The matrix differential Riccati equation (DRE) is ubiquitous in control and systems theory. The presence of the quadratic term implies that a simple linear-systems fundamental solution does not exist. Of course it is well-known that the Bernoulli substitution may be applied to obtain a linear system of doubled size. Here, however, tools from max-plus analysis and semiconvex duality are brought to bear on the DRE. We consider the DRE as a finite-dimensional solution to a deterministic linear/quadratic control problem. Taking the semiconvex dual of the associated semigroup, one obtains the solution operator as a max-plus integral operator with quadratic kernel. The kernel is equivalently represented as a matrix. Using the semigroup property of the dual operator, one obtains a matrix operation whereby the kernel matrix propagates as a semigroup. The propagation forward is through some simple matrix operations. This time-indexed family of matrices forms a new fundamental solution for the DRE. Solution for any initial condition is obtained by a few matrix operations on the fundamental solution and the initial condition. In analogy with standard-algebra linear systems, the fundamental solution can be viewed as an exponential form over a certain idempotent semiring. This fundamental solution has a particularly nice control interpretation, and might lead to improved DRE solution speeds.     

Solution methods and computational investigations for the Linear Bottleneck Assignment Problem

The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected. Supported by the SFB F003 ‘Optimierung und Kontrolle’, Bereich Diskrete Optimierung.     

Dynamics of fisheries with prey reserve and harvesting

A model for two fish species and one predator in a patchy environment is formulated using a deterministic model to study the dynamics of fishery in two homogeneous patches, a free fishing zone and a refuge for prey reserve in which fishing is prohibited. The system is analysed around steady states; the criteria for local and global stabilities are established. The existence of bionomic equilibrium of the system is determined and the conditions for their existence are derived. The optimal harvesting policy is studied by using Pontryagin's maximal principle. Sensitivity analysis is carried out and it is observed that the populations are more sensitive to growth, dispersal and predation rates, least sensitive to the catchability coefficient. Statistical analysis is employed to estimate the parameters and to assess both the uncertainty in the model parameters and in the model-based predictions. Graphical representations of the model are provided.     

Equivalence Classes,Symmetries and Solutions of Linear Third-order Differential Equations

 The subject of this article are third-order differential equations that may be linearized by a variable change. To this end, at first the equivalence classes of linear equations are completely described. Thereafter it is shown how they combine into symmetry classes that are determined by the various symmetry types. An algorithm is presented allowing it to transform linearizable equations by hyperexponential transformations into linear form from which solutions may be obtained more easily. Several examples are worked out in detail. Received February 18, 2002; revised May 10, 2002 Published online: October 24, 2002     

Spanning trees and shortest paths in monge graphs

We investigate three problems onMonge graphs, i.e. complete, undirected weighted graphs whose distance matrix is a Monge matrix: (A) the minimum spanning tree problem, (B) the problem of computing all-pairs shortest paths and (C) the problem of determining a minimum weighted 1-to-all shortest path tree. For all three problems best possible algorithms (in terms of complexity) are presented. This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’/Projektbereich Diskrete Optimierung.     

An improved algorithm for the p-center problem on interval graphs with unit lengths

The p-center problem is to locate p facilities in a network of n   demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O(n)$O(n)$ time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O(pn)$O(\mathit{pn})$.     

Impulsive vaccination of SEIR epidemic model with time delay and nonlinear incidence rate

In this paper, an SEIR epidemic disease model with time delay and nonlinear incidence rate is studied, and the dynamical behavior of the model under pulse vaccination is analyzed. Using the discrete dynamical system determined by the stroboscopic map, we show that there exists an infection-free periodic solution. Further, we show that the infection-free periodic solution is globally attractive when the period of impulsive effect is less than some critical value. Using a new modelling method, we obtain a sufficient condition for the permanence of the epidemic model with pulse vaccination. We show that time delay, pulse vaccination can bring different effects on the dynamic behavior of the model by numerical analysis. Our results also show the time delay is “profitless”. The main feature of this paper is to introduce time delay and impulse into the SEIR epidemic model and to give pulse vaccination strategies.     

Control Invariant Sets of Linear Systems with Bounded Disturbances

In this paper, algorithms to compute robust control invariant sets are proposed for linear continuous-time systems subject to additive but bounded disturbances. Robust control invariant sets of linear time invariant systems are achieved by logarithmic norm. Robust control invariant sets of linear uncertain systems, which are level sets of the storage functions, are obtained by solving functional differential inequality. Simulation shows that the proposed algorithms can yield improved minimal volume robust control invariant sets approximations in comparison with the schemes in the existing literature.     

Local controllability of scalar input systems on 3-manifolds

Local controllability of generic C^k pairs of vector fields in a three dimensional connected manifold M is studied, showing that in general a necessary condition is also sufficient on an open dense subset of the set of points where it is verified. The results obtained are used to determine local controllability for scalar input affine control systems.     

Parallelization of Pipelined Algorithms for Sets of Linear Banded Systems

Solution of independent sets of linear banded systems is a core part of implicit numerical algorithms. In this study we propose a novel pipelined Thomas algorithm with low parallelization penalty. We introduce two-step pipelined algorithms (PAs) formally and show that the idle processor time is invariant with respect to the order of backward and forward steps. Therefore, the parallelization efficiency of the PA cannot be improved directly. However, the processor idle time can be used if some lines have been computed by the time processors become idle. We develop the immediate backward pipelined Thomas algorithm (IB-PTA). The backward step is computed immediately after the forward step has been completed for the first portion of lines. The advantage of the IB-PTA over the basic PTA is the presence of solved lines, which are available for other computations, by the time processors become idle. Implementation of the IB-PTA is based on a proposed static processor schedule that switches between forward and backward computations and controls communication between processors. Computations are performed on the Cray T3E MIMD computer. Combination of the proposed IB-PTA with the “burn from two ends” algorithm shows low parallelization penalty.     

Outer Estimation of Generalized Solution Sets to Interval Linear Systems

The work advances a numerical technique for computing enclosures of generalized AE-solution sets to interval linear systems of equations. We develop an approach (called algebraic) in which the outer estimation problem reduces to a problem of computing algebraic solutions of an auxiliary interval equation in Kaucher complete interval arithmetic.     

Uniformly Stabilizing Sets of Switching Sequences for Switched Linear Systems

A set of switching sequences of a discrete-time switched linear system is said to be uniformly stabilizing if the system is uniformly exponentially stable over all switching sequences that belong to the set. Based on the recent result that a switched linear system is uniformly stable if and only if an increasing countable union of linear matrix inequality conditions is satisfied, we characterize all uniformly stabilizing sets of switching sequences. A discrete-time hybrid automaton of the automobile engine is considered to illustrate the result     

Algorithmic solution of Abel’s equation

The solution scheme for Abel’s equation proposed in this article avoids to a large extent thead hoc methods that have been discovered in the last two centuries since Abel introduced the equation named after him. On the one hand, it describes an algorithmic method for obtaining almost all closed form solutions known in the literature. It is based on Lie’s symmetry analysis. Secondly, for equations without a symmetry, a new method is proposed that allows to generate solutions of all equations within an equivalence class if a single representative has been solved before. It is based on functional decomposition of the absolute invariant of the equation at hand for which computer algebra algorithms have become available recently.     

Continuous and impulsive vaccination of SEIR epidemic models with saturation incidence rates

In this paper, two delayed SEIR epidemic models with continuous and impulsive vaccination and saturating incidence are investigated. The dynamical behaviors of the disease are analyzed. For continuous vaccination, we obtain a basic reproductive number _R1$R_1$ and prove that if _R1≤1$R_1\le 1$ then the disease-free equilibrium is globally attractive and if _R1>1$R_1>1$ then the disease is permanent by using the Lyapunov functional method. For impulsive vaccination, we obtain two thresholds R^∗$R^{\ast }$ and _R∗$R_{\ast }$ and prove that if R^∗<1$R^{\ast }<1$ then the disease-free periodic solution is globally attractive and if _R∗>1$R_{\ast }>1$ then the disease is permanent by using the comparison theorem of impulsive differential equation and the Lyapunov functional method. Lastly, we compared the effects of two vaccination strategies.     

A storage scheme for extendible arrays

Conventional methods of storing aK-dimensional array allow easy extension only along one dimension. We present a technique of allocating a linear sequence of contiguous storage locations for aK-dimensional extendible array by adjoining blocks of (K–1)-dimensional subarrays. Element access is by determination of the block header location and then the displacement within the block. For cubical and all practical cases of rectangular arrays considered, the storage requirement isO (N) whereN is the array size. The element access cost isO (K) for the 2-step computed access function used.

---

Ein Speicherschema für erweiterbare Felder

Zusammenfassung Konventionelle Methoden der SpeicherungK-dimensionaler Felder lassen eine einfache Erweiterung lediglich entlang einer Dimension zu. Wir beschreiben eine Technik der Zuweisung einer linearen Folge von zusammenhängenden Speicherzellen fürK-dimensional erweiterbare Felder durch Hinzufügen von Blöcken aus (K–1)-dimensionierten Teilfeldern. Der Elementzugriff erfolgt durch Bestimmung des Headers und des Displacements innerhalb des Blockes. Für kubische und alle praktische Fälle rechteckiger Felder ist der SpeicherbedarfO (N) wobeiN die Feldgröße ist. Die Kosten eines Elementzugriffs betragenO (K) für die in zwei Schritten berechnete Zugriffsfunktion.

     

On the use of incomplete sensitivities for feedback control of laminar vortex shedding

A feedback control method based on incomplete sensitivities and gradient evaluation by complex variable method is proposed and applied to the problem of the control of the laminar vortex shedding past a circular cylinder. This procedure results in a low-cost control algorithm, which does not require to compute the gradient of the Navier–Stokes solution with respect to the controllers. For the sake of usability for practical applications, realistic sensors and actuators are used. Validation simulations aiming at controlling the drag of the cylinder are presented and compared with previous published results, proving the efficiency of the proposed method. Application to the control of the cylinder lift is also shown.     

Euler polygonal method for metric dynamical systems

Following some ideas developed for equations with a nonlinear differential, we consider the existence and uniqueness of solution for the metric dynamical system (F,x₀) and we study the approximation, under appropriate hypotheses, of the unique solution using the Euler polygonal approximation method in relation with function F.     

部分参数不准确的线性系统的鲁棒性控制

研究了部分参数不准确的线性系统在有界能量噪声作用下的控制问题,即对于系统参数的鲁棒性控制问题.先将它简化为一个带正参数δ的H∞控制问题,然后采用J无损分解方法,推导出调节问题的可解性条件和动态反馈控制器的全部显示通解.