Output feedback stabilization for a class of nonlinear time-evolution systems

A variety of problems in nonlinear time-evolution systems such as communication networks, computer networks, manufacturing, traffic management, etc., can be modelled as min–max-plus systems in which operations of min, max and addition appear simultaneously. Systems with only maximum (or minimum) constraints can be modelled as max-plus system and handled by max-plus algebra which changes the original nonlinear system in the traditional sense into linear system in this framework. Min-max-plus systems are extensions of max-plus systems and nonlinear even in the max-plus algebra view. Output feedback stabilization for min–max-plus systems with min–max-plus inputs and max-plus outputs is considered in this paper. Max-plus projection representation for the closed-loop system with min–max-plus output feedback is introduced and the formula to calculate the cycle time is presented. Stabilization of reachable systems with at least one observable state and a further result for reachable and observable systems are worked out, during which max-plus output feedbacks are used to stabilize the systems. The method based on the max-plus algebra is constructive in nature.     

A generalized eigenmode algorithm for reducible regular matrices over the max-plus algebra with applications to the Metro-bus public transport system in Mexico city

In this paper, an algorithm for computing a generalized eigenmode of reducible regular matrices over the max-plus algebra is applied to the Metro-bus public transport system in Mexico city. A timed event Petri net model is constructed from the data table that characterizes the transport system. A max-plus recurrence equation, with a reducible and regular matrix, is associated with the transport system timed event Petri net. Next, given the reducible and regular matrix, the problem consists of giving an algorithm which will tell us how to compute its generalized eigenmode over the max plus algebra. The solution to the problem is achieved by studying some type of recurrence equations. In fact, by transforming the reducible regular matrix into its normal form, and considering a very specific recurrence equation, an explicit mathematical characterization is obtained, upon which the algorithm is constructed. The generalized eigenmode obtained sets a timetable for the transport system.     

Min-Max Spaces and Complexity Reduction in Min-Max Expansions

Idempotent methods have been found to be extremely helpful in the numerical solution of certain classes of nonlinear control problems. In those methods, one uses the fact that the value function lies in the space of semiconvex functions (in the case of maximizing controllers), and approximates this value using a truncated max-plus basis expansion. In some classes, the value function is actually convex, and then one specifically approximates with suprema (i.e., max-plus sums) of affine functions. Note that the space of convex functions is a max-plus linear space, or moduloid. In extending those concepts to game problems, one finds a different function space, and different algebra, to be appropriate. Here we consider functions which may be represented using infima (i.e., min-max sums) of max-plus affine functions. It is natural to refer to the class of functions so represented as the min-max linear space (or moduloid) of max-plus hypo-convex functions. We examine this space, the associated notion of duality and min-max basis expansions. In using these methods for solution of control problems, and now games, a critical step is complexity-reduction. In particular, one needs to find reduced-complexity expansions which approximate the function as well as possible. We obtain a solution to this complexity-reduction problem in the case of min-max expansions.     

The General Theory of Linear Difference Equations over the Max-Plus Semi-Ring

We present the mathematical theory underlying systems of linear difference equations over the max-plus semi-ring. The result provides an analog of isomonodromy theory for ultradiscrete Painlevé equations, which are extended cellular automata, and provide evidence for their integrability. Our theory is analogous to that developed by Birkhoff and his school for linear q -difference equations, but stands independently of the latter. As an example, we derive linear problems in this algebra for ultradiscrete versions of the symmetric P_IV equation and show how it is a necessary condition for isomonodromic deformation of a linear system.     

Max-Plus Stochastic Control and Risk-Sensitivity

In the Maslov idempotent probability calculus, expectations of random variables are defined so as to be linear with respect to max-plus addition and scalar multiplication. This paper considers control problems in which the objective is to minimize the max-plus expectation of some max-plus additive running cost. Such problems arise naturally as limits of some types of risk sensitive stochastic control problems. The value function is a viscosity solution to a quasivariational inequality (QVI) of dynamic programming. Equivalence of this QVI to a nonlinear parabolic PDE with discontinuous Hamiltonian is used to prove a comparison theorem for viscosity sub- and super-solutions. An example from mathematical finance is given, and an application in nonlinear H-infinity control is sketched.     

连续型凸动态规划的离散近似迭代法研究

为解决连续型凸动态规划的“维数灾”问题,提出了一种新的算法—离散近似迭代法.该算法的基本思路为:首先,将连续型状态变量离散化,根据网络图的构造方法将动态规划问题转化为多阶段有向赋权图;其次,运用极大代数求出起点至终点的最短路,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.文章还证明了该算法的收敛性和线性收敛,并以一个具体例子验证了算法的有效性.     

Primitive idempotents in central simple algebras over Fq(t) with an application to coding theory

We consider the algorithmic problem of computing a primitive idempotent of a central simple algebra over the field of rational functions over a finite field. The algebra is given by a set of structure constants. The problem is reduced to the computation of a division algebra Brauer equivalent to the central simple algebra. This division algebra is constructed as a cyclic algebra, once the Hasse invariants have been computed. We give an application to skew constacyclic convolutional codes.     

