Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions

Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: Metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the Metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous-time interpolations of the Metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.The research reported here has been supported by the Whirlpool Foundation, by the Air Force Office of Scientific Research under Contract 89-0276, and by the Army Research Office under Contract DAAL-03-86-K-0171 (Center for Intelligent Control Systems).     

On the limit of the largest eigenvalue of the large dimensional sample covariance matrix

Summary In this paper the authors show that the largest eigenvalue of the sample covariance matrix tends to a limit under certain conditions when both the number of variables and the sample size tend to infinity. The above result is proved under the mild restriction that the fourth moment of the elements of the sample sums of squares and cross products (SP) matrix exist.Research sponsored by the Air Force Office of Scientific Research under Contract F49620-C-0008. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereonThe work of this author was done when he was working at the Center for Multivariate Analysis, University of Pittsburgh.     

Limit set of inhomogeneous Ornstein-Uhlenbeck processes,destabilization and annealing

We consider the Diffusion Process obtained by perturbing a dynamical system having a single equilibrium point x, by a fixed time-inhomogeneous Gaussian process whose intensity tends to 0 at infinity. We establish criteria for the exit time from a neighborhood of x to be a.s. finite by linking this fact with the structure of the limit set at infinity. We are also able to compute this limit set for inhomogeneous Ornstein-Uhlenbeck processes associated to linear systems. An application is given to simulated annealing.     

Asymptotic behavior of a system of interacting nuclear-space-valued stochastic differential equations driven by Poisson random measures

In this paper we study a system of interacting stochastic differential equations taking values in duals of nuclear spaces driven by Poisson random measures. We also consider the McKean-Vlasov equation associated with the system. We show that under suitable conditions the system has a unique solution and the sequence of its empirical distributions converges to the solution of the McKean-Vlasov equation when the size of the system tends to infinity. The results are applied to the voltage potentials of a large system of neurons and the limiting distribution of the empirical measure is obtained.This research was supported by the National Science Foundation, the Air Force Office of Scientific Research under Grant No. F49620-92-J-0154, and the Army Research Office under Grant No DAAL03-92-G-0008.     

Nonexistence of an a priori bound at the center in terms of anL 1 bound on the boundary for solutions of uniformly elliptic equations on a sphere

Summary Positive solutions on the unit sphere of second order uniformly elliptic nonvariational equations are found which exhibit behavior sharply differing from that of positive harmonic functions, despite the fact that the coefficients may be uniformly arbitrarily close (at least for n=2) to those of the Laplacian. A solution is found whose boundary integral on expanding concentric subspheres tends to zero and another is found for which this boundary iutegral tends to infinity. This work was supported by the Air Force Office of Scientific Research and the National Academy of Sciences through a Postdoctoral Research Fellowship for 1964–1965 at the University of Genova.     

Asymptotic normality determined by high moments,and submap counts of random maps

We give a general result showing that the asymptotic behaviour of high moments determines the shape of distributions which are asymptotically normal. Both the factorial and non-factorial (non-central) moments are treated. This differs from the usual moment method in combinatorics, as the expected value may tend to infinity quite rapidly. Applications are given to submap counts in random planar triangulations, where we use a simple argument to asymptotically determine high moments for the number of copies of a given subtriangulation in a random 3-connected planar triangulation. Similar results are also obtained for 2-connected triangulations and quadrangulations with no multiple edges.Revised version: 6 February 2004Research supported by NSERCC and University of Macau.Research supported by the Australian Research Council and the Canada Research Chairs program. Research carried mainly while the author was at the Department of Mathematics and Statistics, University of Melbourne.     

Total risk aversion,stochastic optimal control,and differential games

We present a connection between the theory of risk in the context of a stochastic optimal control problem and its relation to the theory of differential games. In particular, we define the notion of total risk aversion from the viewpoint of the upper value of a differential game. We prove that as the index of absolute risk aversion of a utility function in a stochastic control problem converges to infinity the (certainty equivalent) optimal payoff converges to the upper value of an associated deterministic differential game. The two main points of this paper are (1) a precise characterization oftotal risk aversion and (2) the construction of a stochastic optimal control problem intimately connected to a deterministic differential game.Partially supported by the Air Force Office of Scientific Research Grant No. AFOSR-86-0202.Partially supported by a grant from the National Science Foundation.     

Embedding and asymptotic expansions for martingales

The paper develops a way of embedding general martingales in continuous ones in such a way that the quadratic variation of the continuous martingale has conditional cumulants (given the original martingale) that are explicitly given in terms of optional and predictable variations of the original process. Bartlett identities for the conditional cumulants are also found. A main corollary to these results is the establishment of second (and in some cases higher) order asymptotic expansions for martingales.Research supported in part by National Science Foundation grant DMS 93-05601 and Army Research Office grant DAAH04-1-0105     

On the existence of equivalent finite invariant measures

Summary Necessary and sufficient conditions are given for the existence of a finite measure which is equivalent to a given measure and invariant with respect to each transformation in a given commutative semigroup of measurable null-invariant point transformations. This result was already known for denumerably generated semigroups. A complementary result is proved which states that if one such equivalent measure exists, then there exists a unique equivalent measure which agrees with the original measure on the invariant sets.Research sponsored by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force, under Grant No. AFOSR-68-1394.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Stopping rules,permutation invariance and sufficiency principle

