Adaptive Rejection Metropolis Simulated Annealing for Detecting Global Maximum Regions

A finite mixture model has been used to fit the data from heterogeneous populations to many applications. An Expectation Maximization (EM) algorithm is the most popular method to estimate parameters in a finite mixture model. A Bayesian approach is another method for fitting a mixture model. However, the EM algorithm often converges to the local maximum regions, and it is sensitive to the choice of starting points. In the Bayesian approach, the Markov Chain Monte Carlo (MCMC) sometimes converges to the local mode and is difficult to move to another mode. Hence, in this paper we propose a new method to improve the limitation of EM algorithm so that the EM can estimate the parameters at the global maximum region and to develop a more effective Bayesian approach so that the MCMC chain moves from one mode to another more easily in the mixture model. Our approach is developed by using both simulated annealing (SA) and adaptive rejection metropolis sampling (ARMS). Although SA is a well-known approach for detecting distinct modes, the limitation of SA is the difficulty in choosing sequences of proper proposal distributions for a target distribution. Since ARMS uses a piecewise linear envelope function for a proposal distribution, we incorporate ARMS into an SA approach so that we can start a more proper proposal distribution and detect separate modes. As a result, we can detect the maximum region and estimate parameters for this global region. We refer to this approach as ARMS annealing. By putting together ARMS annealing with the EM algorithm and with the Bayesian approach, respectively, we have proposed two approaches: an EM-ARMS annealing algorithm and a Bayesian-ARMS annealing approach. We compare our two approaches with traditional EM algorithm alone and Bayesian approach alone using simulation, showing that our two approaches are comparable to each other but perform better than EM algorithm alone and Bayesian approach alone. Our two approaches detect the global maximum region well and estimate the parameters in this region. We demonstrate the advantage of our approaches using an example of the mixture of two Poisson regression models. This mixture model is used to analyze a survey data on the number of charitable donations.     

Adaptive Markov Chain Monte Carlo for Bayesian Variable Selection

We describe adaptive Markov chain Monte Carlo (MCMC) methods for sampling posterior distributions arising from Bayesian variable selection problems. Point-mass mixture priors are commonly used in Bayesian variable selection problems in regression. However, for generalized linear and nonlinear models where the conditional densities cannot be obtained directly, the resulting mixture posterior may be difficult to sample using standard MCMC methods due to multimodality. We introduce an adaptive MCMC scheme that automatically tunes the parameters of a family of mixture proposal distributions during simulation. The resulting chain adapts to sample efficiently from multimodal target distributions. For variable selection problems point-mass components are included in the mixture, and the associated weights adapt to approximate marginal posterior variable inclusion probabilities, while the remaining components approximate the posterior over nonzero values. The resulting sampler transitions efficiently between models, performing parameter estimation and variable selection simultaneously. Ergodicity and convergence are guaranteed by limiting the adaptation based on recent theoretical results. The algorithm is demonstrated on a logistic regression model, a sparse kernel regression, and a random field model from statistical biophysics; in each case the adaptive algorithm dramatically outperforms traditional MH algorithms. Supplementary materials for this article are available online.     

Automatically tuned general-purpose MCMC via new adaptive diagnostics

Adaptive Markov Chain Monte Carlo (MCMC) algorithms attempt to ‘learn’ from the results of past iterations so the Markov chain can converge quicker. Unfortunately, adaptive MCMC algorithms are no longer Markovian, so their convergence is difficult to guarantee. In this paper, we develop new diagnostics to determine whether the adaption is still improving the convergence. We present an algorithm which automatically stops adapting once it determines further adaption will not increase the convergence speed. Our algorithm allows the computer to tune a ‘good’ Markov chain through multiple phases of adaption, and then run conventional non-adaptive MCMC. In this way, the efficiency gains of adaptive MCMC can be obtained while still ensuring convergence to the target distribution.     

Efficient Adaptive MCMC Through Precision Estimation

The performance of Markov chain Monte Carlo (MCMC) algorithms like the Metropolis Hastings Random Walk (MHRW) is highly dependent on the choice of scaling matrix for the proposal distributions. A popular choice of scaling matrix in adaptive MCMC methods is to use the empirical covariance matrix (ECM) of previous samples. However, this choice is problematic if the dimension of the target distribution is large, since the ECM then converges slowly and is computationally expensive to use. We propose two algorithms to improve convergence and decrease computational cost of adaptive MCMC methods in cases when the precision (inverse covariance) matrix of the target density can be well-approximated by a sparse matrix. The first is an algorithm for online estimation of the Cholesky factor of a sparse precision matrix. The second estimates the sparsity structure of the precision matrix. Combining the two algorithms allows us to construct precision-based adaptive MCMC algorithms that can be used as black-box methods for densities with unknown dependency structures. We construct precision-based versions of the adaptive MHRW and the adaptive Metropolis adjusted Langevin algorithm and demonstrate the performance of the methods in two examples. Supplementary materials for this article are available online.     

