On the Convergence of a Population-Based Global Optimization Algorithm

In global optimization, a typical population-based stochastic search method works on a set of sample points from the feasible region. In this paper, we study a recently proposed method of this sort. The method utilizes an attraction-repulsion mechanism to move sample points toward optimality and is thus referred to as electromagnetism-like method (EM). The computational results showed that EM is robust in practice, so we further investigate the theoretical structure. After reviewing the original method, we present some necessary modifications for the convergence proof. We show that in the limit, the modified method converges to the vicinity of global optimum with probability one.     

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.     

A computational study on different penalty approaches for solving constrained global optimization problems with the electromagnetism-like method

In this article, the application of the electromagnetism-like method (EM) for solving constrained optimization problems is investigated. A number of penalty functions have been tested with EM in this investigation, and their merits and demerits have been discussed. We have also provided motivations for such an investigation. Finally, we have compared EM with two recent global optimization algorithms from the literature. We have shown that EM is a suitable alternative to these methods and that it has a role to play in solving constrained global optimization problems.     

A hybrid metaheuristic approach to the university course timetabling problem

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.     

Almost sure exponential stability of backward Euler-Maruyama discretizations for hybrid stochastic differential equations

This is a continuation of the first author’s earlier paper [1] jointly with Pang and Deng, in which the authors established some sufficient conditions under which the Euler-Maruyama (EM) method can reproduce the almost sure exponential stability of the test hybrid SDEs. The key condition imposed in [1] is the global Lipschitz condition. However, we will show in this paper that without this global Lipschitz condition the EM method may not preserve the almost sure exponential stability. We will then show that the backward EM method can capture the almost sure exponential stability for a certain class of highly nonlinear hybrid SDEs.     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

Space alternating penalized Kullback proximal point algorithms for maximizing likelihood with nondifferentiable penalty

The EM algorithm is a widely used methodology for penalized likelihood estimation. Provable monotonicity and convergence are the hallmarks of the EM algorithm and these properties are well established for smooth likelihood and smooth penalty functions. However, many relaxed versions of variable selection penalties are not smooth. In this paper, we introduce a new class of space alternating penalized Kullback proximal extensions of the EM algorithm for nonsmooth likelihood inference. We show that the cluster points of the new method are stationary points even when they lie on the boundary of the parameter set. We illustrate the new class of algorithms for the problems of model selection for finite mixtures of regression and of sparse image reconstruction.     

A novel hybrid approach combining electromagnetism-like method with Solis and Wets local search for continuous optimization problems

The electromagnetism-like method (EM) is a meta-heuristic algorithm utilizing an attraction-repulsion mechanism to move sample points towards optimality in continuous optimization problems. Traditionally, the EM uses two algorithms known as the original and revised EMs. This paper presents a novel hybrid approach for EM by employing a well-known local search, called Solis and Wets. To show the performance of our proposed hybrid EM, a number of experiments are carried out on a set of well-known test problems and the related results are compared with two forgoing algorithms.     

罚函数与带不等式约束的总极值问题

设f(x)是n维欧氏空间R~n中有界闻区域G上的连续函数,考虑下列带不等式约束的函数极小问题: 求f(x)在G上的总极小,并满足约束x∈S,     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

带跳随机微分方程的Euler-Maruyama方法的几乎处处指数稳定性和矩稳定性

本文首先研究了一维带跳随机微分方程的指数稳定性,并证明Euler-Maruyama(EM)方法保持了解析解的稳定性.其次,研究了多维带跳随机微分方程的稳定性,证明若系数满足全局Lipchitz条件,则EM方法能够很好地保持解析解的几乎处处指数稳定性、均方指数稳定性.最后,给出算例来支持所得结论的正确性.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

Stochastic mathematical programs with equilibrium constraints,modelling and sample average approximation

In this article, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate the structure of both–the lower level equilibrium solution and objective integrand. We show almost sure convergence of optimal values, optimal solutions (both local and global) and generalized Karush–Kuhn–Tucker points of the SAA program to their true counterparts. We also study uniform exponential convergence of the sample average approximations, and as a consequence derive estimates of the sample size required to solve the true problem with a given accuracy. Finally, we present some preliminary numerical test results.     

Implementations of the Monte Carlo EM Algorithm

