Integrating and accelerating tabu search,simulated annealing,and genetic algorithms

We integrate tabu search, simulated annealing, genetic algorithms, and random restarting. In addition, while simulating the original Markov chain (defined on a state space tailored either to stand-alone simulated annealing or to the hybrid scheme) with the original cooling schedule implicitly, we speed up both stand-alone simulated annealing and the combination by a factor going to infinity as the number of transitions generated goes to infinity. Beyond this, speedup nearly linear in the number of independent parallel processors often can be expected.This research was (partially) supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract #F49620-90-C-0033.     

Control of a hybrid conditionally linear Gaussian process

A control problem is considered where the coefficients of the linear dynamics are functions of a noisily observed Markov chain. The approximation introduced is to consider these coefficients as functions of the filtered estimate of the state of the chain; this gives rise to a finite-dimensional conditional Kalman filter. A minimum principle and a new equation for an adjoint process are obtained.This research was partially supported by NSERC under Grant A-7964, by the US Air Force Office of Scientific Research under Contract AFOSR-86-0332, and by the US Army Research Office under Contract DAAL03-87-0102.The authors obtained these results during a visit to UCSD by the first author in January 1990. This author wishes to thank Professor D. D. Sworder and his department for their hospitality.     

Optimal switching among a finite number of Markov processes

This paper investigates the problem of the optimal switching among a finite number of Markov processes, generalizing some of the author's earlier results for controlled one-dimensional diffusion. Under rather general conditions, it is shown that the optimal discounted cost function is the unique solution of a functional equation. Under more restrictive assumptions, this function is shown to be the unique solution of some quasi-variational inequalities. These assumptions are verified for a large class of control problems. For controlled Markov chains and controlled one-dimensional diffusion, the existence of a stationary optimal policy is established. Finally, a policy iteration method is developed to calculate an optimal stationary policy, if one exists.This research was sponsored by the Air Force Office of Scientific Research (AFSC), United States Air Force, under Contract No. F-49620-79-C-0165.The author would like to thank the referee for bringing Refs. 7, 8, and 9 to his attention.     

Linear complexity algorithms for semiseparable matrices

Linear complexity algorithms are derived for the solution of a linear system of equations with the coefficient matrix represented as a sum of diagonal and semiseparable matrices. LDU-factorization algorithms for such matrices and their inverses are also given. The case in which the solution can be efficiently update is treated separately.This work was supported in part by the U.S. Army Research Office, under Contract DAAG29-83-K-0028, and the Air Force Office of Scientific Research, Air Force Systems Command under Contract AF83-0228.     

On the computation of the optimal cost function for discrete time Markov models with partial observations

We consider several applications of two state, finite action, infinite horizon, discrete-time Markov decision processes with partial observations, for two special cases of observation quality, and show that in each of these cases the optimal cost function is piecewise linear. This in turn allows us to obtain either explicit formulas or simplified algorithms to compute the optimal cost function and the associated optimal control policy. Several examples are presented.Research supported 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, in part by the Advanced Technology Program of the State of Texas, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

On a direct method for the solution of nearly uncoupled Markov chains

Summary This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associated with aggregation and the coupling respectively.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

The optimal control of diffusions

Using a differentiation result of Blagovescenskii and Freidlin calculations of Bensoussan are simplified and the adjoint process identified in a stochastic control problem in which the control enters both the drift and diffusion coefficients. A martingale representation result of Elliott and Kohlmann is then used to obtain the integrand in a stochastic integral, and explicit forward and backward equations satisfied by the adjoint process are derived.This research was partially supported by NSERC under Grant A7964, the U.S. Air Force Office of Scientific Research under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-K-0102.     

Control of partially observed diffusions

The optimal control of a partially observed diffusion is discussed when the control parameter is present in both the drift and diffusion coefficients. Using a differentiation result of Blagovescenskii and Freidlin, and adapting techniques of Bensoussan, we obtain a stochastic minimum principle.This research was partially supported by NSERC Grant A7964, by the US Air Force Office of Scientific Research Contract AFOSR-86-0332, and by the US Army Research Office Contract DAAL03-87-K-0102.     

Mean stochastic comparison of diffusions

Summary Stochastic bounds are derived for one dimensional diffusions (and somewhat more general random processes) by dominating one process pathwise by a convex combination of other processes. The method permits comparison of diffusions with different diffusion coefficients. One interpretation of the bounds is that an optimal control is identified for certain diffusions with controlled drift and diffusion coefficients, when the reward function is convex. An example is given to show how the bounds and the Liapunov function technique can be applied to yield bounds for multidimensional diffusions.This work was supported by the Office of Naval Research under Contract N00014-82-K-0359 and the U.S. Army Research Office under Contract DAAG29-82-K-0091 (administered through the University of California at Berkeley).     