A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)

We propose an algorithm for finding the so-called principal solution of the Sylvester matrix equation over max-plus algebra. The derivation of our algorithm is based on the concept of tropical tensor product introduced by Butkovi? and Fiedler. Our algorithm reduces the computational cost of finding the principal solution from quartic to cubic. It also reduces the space complexity from quartic to quadratic. Since matrix–matrix multiplication is the most important ingredient of our proposed technique, we show how to use column-oriented matrix multiplications in order to speed-up MATLAB implementation of our algorithm. Finally, we illustrate our results and discuss the connection with the residuation theory.     

Origami,geometry and art

The purpose of this paper is to describe the mathematics that emanates from the construction of an origami box. We first construct a simple origami box from a rectangular sheet and then discuss some of the mathematical questions that arise in the context of geometry and algebra. The activity can be used as a context for illustrating how algebra and geometry, like other branches of mathematics, are interrelated.     

Optimization of Single-Item Multi-Stage Stochastic Production — Inventory Systems

This paper presents a mathematical model developed for optimization of single-item multi-stage production-inventory systems. The demands are assumed to occur randomly at the same rate whereas processing and setup times are different, each following exponential distributions with different means. The model assumes a "one-for-one ordering" inventory policy and that on total system cost expression comprising setup, holding and penalty costs is obtained for optimization. As a special case, single stage, cost expressions become the same as those obtained by Baker. Computational results for two stages are given. Implications of aggregating the two stages into an equivalent simple stage are discussed.     

Max-Plus Objects to Study the Complexity of Graphs

Given an undirected graph G, we define a new object H _G , called the mp-chart of G, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of H _G in terms of the adjacency matrix of G and we give a central limit theorem for H _G . Finally, we show that the mp-chart is easily tractable also for the complement graph.     

Mathematical art and artistic mathematics

ABSTRACT

The purpose of this note is to describe the mathematics that emanates from the construction of an origami box. We first construct a simple origami box from two rectangular sheets and then discuss some of the mathematical questions that arise in the context of geometry and algebra.     

Ergodic Type Bellman Equations of First Order with Quadratic Hamiltonian

We consider Bellman equations of ergodic type in first order. The Hamiltonian is quadratic on the first derivative of the solution. We study the structure of viscosity solutions and show that there exists a critical value among the solutions. It is proved that the critical value has the representation by the long time average of the kernel of the max-plus Schrödinger type semigroup. We also characterize the critical value in terms of an invariant density in max-plus sense, which can be understood as a counterpart of the characterization of the principal eigenvalue of the Schrödinger operator by an invariant measure.     

The Lie Theory of Two-Variable Hypergeometric Functions

We develop a Lie-algebraic method that associates with each of the 34 distinct second-order hypergeometric functions in two variables a canonical system of partial differential equations. The special functions arise by partial separation of variables in these simple systems. Some consequences are a demonstration that all such functions appear as solutions of the 4-variable wave equation and a classification of the possible imbeddings. In each case the functions are characterized by first- and second-order operators in the enveloping algebra of the conformal symmetry algebra for the wave equation. In some cases the 3-variable wave and heat equations and the 2-variable Helmholtz equation also arise. This intimate relationship between Horn functions and some fundamental equations of mathematical physics shows that these functions are more interesting than was previously recognized and permits use of the powerful tools of Lie theory and separation of variables to obtain properties of the functions.     

Symmetry breaking of systems of linear second-order ordinary differential equations with constant coefficients

We show that the structure of the Lie symmetry algebra of a system of n linear second-order ordinary differential equations with constant coefficients depends on at most n-1 parameters. The tools used are Jordan canonical forms and appropriate scaling transformations. We put our approach to test by presenting a simple proof of the fact that the dimension of the symmetry Lie algebra of a system of two linear second-order ordinary differential with constant coefficients is either 7, 8 or 15. Also, we establish for the first time that the dimension of the symmetry Lie algebra of a system of three linear second-order ordinary differential equations with constant coefficients is 10, 12, 13 or 24.     

极大加可约矩阵的谱与周期时间向量的关系

提出了极大加代数上可约矩阵特征值的缺失值及冗余值的概念,得到了相应的定理;对特征值与周期时间向量分量之间的关系作了深入的研究.     

Cohomologies of the Lie Algebra of Vector Fields on a Line

Providing adequate mathematical tools, we find cohomologies of the Lie algebra of smooth vector fields on a line with coefficients in the trivial, natural, and adjoint representations. We construct the generalized series of complexes and calculate the corresponding cohomologies.     

Measuring rates of convergence of numerical algorithms

We analyze the behavior of common indices used in numerical linear algebra, analysis, and optimization to measure rates of convergence of an algorithm. A simple consistent axiomatic structure is used to uniquely define convergence rate measures on the basic linear, superlinear, and sublinear scales in terms of standard comparison sequences. Agreement with previously utilized indices and related measures is discussed.This research was supported in part by grants from the Natural Sciences and Engineering Research Council of Canada.The authors are grateful to the referees for comments which improved an earlier draft.