The Monte Carlo EM (MCEM) algorithm is a modification of the EM algorithm where the expectation in the E-step is computed numerically through Monte Carlo simulations. The most exible and generally applicable approach to obtaining a Monte Carlo sample in each iteration of an MCEM algorithm is through Markov chain Monte Carlo (MCMC) routines such as the Gibbs and Metropolis–Hastings samplers. Although MCMC estimation presents a tractable solution to problems where the E-step is not available in closed form, two issues arise when implementing this MCEM routine: (1) how do we minimize the computational cost in obtaining an MCMC sample? and (2) how do we choose the Monte Carlo sample size? We address the first question through an application of importance sampling whereby samples drawn during previous EM iterations are recycled rather than running an MCMC sampler each MCEM iteration. The second question is addressed through an application of regenerative simulation. We obtain approximate independent and identical samples by subsampling the generated MCMC sample during different renewal periods. Standard central limit theorems may thus be used to gauge Monte Carlo error. In particular, we apply an automated rule for increasing the Monte Carlo sample size when the Monte Carlo error overwhelms the EM estimate at any given iteration. We illustrate our MCEM algorithm through analyses of two datasets fit by generalized linear mixed models. As a part of these applications, we demonstrate the improvement in computational cost and efficiency of our routine over alternative MCEM strategies.     

Simple linkage: Analysis of a threshold-accepting global optimization method

In a recent paper the authors introduced an infinite class of global optimization algorithms based upon random sampling from the feasible region and local searches started from selected sample points, based upon an acceptance/rejection criterion. All of the algorithms of that class possess strong theoretical properties.Here we analyze a member of that family, which, although being significantly simpler to implement and more efficient than the well known Multi-Level Single-Linkage algorithm, enjoys the same theoretical properties. It is shown here that, with very high probability, our method is able to discover from which points Multi-Level Single-Linkage will decide to start local search.     

Testing the topographical global initialization strategy in the framework of an unconstrained optimization method

In general, classical iterative algorithms for optimization, such as Newton-type methods, perform only local search around a given starting point. Such feature is an impediment to the direct use of these methods to global optimization problems, when good starting points are not available. To overcome this problem, in this work we equipped a Newton-type method with the topographical global initialization strategy, which was employed together with a new formula for its key parameter. The used local search algorithm is a quasi-Newton method with backtracking. In this approach, users provide initial sets, instead of starting points. Then, using points sampled in such initial sets (merely boxes in \({\mathbb {R}}^{n}\)), the topographical method selects appropriate initial guesses for global optimization tasks. Computational experiments were performed using 33 test problems available in literature. Comparisons against three specialized methods (DIRECT, MCS and GLODS) have shown that the present methodology is a powerful tool for unconstrained global optimization.     

周期数据时段划分的双截断高斯混合模型及其EM算法

有限混合模型是多模态数据拟合和聚类的有力工具,本文针对具有多模态的周期数据提出了双截断高斯混合糢型,并推导出相应的EM算法,再通过BIC准則确定混合成分个数,该方法的优点是可以将相邻周期上距离较近的数据聚为一类.模拟研究显示,在具体参数设置下,EM算法和BIC准则是相合的。最后,该方法应用于车流量数据的时段划分,将一天划分为具有显著特征的6个时段,有助于交通部门采取相应策略,为优化交通灯信号配时提供参考依据.     

Online EM Algorithm for Hidden Markov Models

Online (also called “recursive” or “adaptive”) estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modeling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maximization (EM) methodology, consists in reparameterizing the problem using complete-data sufficient statistics. The second ingredient consists in exploiting a purely recursive form of smoothing in HMMs based on an auxiliary recursion. Although the proposed online EM algorithm resembles a classical stochastic approximation (or Robbins–Monro) algorithm, it is sufficiently different to resist conventional analysis of convergence. We thus provide limited results which identify the potential limiting points of the recursion as well as the large-sample behavior of the quantities involved in the algorithm. The performance of the proposed algorithm is numerically evaluated through simulations in the case of a noisily observed Markov chain. In this case, the algorithm reaches estimation results that are comparable to those of the maximum likelihood estimator for large sample sizes. The supplemental material for this article available online includes an appendix with the proofs of Theorem 1 and Corollary 1 stated in Section 4 as well as the MATLAB/OCTAVE code used to implement the algorithm in the case of a noisily observed Markov chain considered in Section 5.     

A NEW SQP-FILTER METHOD PROGRAMMING FOR SOLVING NONLINEAR PROBLEMS

In [4], Fletcher and Leyffer present a new method that solves nonlinear programming problems without a penalty function by SQP-Filter algorithm. It has attracted much attention due to its good numerical results. In this paper we propose a new SQP-Filter method which can overcome Maratos effect more effectively. We give stricter acceptant criteria when the iterative points are far from the optimal points and looser ones vice-versa. About this new method, the proof of global convergence is also presented under standard assumptions. Numerical results show that our method is efficient.