A hybrid approach for single-machine tardiness problems with sequence-dependent setup times

Scheduling problems in real systems often require sequence-dependent setup times. The topic of sequence-dependent setup times has not been addressed adequately, and improved competitiveness is thus not achieved. This study proposes a hybrid approach that takes advantage of simulated annealing (SA) and tabu search (TS) to solve single-machine tardiness problems with sequence-dependent setup times. To verify the proposed approach, experiments were conducted on benchmark problem sets that included both the weighted and un-weighted tardiness problems. The results show that the performance of the hybrid approach is superior to that of the SA, genetic algorithm, TS and ant colony optimization approaches, and is comparable with the Tabu-VNS approach. And the proposed approach found new upper bound values for many benchmark problems with an acceptable computational time.     

The Generalized Multiset Sampler

The multiset sampler, an MCMC algorithm recently proposed by Leman and coauthors, is an easy-to-implement algorithm which is especially well-suited to drawing samples from a multimodal distribution. We generalize the algorithm by redefining the multiset sampler with an explicit link between target distribution and sampling distribution. The generalized formulation replaces the multiset with a K-tuple, which allows us to use the algorithm on unbounded parameter spaces, improves estimation, and sets up further extensions to adaptive MCMC techniques. Theoretical properties of the algorithm are provided and guidance is given on its implementation. Examples, both simulated and real, confirm that the generalized multiset sampler provides a simple, general and effective approach to sampling from multimodal distributions. Supplementary materials for this article are available online.     

Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using this measure. S²A uses a fixed cooling schedule during the algorithm execution. Though S²A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper.     

On Markov Chain Monte Carlo Acceleration

Abstract

Markov chain Monte Carlo (MCMC) methods are currently enjoying a surge of interest within the statistical community. The goal of this work is to formalize and support two distinct adaptive strategies that typically accelerate the convergence of an MCMC algorithm. One approach is through resampling; the other incorporates adaptive switching of the transition kernel. Support is both by analytic arguments and simulation study. Application is envisioned in low-dimensional but nontrivial problems. Two pathological illustrations are presented. Connections with reparameterization are discussed as well as possible difficulties with infinitely often adaptation.     

Bayesian variable selection in generalized linear models using a combination of stochastic optimization methods

In this paper the usage of a stochastic optimization algorithm as a model search tool is proposed for the Bayesian variable selection problem in generalized linear models. Combining aspects of three well known stochastic optimization algorithms, namely, simulated annealing, genetic algorithm and tabu search, a powerful model search algorithm is produced. After choosing suitable priors, the posterior model probability is used as a criterion function for the algorithm; in cases when it is not analytically tractable Laplace approximation is used. The proposed algorithm is illustrated on normal linear and logistic regression models, for simulated and real-life examples, and it is shown that, with a very low computational cost, it achieves improved performance when compared with popular MCMC algorithms, such as the MCMC model composition, as well as with “vanilla” versions of simulated annealing, genetic algorithm and tabu search.     

On the stability and ergodicity of adaptive scaling Metropolis algorithms

The stability and ergodicity properties of two adaptive random walk Metropolis algorithms are considered. Both algorithms adjust the scaling of the proposal distribution continuously based on the observed acceptance probability. Unlike the previously proposed forms of the algorithms, the adapted scaling parameter is not constrained within a predefined compact interval. The first algorithm is based on scale adaptation only, while the second one also incorporates covariance adaptation. A strong law of large numbers is shown to hold assuming that the target density is smooth enough and has either compact support or super-exponentially decaying tails.     

Parallelizing simulated annealing algorithms based on high-performance computer

We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance computers and applied them to a set of standard function optimization problems in order to test their performances. According to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely, parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great time cost if the random search space was considerably expanded. The most effective way we found in identifying the global optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success rate and solution quality.     

An adaptive tabu-simulated annealing for concave cost transportation problems

The transportation problem (TP) is one of the most popular network problems because of its theoretical and practical importance. If the transportation cost linearly depends on the transported amount of the product, then TP is solvable in polynomial time with linear programming methods. However, in the real world, the transportation costs are generally nonlinear, frequently concave where the unit cost for transporting products decreases as the amount of products increases. Since concave cost transportation problems (ccTPs) are NP-hard, solving large-scale problems is time consuming. In this study, we propose a hybrid algorithm based on the concepts borrowed from tabu search (TS) and simulated annealing (SA) to solve the ccTP. This algorithm, called ATSA (adaptive tabu-simulated annealing), is an SA approach supplemented with a tabu list and adaptive cooling strategy. The effectiveness of ATSA has been investigated in two stages using a set of TPs with different sizes. The first stage includes performance analysis of ATSA using SA, ASA (adaptive simulated anealing) and TS, which are basic forms of ATSA. In the second stage, ATSA has been compared with the heuristic approaches given in the literature for ccTP. Statistical analysis shows that ATSA exhibits better performance than its basic forms and heuristic approaches.     

