Scale Invariance Properties in the Simulated Annealing Algorithm

The Boltzmann distribution used in the steady-state analysis of the simulated annealing algorithm gives rise to several scale invariant properties. Scale invariance is first presented in the context of parallel independent processors and then extended to an abstract form based on lumping states together to form new aggregate states. These lumped or aggregate states possess all of the mathematical characteristics, forms and relationships of states (solutions) in the original problem in both first and second moments. These scale invariance properties therefore permit new ways of relating objective function values, conditional expectation values, stationary probabilities, rates of change of stationary probabilities and conditional variances. Such properties therefore provide potential applications in analysis, statistical inference and optimization. Directions for future research that take advantage of scale invariance are also discussed.     

On the poisson output of queueing systems with dependent service times

In this paper a method is stated to conclude that the output of given queueing system is POISSON from the steady-state probabilities and from the behavior of the queueing system at jump epochs, i.e. at epochs when the system state can be changed. The corresponding statement for queueing systems described by Markov processes with denumber-able state space will be generalized to systems which can have arbitrary service time distributions if the steady-state probabilities are insensitive with respect to these distributions.     

Transient Analysis for State-Dependent Queues with Catastrophes

Abstract

Queueing systems with catastrophes and state-dependent arrival and service rates are considered. For two types of queueing systems namely, queues with discouraged arrivals and infinite server queue, explicit expressions for the transient probabilities of system size are obtained by using continued fractions technique. Some system performance measures and steady-state probabilities are studied. The effect of system parameters on system size probabilities are also illustrated numerically. It is observed that the steady-state probabilities differ when catastrophes are present, while they are identical in the absence of catastrophes.     

A method for solving linear differential-algebraic systems of equations supplemented with nonlocal conditions specified by the Stieltjes integral

A method is proposed for solving linear differential-algebraic systems of equations supplemented with nonlocal conditions specified by the Stieltjes integral. The method is based on a series of successive transformations of the original system. The result is either a normal system of differential equations or a system of algebraic equations. In the first case, the use of the supplementary nonlocal condition is realized through the introduction of auxiliary boundary conditions of a standard type.     

Methods of aggregation

We study a class of methods for accelerating the convergence of iterative methods for solving linear systems. The methods proceed by replacing the given linear system with a derived one of smaller size, the aggregated system. The solution of the latter is used to accelerate the original iterative process. The construction of the aggregated system as well as the passage of information between it and the original system depends on one or more approximations of the solution of the latter. A number of variants are introduced, estimates of the acceleration are obtained, and numerical experiments are performed. The theory and computations show the methods to be effective.     

Entrywise perturbation theory and error analysis for Markov chains

Summary Grassmann, Taksar, and Heyman introduced a variant of Gaussian climination for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem itself is well-conditioned, in the sense of entrywise relative error. Thus the algorithm computes each entry of the steady-state vector with low relative error. Even the small steady-state probabilities are computed accurately. The key to our analysis is to focus on entrywise relative error in both the data and the computed solution, rather than making the standard assessments of error based on norms. Our conclusions do not depend on any Condition numbers for the problem.This work was supported by NSF under grants DMS-9106207 and DDM-9203134     

A note on the solution to a common thermal network problem encountered in heat-transfer analysis of spacecraft

A widely used discretization method for modeling thermal systems is the thermal network approach. The network approach is derived from energy balance equations and is equivalent to a particular finite difference discretization of the underlying heat-transfer equation. The steady-state problems that arise in the analysis of spacecraft systems using network models are frequently dominated by radiative transfer, which introduces quartic nonlinearities in the equations. Although these systems are routinely encountered, there has not appeared any detailed analysis of these equations. Questions of existence and uniqueness of solutions and numerical methods for solving the systems have never been addressed in any generality. In this paper, general existence and uniqueness properties of the network equations are established. Globally convergent methods for solving the systems are developed and insight into the relative success of existing methods is given. Numerical examples are presented illustrating the methods. The perspective adopted here is also useful in interdisciplinary applications. A simple example involving thermal control is used to demonstrate this.     

Template-Based Stabilization of Relative Equilibria in Systems with Continuous Symmetry

We present an approach to the design of feedback control laws that stabilize relative equilibria of general nonlinear systems with continuous symmetry. Using a template-based method, we factor out the dynamics associated with the symmetry variables and obtain evolution equations in a reduced frame that evolves in the symmetry direction. The relative equilibria of the original systems are fixed points of these reduced equations. Our controller design methodology is based on the linearization of the reduced equations about such fixed points. We present two different approaches of control design. The first approach assumes that the closed loop system is affine in the control and that the actuation is equivariant. We derive feedback laws for the reduced system that minimize a quadratic cost function. The second approach is more general; here the actuation need not be equivariant, but the actuators can be translated in the symmetry direction. The controller resulting from this approach leaves the dynamics associated with the symmetry variable unchanged. Both approaches are simple to implement, as they use standard tools available from linear control theory. We illustrate the approaches on three examples: a rotationally invariant planar ODE, an inverted pendulum on a cart, and the Kuramoto-Sivashinsky equation with periodic boundary conditions.     

Natural atomic probabilities in quantum information theory