A partially observed control problem for Markov chains

A finite state, continuous time Markov chain is considered and the solution to the filtering problem given when the observation process counts the total number of jumps. The Zakai equation for the unnormalized conditional distribution is obtained and the control problem discussed in separated form with this as the state. A new feature is that, because of the correlation between the state and observation process, the control parameter appears in the diffusion coefficient which multiplies the Poisson noise in the Zakai equation. By introducing a Gâteaux derivative the minimum principle, satisfied by an optimal control, is derived. If the optimal control is Markov, a stochastic integrand can be obtained more explicitly and new forward and backward equations satisfied by the adjoint process are obtained.This research was partially supported by NSERC Grant A7964, the Air Force Office of Scientific Research, United States Air Force, under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-0102.     

Occupation Measures of Singularly Perturbed Markov Chains with Absorbing States

Abstract This paper develops asymptotic properties of singularly perturbed Markov chains with inclusion of absorbing states. It focuses on both unscaled and scaled occupation measures. Under mild conditions, a mean-square estimate is obtained. By averaging the fast components, we obtain an aggregated process. Although the aggregated process itself may be non-Markovian, its weak limit is a Markov chain with much smaller state space. Moreover, a suitably scaled sequence consisting of a component of scaled occupation measures and a component of the aggregated process is shown to converge to a pair of processes with a switching diffusion component. * The research of this author is supported in part by the National Science Foundation under Grant DMS-9877090 ** The research of this author is supported in part by the Office of Naval Research Grant N00014-96-1-0263 *** The research of this author is supported in part by Wayne State University     

Local convergence of interior-point algorithms for degenerate monotone LCP

Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

A χ2 goodness-of-fit test for Markov renewal processesgoodness-of-fit test for Markov renewal processes

A Markov Renewal Process (M.R.P.) is a process similar to a Markov chain, except that the time required to move from one state to another is not fixed, but is a random variable whose distribution may depend on the two states between which the transition is made. For an M.R.P. ofm (<∞) states we derive a goodness-of-fit test for a hypothetical matrix of transition probabilities. This test is similar to the test Bartlett has derived for Markov chains. We calculate the first two moments of the test statistic and modify it to fit the moments of a standard χ². Finally, we illustrate the above procedure numeerically for a particular case of a two-state M.R.P. Dwight B. Brock is mathematical statistican, Office of Statistical Methods, National Center for Health Statistics, Rockville, Maryland. A. M. Kshisagar is Associate Professor, Department of Statistics, Southern Methodist University. This research was partially supported by Office of Naval Research Contract No. N000 14-68-A-0515, and by NIH Training Grant GM-951, both with Southern Methodist University. This article is partially based on Dwight B. Brock's Ph.D. dissertation accepted by Southern Methodist University.     

The empirical behavior of sampling methods for stochastic programming

We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

Canonical representations of partial 2- and 3-trees

We give algorithms constructing canonical representations of partial 2-trees (series parallel graphs) and partial 3-trees. The algorithms can be implemented in log-linear space, or in linear time using quadratic space.Supported in part by a grant from the Swedish Natural Science Research Council.Research supported in part by the Office of Naval Research Contract N00014-86-K-0419.     

Fast algorithms for the integral equations of the inverse scattering problem

The Gelfand-Levitan and Marchenko equations of inverse scattering theory are integral equations with Toeplitz and Hankel kernels respectively. It is shown that these facts can be used to reduce the integral equations to differential equations which can be solved with an order of magnitude less computation than generally envisaged.This work was supported by the Army Research Office under Contract DAAG29-77-C-0042, by the Air Force Office of Scientific Research, Air Force Systems Command, under Contract AF44-620-74-C-0068 and the Australian Research Grants Committee.     

Adaptive control of Markov processes with incomplete state information and unknown parameters

Recent results for parameter-adaptive Markov decision processes (MDP's) are extended to partially observed MDP's depending on unknown parameters. These results include approximations converging uniformly to the optimal reward function and asymptotically optimal adaptive policies.This research was supported in part by the Consejo del Sistema Nacional de Educación Tecnologica (COSNET) under Grant 178/84, in part by the Air Force Office of Scientific Research under Grant AFOSR-84-0089, in part by the National Science Foundation under Grant ECS-84-12100, and in part by the Joint Services Electronics Program under Contract F49602-82-C-0033.