Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

Decoupled reliability-based geotechnical design of deep excavations of soil with spatial variability

This paper presents a general decoupled method for reliability-based geotechnical design that takes into account the spatial variability of soil properties. In this method, reliability analyses that require a lot of computational resources are decoupled from the optimization procedure by approximating the failure probability function globally. Failure samples are iteratively generated over the entire design space so that their global distribution information can be extracted to construct the failure probability function. The method is computationally efficient, is flexible to implement, and is well suited for geotechnical problems that may involve sophisticated models. A design example of two-dimensional deep excavation against basal heave is discussed for Singapore marine clay where the density and normalized undrained shear strength of soil mass are modeled as random fields. Results demonstrate that the proposed method works well in practice and is advantageous over the coupled or locally decoupled reliability-based geotechnical design methods.     

Convex polyhedra of distributions preserved by operations over a finite field

We construct families of polyhedra in the space of probability distributions over a finite field, which are preserved, i.e., adding or multiplying independent random variables with distributions from the constructed set, the resulting distribution belongs to the same set.     

A new lattice Boltzmann model for the laplace equation

In this paper, a new lattice Boltzmann equation which is independent of time is proposed. Based on the new lattice Boltzmann equation, some steady problems can be modeled by the lattice Boltzmann method. In the further study, the Laplace equation is investigated with the method of the higher-order moment of equilibrium distribution functions and a series of partial differential equations in different space scales. The numerical results show that the new method is effective.     

Nondifferentiable variational principles in terms of a quantum operator

We develop Cresson's nondifferentiable calculus of variations on the space of Hölder functions. Several quantum variational problems are considered: with and without constraints, with one and more than one independent variable, of first and higher‐order type. Copyright © 2011 John Wiley & Sons, Ltd.     

Distribution of spatial requirements for a MAP/G/1 queue when space and service times are dependent

In this paper, we consider a MAP/G/1 queue in which each customer arrives with a service and a space requirement, which could be dependent. However, the space and service requirements of different customers are assumed to be independent. Each customer occupies its space requirement in a buffer until it has completely received its service, at which time, it relinquishes the space it occupied. We study and solve the problem of finding the steady-state distribution of the total space requirement of all customers present in the system. In the process of doing so, we also generalize the solution of the MAP/G/1 queue and find the time-average joint distribution of the queue-length, the state of the arrival process and the elapsed service time, conditioned on the server being busy. This problem has applications to the design of buffer requirements for a computer or communication system.     

Approximate dynamic programming via direct search in the space of value function approximations

This paper deals with approximate value iteration (AVI) algorithms applied to discounted dynamic programming (DP) problems. For a fixed control policy, the span semi-norm of the so-called Bellman residual is shown to be convex in the Banach space of candidate solutions to the DP problem. This fact motivates the introduction of an AVI algorithm with local search that seeks to minimize the span semi-norm of the Bellman residual in a convex value function approximation space. The novelty here is that the optimality of a point in the approximation architecture is characterized by means of convex optimization concepts and necessary and sufficient conditions to local optimality are derived. The procedure employs the classical AVI algorithm direction (Bellman residual) combined with a set of independent search directions, to improve the convergence rate. It has guaranteed convergence and satisfies, at least, the necessary optimality conditions over a prescribed set of directions. To illustrate the method, examples are presented that deal with a class of problems from the literature and a large state space queueing problem setting.     

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions

Summary. Multilevel Schwarz methods are developed for a conforming finite element approximation of second order elliptic problems. We focus on problems in three dimensions with possibly large jumps in the coefficients across the interface separating the subregions. We establish a condition number estimate for the iterative operator, which is independent of the coefficients, and grows at most as the square of the number of levels. We also characterize a class of distributions of the coefficients, called quasi-monotone, for which the weighted -projection is stable and for which we can use the standard piecewise linear functions as a coarse space. In this case, we obtain optimal methods, i.e. bounds which are independent of the number of levels and subregions. We also design and analyze multilevel methods with new coarse spaces given by simple explicit formulas. We consider nonuniform meshes and conclude by an analysis of multilevel iterative substructuring methods. Received April 6, 1994 / Revised version received December 7, 1994     

On the convergence in law of almost all sums of independent random variables

The paper deals with sums of independent and identically distributed random variables defined on some probability space which are multiplied by random coefficients. These coefficients are the values of independent random variables defined on another probability space. We obtain conditions for the weak convergence of weighted sums, for almost all coefficients, to some infinitely divisible distribution. The limit distribution for these sums is found. Supported by the Russian Foundation for Fundamental Research (grant No. 93-011-16099). Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow, 1993.     

Comparison of two variances under inequality constraints by using empirical likelihood method

In this article, the empirical likelihood introduced by Owen Biometrika, 75, 237-249 （1988） is applied to test the variances of two populations under inequality constraints on the parameter space. One reason that we do the research is because many literatures in this area are limited to testing the mean of one population or means of more than one populations; the other but much more important reason is： even if two or more populations are considered, the parameter space is always without constraint. In reality, parameter space with some kind of constraints can be met everywhere. Nuisance parameter is unavoidable in this case and makes the estimators unstable. Therefore the analysis on it becomes rather complicated. We focus our work on the relatively complicated testing issue over two variances under inequality constraints, leaving the issue over two means to be its simple ratiocination. We prove that the limiting distribution of the empirical likelihood ratio test statistic is either a single chi-square distribution or the mixture of two equally weighted chi-square distributions.     

Use of Pτ-nets for the approximation of the Edgeworth-Pareto set in multicriteria optimization