Optimality criteria coupled adaptive mesh method for optimal shape design of Stokes flow

An adaptive mesh method combined with the optimality criteria algorithm is applied to optimal shape design problems of fluid dynamics. The shape sensitivity analysis of the cost functional is derived. The optimization problem is solved by a simple but robust optimality criteria algorithm, and an automatic local adaptive mesh refinement method is proposed. The mesh adaptation, with an indicator based on the material distribution information, is itself shown as a shape or topology optimization problem. Taking advantages of this algorithm, the optimal shape design problem concerning fluid flow can be solved with higher resolution of the interface and a minimum of additional expense. Details on the optimization procedure are provided. Numerical results for two benchmark topology optimization problems are provided and compared with those obtained by other methods. Copyright © 2016 John Wiley & Sons, Ltd.     

Adaptive Component-Wise Multiple-Try Metropolis Sampling

One of the most widely used samplers in practice is the component-wise Metropolis–Hastings (CMH) sampler that updates in turn the components of a vector-valued Markov chain using accept–reject moves generated from a proposal distribution. When the target distribution of a Markov chain is irregularly shaped, a “good” proposal distribution for one region of the state–space might be a “poor” one for another region. We consider a component-wise multiple-try Metropolis (CMTM) algorithm that chooses from a set of candidate moves sampled from different distributions. The computational efficiency is increased using an adaptation rule for the CMTM algorithm that dynamically builds a better set of proposal distributions as the Markov chain runs. The ergodicity of the adaptive chain is demonstrated theoretically. The performance is studied via simulations and real data examples. Supplementary material for this article is available online.     

A hybrid glowworm swarm optimization algorithm to solve constrained multimodal functions optimization

In this paper, a novel hybrid glowworm swarm optimization (HGSO) algorithm is proposed. The HGSO algorithm embeds predatory behaviour of artificial fish swarm algorithm (AFSA) into glowworm swarm optimization (GSO) algorithm and combines the GSO with differential evolution on the basis of a two-population co-evolution mechanism. In addition, to overcome the premature convergence, the local search strategy based on simulated annealing is applied to make the search of GSO approach the true optimum solution gradually. Finally, several benchmark functions show that HGSO has faster convergence efficiency and higher computational precision, and is more effective for solving constrained multi-modal function optimization problems.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

A robust parameter design for multi-response problems

Most real world search and optimization problems naturally involve multiple responses. In this paper we investigate a multiple response problem within desirability function framework and try to determine values of input variables that achieve a target value for each response through three meta-heuristic algorithms such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Each algorithm has some parameters that need to be accurately calibrated to ensure the best performance. For this purpose, a robust calibration is applied to the parameters by means of Taguchi method. The computational results of these three algorithms are compared against each others. The superior performance of SA over TS and TS over GA is inferred from the obtained results in various situations.     

Nonmonotone adaptive trust region method

In this paper, we propose a nonmonotone adaptive trust region method for unconstrained optimization problems. This method can produce an adaptive trust region radius automatically at each iteration and allow the functional value of iterates to increase within finite iterations and finally decrease after such finite iterations. This nonmonotone approach and adaptive trust region radius can reduce the number of solving trust region subproblems when reaching the same precision. The global convergence and convergence rate of this method are analyzed under some mild conditions. Numerical results show that the proposed method is effective in practical computation.     

Chaotic annealing with hypothesis test for function optimization in noisy environments

As a special mechanism to avoid being trapped in local minimum, the ergodicity property of chaos has been used as a novel searching technique for optimization problems, but there is no research work on chaos for optimization in noisy environments. In this paper, the performance of chaotic annealing (CA) for uncertain function optimization is investigated, and a new hybrid approach (namely CAHT) that combines CA and hypothesis test (HT) is proposed. In CAHT, the merits of CA are applied for well exploration and exploitation in searching space, and solution quality can be identified reliably by hypothesis test to reduce the repeated search to some extent and to reasonably estimate performance for solution. Simulation results and comparisons show that, chaos is helpful to improve the performance of SA for uncertain function optimization, and CAHT can further improve the searching efficiency, quality and robustness.     

Adaptive computation of smallest eigenvalues of self‐adjoint elliptic partial differential equations

We consider a new adaptive finite element (AFEM) algorithm for self‐adjoint elliptic PDE eigenvalue problems. In contrast to other approaches we incorporate the inexact solutions of the resulting finite‐dimensional algebraic eigenvalue problems into the adaptation process. In this way we can balance the costs of the adaptive refinement of the mesh with the costs for the iterative eigenvalue method. We present error estimates that incorporate the discretization errors, approximation errors in the eigenvalue solver and roundoff errors, and use these for the adaptation process. We show that it is also possible to restrict to very few iterations of a Krylov subspace solver for the eigenvalue problem on coarse meshes. Several examples are presented to show that this new approach achieves much better complexity than the previous AFEM approaches which assume that the algebraic eigenvalue problem is solved to full accuracy. Copyright © 2010 John Wiley & Sons, Ltd.