Efficient simulation of general stochastic hybrid systems

General Stochastic Hybrid System (SHS) are characterised by Stochastic Differential Equations (SDEs) with discontinuities and Poisson jump processes. SHS are useful in model based design of Cyber-Physical System (CPS) controllers under uncertainty. Industry standard model based design tools such as Simulink/Stateflow® are inefficient when simulating, testing, and validating SHS, because of dependence on fixed-step Euler–Maruyama (EM) integration and discontinuity detection. We present a novel efficient adaptive step-size simulation/integration technique for general SHSs modelled as a network of Stochastic Hybrid Automatons (SHAs). We propose a simulation algorithm where each SHA in the network executes synchronously with the other, at an integration step-size computed using adaptive step-size integration. Ito’ multi-dimensional lemma and the inverse sampling theorem are leveraged to compute the integration step-size by making the SDEs and Poisson jump rate integration dependent upon discontinuities. Existence and convergence analysis along with experimental results show that the proposed technique is substantially faster than Simulink/Stateflow®when simulating general SHSs.     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

The ground-state energy of the ±J sping glass. A comparison of various biologically motivated algorithms

We compare various evlutionary strategies to determine the ground-state energy of the ±J spin glass. We show that the choice of different evolution laws is less important than a suitable treatment of the free spins of the system At least one combination of these strategies does not give the correct results, but the ground states of the other different strategies coincide. Therefore we are able to extrapolate the infinit-size ground-state energy for the square lattice to –1.401±0.0015 and for the simple cubic lattice to –1.786±0.004.     

Local minima of the trust region problem

We consider the minimization of a quadratic formzVz+2zq subject to the two-norm constraint z=. The problem received considerable attention in the literature, notably due to its applications to a class of trust region methods in nonlinear optimization. While the previous studies were concerned with just the global minimum of the problem, we investigate the existence of all local minima. The problem is approached via the dual Lagrangian, and the necessary and sufficient conditions for the existence of all local minima are derived. We also examine the suitability of the conventional numerical techniques used to solve the problem to a class of single-instruction multiple-data computers known as processor arrays (in our case, AMT DAP 610). Simultaneously, we introduce certain hardware-oriented multisection algorithms, showing their efficiency in the case of small to medium size problems.This research was partially supported by the National Physical Laboratories of England under Contract RTP2/155/127.     

Trigonometric wavelets for Hermite interpolation

The aim of this paper is to investigate a multiresolution analysis of nested subspaces of trigonometric polynomials. The pair of scaling functions which span the sample spaces are fundamental functions for Hermite interpolation on a dyadic partition of nodes on the interval . Two wavelet functions that generate the corresponding orthogonal complementary subspaces are constructed so as to possess the same fundamental interpolatory properties as the scaling functions. Together with the corresponding dual functions, these interpolatory properties of the scaling functions and wavelets are used to formulate the specific decomposition and reconstruction sequences. Consequently, this trigonometric multiresolution analysis allows a completely explicit algorithmic treatment.

     

Heuristic methods for evolutionary computation techniques

Evolutionary computation techniques, which are based on a powerful principle of evolution—survival of the fittest, constitute an interesting category of heuristic search. In other words, evolutionary techniques are stochastic algorithms whose search methods model some natural phenomena: genetic inheritance and Darwinian strife for survival.Any evolutionary algorithm applied to a particular problem must address the issue of genetic representation of solutions to the problem and genetic operators that would alter the genetic composition of offspring during the reproduction process. However, additional heuristics should be incorporated in the algorithm as well; some of these heuristic rules provide guidelines for evaluating (feasible and infeasible) individuals in the population. This paper surveys such heuristics and discusses their merits and drawbacks.An abridged version of this paper appears in the volume entitled META-HEURISTICS: Theory & Application, edited by Ibrahim H. Osman and James P. Kelly, to be published by Kluwer Academic Publishers in March 1996.     

Nonmonotone bundle-type scheme for convex nonsmooth minimization

In this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view.This work was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica and by ASI: Agenzia Spaziale Italiana.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.