Engineering optimization problems, design problems among them, are multicriteria in their essence. When designing machines, mechanisms, and structures, one has to deal with numerous contradictory criteria.Experience gained in solving engineering optimization and optimal design problems shows that the designer cannot formulate them correctly. Unfortunately, the known optimization methods offer little assistance. To assure a correct formulation and solution of engineering optimization problems, the parameter space investigation (PSI) method and methods of approximation have been developed and widely integrated into different fields of industry, science, and technology. The PSI method has become one of the basic working tools for choosing optimal parameters in many fields of the national economy in Russia.     

Single Sample Path-Based Optimization of Markov Chains

Motivated by the needs of on-line optimization of real-world engineering systems, we studied single sample path-based algorithms for Markov decision problems (MDP). The sample path used in the algorithms can be obtained by observing the operation of a real system. We give a simple example to explain the advantages of the sample path-based approach over the traditional computation-based approach: matrix inversion is not required; some transition probabilities do not have to be known; it may save storage space; and it gives the flexibility of iterating the actions for a subset of the state space in each iteration. The effect of the estimation errors and the convergence property of the sample path-based approach are studied. Finally, we propose a fast algorithm, which updates the policy whenever the system reaches a particular set of states and prove that the algorithm converges to the true optimal policy with probability one under some conditions. The sample path-based approach may have important applications to the design and management of engineering systems, such as high speed communication networks.This work was supported in part by     

Nonatomic total rewards Markov decision processes with multiple criteria

We consider a Markov decision process with an uncountable state space for which the vector performance functional has the form of expected total rewards. Under the single condition that initial distribution and transition probabilities are nonatomic, we prove that the performance space coincides with that generated by nonrandomized Markov policies. We also provide conditions for the existence of optimal policies when the goal is to maximize one component of the performance vector subject to inequality constraints on other components. We illustrate our results with examples of production and financial problems.     

Fixed Point Optimality Criteria for the Location Problem with Arbitrary Norms

The single-facility location problem in continuous space is considered, with distances given by arbitrary norms. When distances are Euclidean, for many practical problems the optimal location of the new facility coincides with one of the existing facilities. This property carries over to problems with generalized distances. In this paper a necessary and sufficient condition for the location of an existing facility to be the optimal location of the new facility is developed. Some computational examples using the condition are given.     

A comparative study of null‐space factorizations for sparse symmetric saddle point systems

Null‐space methods for solving saddle point systems of equations have long been used to transform an indefinite system into a symmetric positive definite one of smaller dimension. A number of independent works in the literature have identified that we can interpret a null‐space method as a matrix factorization. We review these findings, highlight links between them, and bring them into a unified framework. We also investigate the suitability of using null‐space factorizations to derive sparse direct methods and present numerical results for both practical and academic problems.     

The Poisson aggregation process

In this paper we introduce and analyze the Poisson Aggregation Process (PAP): a stochastic model in which a random collection of random balls is stacked over a general metric space. The scattering of the balls’ centers follows a general Poisson process over the metric space, and the balls’ radii are independent and identically distributed random variables governed by a general distribution. For each point of the metric space, the PAP counts the number of balls that are stacked over it. The PAP model is a highly versatile spatial counterpart of the temporal M/G/∞ model in queueing theory. The surface of the moon, scarred by circular meteor-impact craters, exemplifies the PAP model in two dimensions: the PAP counts the number of meteor-impacts that any given moon-surface point sustained. A comprehensive analysis of the PAP is presented, and the closed-form results established include: general statistics, stationary statistics, short-range and long-range dependencies, a Central Limit Theorem, an Extreme Limit Theorem, and fractality.     

An algebraic multigrid method with interpolation reproducing rigid body modes for semi-definite problems in two-dimensional linear elasticity

Based on the geometric grid information as geometric coordinates, an algebraic multigrid (AMG) method with the interpolation reproducing the rigid body modes (namely the kernel elements of semi-definite operator arising from linear elasticity) is constructed, and such method is applied to the linear elasticity problems with a traction free boundary condition and crystal problems with free boundary conditions as well. The results of various numerical experiments in two dimensions are presented. It is shown from the numerical results that the constructed AMG method is robust and efficient for such semi-definite problems, and the convergence is uniformly bounded away from one independent of the problem size. Furthermore, the AMG method proposed in this paper has better convergence rate than the commonly used AMG methods. Simultaneously, an AMG method that can preserve the quotient space, which means that if the exact solution of original problem belongs to the quotient space of discrete operator considered, then the numerical solution of AMG method is convergent in the same quotient space, is obtained using the technique of orthogonal decomposition.     

Size of the jump and behavior of the absolute maximum for processes with independent increments

For a process with independent increments and negative mean one investigates the asymptotic behavior of the distribution of the absolute maximum and the size of the jump over a positive level. Necessary and sufficient conditions for the existence of a proper distribution of the size of a jump over an infinite level are found.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 4, pp. 451–458, April, 1990.     

A Staged Continuous Tabu Search Algorithm for the Global Optimization and its Applications to the Design of Fiber Bragg Gratings

A novel staged continuous Tabu search (SCTS) algorithm is proposed for solving global optimization problems of multi-minima functions with multi-variables. The proposed method comprises three stages that are based on the continuous Tabu search (CTS) algorithm with different neighbor-search strategies, with each devoting to one task. The method searches for the global optimum thoroughly and efficiently over the space of solutions compared to a single process of CTS. The effectiveness of the proposed SCTS algorithm is evaluated using a set of benchmark multimodal functions whose global and local minima are known. The numerical test results obtained indicate that the proposed method is more efficient than an improved genetic algorithm published previously. The method is also applied to the optimization of fiber grating design for optical communication systems. Compared with two other well-known algorithms, namely, genetic algorithm (GA) and simulated annealing (SA), the proposed method performs better in the optimization of the fiber grating design.