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.     

Generalized solutions of a stochastic partial differential equation

We discuss the Cauchy problem of a certain stochastic parabolic partial differential equation arising in the nonlinear filtering theory, where the initial data and the nonhomogeneous noise term of the equation are given by Schwartz distributions. The generalized (distributional) solution is represented by a partial (conditional) generalized expectation ofT(t)° _0,t ^–1 , whereT(t) is a stochastic process with values in distributions and _s,t is a stochastic flow generated by a certain stochastic differential equation. The representation is used for getting estimates of the solution with respect to Sobolev norms.Further, by applying the partial Malliavin calculus of Kusuoka-Stroock, we show that any generalized solution is aC -function under a condition similar to Hörmander's hypoellipticity condition.     

Rate conservation laws: A survey

We survey the rate conservation law, RCL for short, arising in queues and related stochastic models. RCL was recognized as one of the fundamental principles to get relationships between time and embedded averages such as the extended Little's formulaH=G, but we show that it has other applications. For example, RCL is one of the important techniques for deriving equilibrium equations for stochastic processes. It is shown that the various techniques, including Mecke's formula for a stationary random measure, can be formulated as RCL. For this purpose, we start with a new definition of the rate with respect to a random measure, and generalize RCL by using it. We further introduce the notion of quasi-expectation, which is a certain extension of the ordinary expectation, and derive RCL applicable to the sample average results. It means that the sample average formulas such asH=G can be obtained as the stationary RCL in the quasi-expectation framework. We also survey several extensions of RCL and discuss examples. Throughout the paper, we would like to emphasize how results can be easily obtained by using a simple principle, RCL.     

Exact results for the asymmetric simple exclusion process with a blockage

We present new results for the current as a function of transmission rate in the one-dimensional totally asymmetric simple exclusion process (TASEP) with a blockage that lowers the jump rate at one site from one tor<1. Exact finitevolume results serve to bound the allowed values for the current in the infinite system. This proves the existence of a nonequilibrium phase transition, corresponding to an immiscibility gap in the allowed values of the asymptotic densities which the infinite system can have in a stationary state. A series expansion inr, derived from the finite systems, is proven to be asymptotic for all sufficiently large systems. Padé approximants based on this series, which make specific assumptions about the nature of the singularity atr=1, match numerical data for the infinite system to 1 part in 10⁴.     

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.     

Stochastic dominance with nonadditive probabilities

Choquet expected utility which uses capacities (i.e. nonadditive probability measures) in place of-additive probability measures has been introduced to decision making under uncertainty to cope with observed effects of ambiguity aversion like the Ellsberg paradox. In this paper we present necessary and sufficient conditions for stochastic dominance between capacities (i.e. the expected utility with respect to one capacity exceeds that with respect to the other one for a given class of utility functions). One wide class of conditions refers to probability inequalities on certain families of sets. To yield another general class of conditions we present sufficient conditions for the existence of a probability measureP with f dC= f dP for all increasing functionsf whenC is a given capacity. Examples includen-th degree stochastic dominance on the reals and many cases of so-called set dominance. Finally, applications to decision making are given including anticipated utility with unknown distortion function.     

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.     

Analysis of grid file algorithms

Grid file algorithms were suggested in [12] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions:O(v ^c ) orO(v ), wherec=1+b^–1, =1+(s-1)/(sb+1),s is the number of attributes being used,v the file size, andb the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.