Balance Properties and Stabilization of Min-Max Systems

A variety of problems in operations research, performance analysis, manufacturing, and communication networks, etc., can be modelled as discrete event systems with minimum and maximum constraints. When such systems require only maximum constraints (or dually, only minimum constraints), they can be studied using linear methods based on max-plus algebra. Systems with mixed constraints are called min-max systems in which min, max and addition operations appear simultaneously. A significant amount of work on such systems can be seen in literature. In this paper we provide some new results with regard to the balance problem of min-max functions; these are the structure properties of min-max systems. We use these results in the structural stabilization. Our main results are two sufficient conditions for the balance and one sufficient condition for the structural stabilization. The block technique is used to analyse the structure of the systems. The proposed methods, based on directed graph and max-plus algebra are constructive in nature. We provide several examples to demonstrate how the methods work in practice.     

Cycle time assignment of min-max systems

A variety of problems in computer networks, digital circuits, communication networks, manufacturing plants, etc., can be modelled as discrete event systems with maximum and minimum constraints. Systems with mixed constraints are non-linear and are called min-max systems. The cycle time vector of such a system arises as a performance measure for discrete event systems and provides the appropriate non-linear generalization of the spectral radius. This paper gives a complete account of the cycle time assignment by the state feedback for min-max systems. We describe some new definitions and results about such assignment which generalize the initial earlier works and shed new light on aspects of linear control theory. For an arbitrary min-max system, by introducing the concept of colouring graph and constructing the total condensation and its matrix representation, we give the canonical structure form. In order to design the state feedback system in which the internal structure property is unchanged and the cycle time can be assigned, we introduce and characterize the assignability, uniform state feedback and unmerged assignment for min-max systems. We present an algorithm for the unmerged assignment and illustrate our algorithm by means of an example.     

On the Computational Power of Max-Min Propagation Neural Networks

We investigate the computational power of max-min propagation (MMP) neural networks, composed of neurons with maximum (Max) or minimum (Min) activation functions, applied over the weighted sums of inputs. The main results presented are that a single-layer MMP network can represent exactly any pseudo-Boolean function F:{0,1} ⁿ [0,1], and that two-layer MMP neural networks are universal approximators. In addition, it is shown that several well-known fuzzy min-max (FMM) neural networks, such as Simpson's FMM, are representable by MMP neural networks.     

Geometric synthesis of a hybrid limit cycle for the stabilizing control of a class of nonlinear switched dynamical systems

This paper proposes a new constructive method for synthesizing a hybrid limit cycle for the stabilizing control of a class of switched dynamical systems in R², switching between two discrete modes and without state discontinuity. For each mode, the system is continuous, linear or nonlinear. This method is based on a geometric approach. The first part of this paper demonstrates a necessary and sufficient condition of the existence and stability of a hybrid limit cycle consisting of a sequence of two operating modes in R² which respects the technological constraints (minimum duration between two successive switchings, boundedness of the real valued state variables). It outlines the established method for reaching this hybrid limit cycle from an initial state, and then stabilizing it, taking into account the constraints on the continuous variables. This is then illustrated on a Buck electrical energy converter and a nonlinear switched system in R². The second part of the paper proposes and demonstrates an extension to Rⁿ for a class of systems, which is then illustrated on a nonlinear switched system in R³.     

An efficient algorithm for finding ideal schedules

We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O(n ³) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper. Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O(n ³) time, while the most efficient solution to date has required O(n ⁹) time.     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