In the context of sequential (point as well as interval) estimation, a general formulation of permutation-invariant stopping rules is considered. These stopping rules lead to savings in the ASN at the cost of some elevation of the associated risk—a phenomenon which may be attributed to the violation of the sufficiency principle. For the (point and interval) sequential estimation of the mean of a normal distribution, it is shown that such permutation-invariant stopping rules may lead to a substantial saving in the ASN with only a small increase in the associated risk.Work partially supported by (i) Office of Naval Research, Contract Number N00014-85-K-0548, and (ii) Office of Naval Research, Contract Number N00014-83-K-0387.     

On the average cost optimality equation and the structure of optimal policies for partially observable Markov decision processes

We consider partially observable Markov decision processes with finite or countably infinite (core) state and observation spaces and finite action set. Following a standard approach, an equivalent completely observed problem is formulated, with the same finite action set but with anuncountable state space, namely the space of probability distributions on the original core state space. By developing a suitable theoretical framework, it is shown that some characteristics induced in the original problem due to the countability of the spaces involved are reflected onto the equivalent problem. Sufficient conditions are then derived for solutions to the average cost optimality equation to exist. We illustrate these results in the context of machine replacement problems. Structural properties for average cost optimal policies are obtained for a two state replacement problem; these are similar to results available for discount optimal policies. The set of assumptions used compares favorably to others currently available.This research was supported in part by the Advanced Technology Program of the State of Texas, in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, and in part by the Air Force Office of Scientific Research (AFSC) under Contract F49620-89-C-0044.     

A reduction method for variational inequalities

This paper explains a method by which the number of variables in a variational inequality having a certain form can be substantially reduced by changing the set over which the variational inequality is posed. The method applies in particular to certain economic equilibrium problems occurring in applications. We explain and justify the method, and give examples of its application, including a numerical example in which the solution time for the reduced problem was approximately 2% of that for the problem in its original form. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number F49620-95-1-0222, and by the U.S. Army Research Office under grant number DAAH04-95-1-0149. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

A comparison theorem on convergence rates of random walks on groups

We give a comparison theorem which helps us to estimate the change in the convergence rate when we enlarge the support of a probability that generates a random walk, and/or change the original mass assignment. Some examples of applications of this theorem are discussed.Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

Active constraints,indefinite quadratic test problems,and complexity

The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.The authors thank the reviewers for their constructive comments. The first author was supported by the National Science Foundation Grant DMS-85-20926 and by the Air Force Office of Scientific Research Grant AFOSR-ISSA-86-0091.     

Feasible directions algorithms for optimization problems with equality and inequality constraints

In this paper two algorithms, of the feasible-directions and dual feasible-directions type, are presented for optimization problems with equality and inequality constraints. An associated problem, having only inequality constraints, is defined, and shown to be equivalent to the original problem if a certain parameter is sufficiently large. The algorithms solve the associated problem, but incorporate a method for automatically increasing this parameter in order to ensure global convergence to a solution to the original problem. Any feasible directions algorithm can be similarly modified to enable it to handle equality constraints.Research sponsored by the US Army Research Office — Durham, Contract DAHCO4-73-C-0025 and the National Science Foundation Grant GK-37572.     

Scheduling sports competitions at multiple venues—Revisited

In this work, we study scheduling sports competitions at multiple venues, a problem recently introduced by Urban and Russell [T.L. Urban, R.A. Russell, Scheduling sports competitions on multiple venues, European Journal of Operational Research 148 (2003) 302–311]. The distinguishing feature of the problem is that venues come into play when scheduling. We develop beam search and simulated annealing approaches to the problem and its extension. Computational experiments were conducted and algorithms compared and analyzed. We found that the simulated annealing algorithm with specialized neighborhood moves achieved superior solutions in significantly shorter times than the method of Urban and Russell.     

Approximation of the distribution of convergence times for stochastic global optimisation

How long should we run a stochastic global optimisation algorithm such as simulated annealing? How should we tune such an algorithm? This paper proposes an approach to the study of these questions through successive approximation of a generic stochastic global optimisation algorithm with a sequence of stochastic processes, culminating in a backtracking adaptive search process. Our emerging understanding of backtracking adaptive search can thus be used to study the original algorithm. The first approximation, the averaged range process, has the same expected number of iterations to convergence as the original process.     

The alternate-block-factorization procedure for systems of partial differential equations

The alternate-block-factorization (ABF) method is a procedure for partially decoupling systems of elliptic partial differential equations by means of a carefully chosen change of variables. By decoupling we mean that the ABF strategy attempts to reduce intra-equation coupling in the system rather than intra-grid coupling for a single elliptic equation in the system. This has the effect of speeding convergence of commonly used iteration schemes, which use the solution of a sequence of linear elliptic PDEs as their main computational step. Algebraically, the change of variables is equivalent to a postconditioning of the original system. The results of using ABF postconditioning on some problems arising from semiconductor device simulation are discussed.The work of R. E. Bank was supported in part by the Office of Naval Research under contract N00014-82K-0197. The work of T. F. Chan was supported in part by the National Science Foundation under grant NSF-DMS87-14612 and by the Army Research Office under contract DAAL03-88-K-0085.