Quantum Information Theory has witnessed a great deal of interest in the recent years since its potential for allowing the possibility of quantum computation through quantum mechanics concepts such as entanglement, teleportation and cryptography. In Chemistry and Physics, von Neumann entropies may provide convenient measures for studying quantum and classical correlations in atoms and molecules. Besides, entropic measures in Hilbert space constitute a very useful tool in contrast with the ones in real space representation since they can be easily calculated for large systems. In this work, we show properties of natural atomic probabilities of a first reduced density matrix that are based on information theory principles which assure rotational invariance, positivity, and N- and v-representability in the Atoms in Molecules (AIM) scheme. These (natural atomic orbital-based) probabilities allow the use of concepts such as relative, conditional, mutual, joint and non-common information entropies, to analyze physical and chemical phenomena between atoms or fragments in quantum systems with no additional computational cost. We provide with illustrative examples of the use of this type of atomic information probabilities in chemical process and systems.     

A Mesh Free Stochastic Algorithm for Solving Diffusion–Convection–Reaction Equations on Complicated Domains

A mesh free stochastic algorithm for solving transient diffusion–convection–reaction problems on domains with complicated structure is suggested. For the solutions of this kind of equations exact representations of the survival probabilities, the probability densities of the first passage time and position on a sphere are obtained. Based on these representations we construct a stochastic algorithm which is simple in implementaion for solving one- and three-dimensional diffusion–convection–reaction equations. The method is continuous both in space and time, and its advantages are particularly well manifested in solving problems on complicated domains, calculating fluxes to parts of the boundary, and other integral functionals, for instance, the total concentration of the particles which have been reacted to a time instant t.     

Stochastic analysis of transit systems

This paper presents two mathematical models representing on surface transit systems with general failure, towing and repair time distributions. The stochastic analysis is performed with the aid of the regeneration point technique. Laplace transforms of the state probabilities are obtained. A number of general formulas are developed for the transit system steady-state availability when one of the system transition rates is described by the Erlangian probability density function. Various plots of transit system steady-state availability are shown.     

Balanced truncation for linear switched systems

We propose a model order reduction approach for balanced truncation of linear switched systems. Such systems switch among a finite number of linear subsystems or modes. We compute pairs of controllability and observability Gramians corresponding to each active discrete mode by solving systems of coupled Lyapunov equations. Depending on the type, each such Gramian corresponds to the energy associated to all possible switching scenarios that start or, respectively end, in a particular operational mode. In order to guarantee that hard to control and hard to observe states are simultaneously eliminated, we construct a transformed system, whose Gramians are equal and diagonal. Then, by truncation, directly construct reduced order models. One can show that these models preserve some properties of the original model, such as stability and that it is possible to obtain error bounds relating the observed output, the control input and the entries of the diagonal Gramians.     

The Minimax Estimation of Solutions of Boundary-Value Problems of Filtration in Multicomponent Schistous Media by Incomplete Data

We consider systems described by boundary-value problems for elliptic second-order partial differential equations with discontinuous coefficients appearing in the study of steady-state processes of filtration of a liquid in multicomponent media under nonhomogeneous conditions of a nonideal contact. Minimax estimates for functionals of solutions of these equations are found by using observations of states of the system. We assume that the right hand sides of equations, boundary conditions, and junction conditions on borders of media as well as errors in measurements are not known precisely, but we know only the sets to which they belong. We prove that the finding of minimax estimates can be reduced to the solving of some systems of integro-differential equations.     

First passage probabilities of one-dimensional diffusion processes

This work is devoted to calculating the first passage probabilities of one-dimensional diffusion processes. For a one-dimensional diffusion process, we construct a sequence of Markov chains so that their absorption probabilities approximate the first passage probability of the given diffusion process. This method is especially useful when dealing with time-dependent boundaries.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

A natural order in dynamical systems based on Conley–Markov matrices

We introduce a natural order to study properties of dynamical systems, especially their invariant sets. The new concept is based on the classical Conley index theory and transition probabilities among neighborhoods of different invariant sets when the dynamical systems are perturbed by white noises. The transition probabilities can be determined by the Fokker–Planck equation and they form a matrix called a Markov matrix. In the limiting case when the random perturbation is reduced to zero, the Markov matrix recovers the information given by the Conley connection matrix. The Markov matrix also produces a natural order from the least to the most stable invariant sets for general dynamical systems. In particular, it gives the order among the local extreme points if the dynamical system is a gradient-like flow of an energy functional. Consequently, the natural order can be used to determine the global minima for gradient-like systems. Some numerical examples are given to illustrate the Markov matrix and its properties.     

Computational methods of solving the boundary value problems for the loaded differential and Fredholm integro‐differential equations

The article presents a new general solution to a loaded differential equation and describes its properties. Solving a linear boundary value problem for loaded differential equation is reduced to the solving a system of linear algebraic equations with respect to the arbitrary vectors of general solution introduced. The system's coefficients and right sides are computed by solving the Cauchy problems for ordinary differential equations. Algorithms of constructing a new general solution and solving a linear boundary value problem for loaded differential equation are offered. Linear boundary value problem for the Fredholm integro‐differential equation is approximated by the linear boundary value problem for loaded differential equation. A mutual relationship between the qualitative properties of original and approximate problems is obtained, and the estimates for differences between their solutions are given. The paper proposes numerical and approximate methods of solving a linear boundary value problem for the Fredholm integro‐differential equation and examines their convergence, stability, and accuracy.     

Transient analysis of a two-heterogeneous servers queue with system disaster,server repair and customers’ impatience

A two-heterogeneous servers queue with system disaster, server failure and repair is considered. In addition, the customers become impatient when the system is down. The customers arrive according to a Poisson process and service time follows exponential distribution. Each customer requires exactly one server for its service and the customers select the servers on fastest server first basis. Explicit expressions are derived for the time-dependent system size probabilities in terms of the modified Bessel function, by employing the generating function along with continued fraction and the identity of the confluent hypergeometric function. Further, the steady-state probabilities of the number of customers in the system are deduced and finally some important performance measures are obtained.