A faster parametric minimum-cut algorithm

Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n³+kn²) total time, provided that the capacity changes are made in order. Using dynamic trees their time bound isO(nm log(n²/m)+km log(n²/m)). We show how to reduce the total time, using a simple algorithm, to O(n³+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n²/m)+kn log(n²/m)). We further reduce the total time toO(n ²m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not in order, provided we only need the minimum cuts; if the flows are required then the times are respectively O(n³+km) and O(n²m). We illustrate the utility of these results by applying them to therectilinear layout problem.The research of Dan Gusfield was partially supported by Grants CCR-8803704 and CCR-9103937 from the National Science Foundation. The research of Éva Tardos was partially supported by a David and Lucile Packard Fellowship, an NSF Presidential Young Investigator Fellowship, a Research Fellowship of the Sloan Foundation, and by NSF, DARPA, and ONR through Grant DMS89-20550 from the National Science Foundation.     

Correlation structure of training data and the fitting ability of back propagation networks: Some experimental results

White [6–8] has theoretically shown that learning procedures used in network training are inherently statistical in nature. This paper takes a small but pioneering experimental step towards learning about this statistical behaviour by showing that the results obtained are completely in line with White's theory. We show that, given two random vectorsX (input) andY (target), which follow a two-dimensional standard normal distribution, and fixed network complexity, the network's fitting ability definitely improves with increasing correlation coefficient r_XY (0r_XY1) betweenX andY. We also provide numerical examples which support that both increasing the network complexity and training for much longer do improve the network's performance. However, as we clearly demonstrate, these improvements are far from dramatic, except in the case r_XY=+ 1. This is mainly due to the existence of a theoretical lower bound to the inherent conditional variance, as we both analytically and numerically show. Finally, the fitting ability of the network for a test set is illustrated with an example.Nomenclature X Generalr-dimensional random vector. In this work it is a one-dimensional normal vector and represents the input vector - Y Generalp-dimensional random vector. In this work it is a one-dimensional normal vector and represents the target vector - Z Generalr+p dimensional random vector. In this work it is a two-dimensional normal vector - E Expectation operator (Lebesgue integral) - g(X)=E(Y¦X) Conditional expectation - Experimental random error (defined by Eq. (2.1)) - y Realized target value - o Output value - f Network's output function. It is formally expressed asf: R ^r×WR ^p, whereW is the appropriate weight space - Average (or expected) performance function. It is defined by Eq. (2.2) as (w)=E[(Yf(X,w)],w W - Network's performance - w ^* Weight vector for optimal solution. That is, the objective of network is such that (w ^*) is minimum - C ₁ Component one - C ₂ Component two - Z Matrix of realised values of the random vectorZ overn observations - Z _t Transformed matrix version ofZ in such a way thatX andY have values in [0,1] - X _t ,Y _t Transformed versions ofX andY and both are standard one-dimensional normal vectors - n _h Number of hidden nodes (neurons) - r _XY Correlation coefficient between eitherX andY orX _t andY _t - _s and _k in Eq. (3.1) and afterwards _s is average value of 100 differentZ _t matrices. _k is the error function ofkthZ _t , matrix. In Eq. (3.1), the summation is fromk=1 to 100, and in Eq. (3.2) fromi=1 ton. In Eq. (3.2)o _ki andy _ki are the output and target values for the kthZ _t matrix and ith observation, respectively - ^1/2(w ^*) and _k (w_n) k(w_n) is the sample analogue of ^1/2(w ^*) - _Y ² In Eq. (4.1) and afterwards, _Y ² is the variance ofY - _Y ² variance ofY _t . In Sect. 4.3 the transformation isY _t=a Y+b - Y _max,Y _min the maximum and minimum values ofY - R Correlation matrix ofX andY - Covariance matrix ofX andY - Membership symbol in set theory     

On risk concentration for convex combinations of linear estimators

We consider the estimation problem for an unknown vector β ∈ Rp in a linear model Y = Xβ + σξ, where ξ ∈ Rⁿ is a standard discrete white Gaussian noise and X is a known n × p matrix with n ≥ p. It is assumed that p is large and X is an ill-conditioned matrix. To estimate β in this situation, we use a family of spectral regularizations of the maximum likelihood method β^α(Y) = H ^α(X ^T X) β ^?(Y), α ∈ R⁺, where β ^?(Y) is the maximum likelihood estimate for β and {H ^α(·): R⁺ → [0, 1], α ∈ R⁺} is a given ordered family of functions indexed by a regularization parameter α. The final estimate for β is constructed as a convex combination (in α) of the estimates β^α(Y) with weights chosen based on the observations Y. We present inequalities for large deviations of the norm of the prediction error of this method.