A Stochastic Approach to General Nonlinear Programming Problems

Nonlinear programming problem is the general case of mathematical programming problem such that both the objective and constraint functions are nonlinear and is the most difficult case of smooth optimization problem to solve. In this article, we suggest a stochastic search method to general nonlinear programming problems which is not an iterative algorithm but it is an interior point method. The proposed method finds the near-optimal solution to the problem. The results of a few numerical studies are reported. The efficiency of the new method is compared and is found to be reasonable.     

Stochastic adaptation of importance sampler

Improving efficiency of the importance sampler is at the centre of research on Monte Carlo methods. While the adaptive approach is usually not so straightforward within the Markov chain Monte Carlo framework, the counterpart in importance sampling can be justified and validated easily. We propose an iterative adaptation method for learning the proposal distribution of an importance sampler based on stochastic approximation. The stochastic approximation method can recruit general iterative optimization techniques like the minorization–maximization algorithm. The effectiveness of the approach in optimizing the Kullback divergence between the proposal distribution and the target is demonstrated using several examples.     

A stochastic approximation algorithm for maximum-likelihood estimation with incomplete data

We propose a new stochastic approximation (SA) algorithm for maximum-likelihood estimation (MLE) in the incomplete-data setting. This algorithm is most useful for problems when the EM algorithm is not possible due to an intractable E-step or M-step. Compared to other algorithm that have been proposed for intractable EM problems, such as the MCEM algorithm of Wei and Tanner (1990), our proposed algorithm appears more generally applicable and efficient. The approach we adopt is inspired by the Robbins-Monro (1951) stochastic approximation procedure, and we show that the proposed algorithm can be used to solve some of the long-standing problems in computing an MLE with incomplete data. We prove that in general O(n) simulation steps are required in computing the MLE with the SA algorithm and O(n log n) simulation steps are required in computing the MLE using the MCEM and/or the MCNR algorithm, where n is the sample size of the observations. Examples include computing the MLE in the nonlinear error-in-variable model and nonlinear regression model with random effects.     

Stochastic EM algorithm of a finite mixture model from hurdle Poisson distribution with missing responses

ABSTRACT

In this article, a finite mixture model of hurdle Poisson distribution with missing outcomes is proposed, and a stochastic EM algorithm is developed for obtaining the maximum likelihood estimates of model parameters and mixing proportions. Specifically, missing data is assumed to be missing not at random (MNAR)/non ignorable missing (NINR) and the corresponding missingness mechanism is modeled through probit regression. To improve the algorithm efficiency, a stochastic step is incorporated into the E-step based on data augmentation, whereas the M-step is solved by the method of conditional maximization. A variation on Bayesian information criterion (BIC) is also proposed to compare models with different number of components with missing values. The considered model is a general model framework and it captures the important characteristics of count data analysis such as zero inflation/deflation, heterogeneity as well as missingness, providing us with more insight into the data feature and allowing for dispersion to be investigated more fully and correctly. Since the stochastic step only involves simulating samples from some standard distributions, the computational burden is alleviated. Once missing responses and latent variables are imputed to replace the conditional expectation, our approach works as part of a multiple imputation procedure. A simulation study and a real example illustrate the usefulness and effectiveness of our methodology.     

An economical acceptance–rejection algorithm for uniform random variate generation over constrained simplexes

This paper develops an algorithm for uniform random generation over a constrained simplex, which is the intersection of a standard simplex and a given set. Uniform sampling from constrained simplexes has numerous applications in different fields, such as portfolio optimization, stochastic multi-criteria decision analysis, experimental design with mixtures and decision problems involving discrete joint distributions with imprecise probabilities. The proposed algorithm is developed by combining the acceptance–rejection and conditional methods along with the use of optimization tools. The acceptance rate of the algorithm is analytically compared to that of a crude acceptance–rejection algorithm, which generates points over the simplex and then rejects any points falling outside the intersecting set. Finally, using convex optimization, the setup phase of the algorithm is detailed for the special cases where the intersecting set is a general convex set, a convex set defined by a finite number of convex constraints or a polyhedron.     

An Optimal Reliability and Maintainability Design of a Searching System

In this article, we deal with an optimal reliability and maintainability design problem of a searching system with complex structures. The system availability and life cycle cost are used as optimization criteria and estimated by simulation. We want to determine MTBF (Mean Time between Failures) and MTTR (Mean Time to Repair) for all components and ALDT (Administrative and Logistics Delay Times) of the searching system in order to minimize the life cycle cost and to satisfy the target system availability. A hybrid genetic algorithm with a heuristic method is proposed to find near-optimal solutions and compared with a general genetic algorithm.     

Genetic algorithms for numerical optimization

Genetic algorithms (GAs) are stochastic adaptive algorithms whose search method is based on simulation of natural genetic inheritance and Darwinian striving for survival. They can be used to find approximate solutions to numerical optimization problems in cases where finding the exact optimum is prohibitively expensive, or where no algorithm is known. However, such applications can encounter problems that sometimes delay, if not prevent, finding the optimal solutions with desired precision. In this paper we describe applications of GAs to numerical optimization, present three novel ways to handle such problems, and give some experimental results.     

A statistical multivariable optimization method using improved orthogonal algorithm based on large data

Multivariable optimization under large data environment concerns with how to reliably obtain a set of optimization results from a mass of data that influence the object function complexly. This is an important issue in statistical calculation because the complexity between variable parameters leads to repeated statistical calculation analysis and a significant amount of data waste. A statistical multivariable optimization method using improved orthogonal algorithm based on large data is proposed. Considering the optimization problem with multi-parameters under large data environment, a multi-parameter optimization model used for improved orthogonal algorithm is established based on large data. Furthermore, an extensive simulation study on temperature field distribution of anti-/de-icing component was conducted to verify the validity of the statistical calculation analysis optimization method. The optimized temperature field distribution meets the anti-/de-icing requirements through numerical simulation. Simulation results show that the optimization effect is more evident and accurate than the non-optimized temperature distribution with the optimized results of the proposed method. Results verify the effectiveness of the proposed method.     

Simulation-Based Inspection Policies for a One-Shot System in Storage Over a Finite Time Span

In this paper, we consider an inspection policy problem for a one-shot system with two types of units over a finite time span and want to determine inspection intervals optimally with given replacement points of Type 2 units. The interval availability and life cycle cost are used as optimization criteria and estimated by simulation. Two optimization models are proposed to find the optimal inspection intervals for the exponential and general distributions. A heuristic method and a genetic algorithm are proposed to find the near-optimal inspection intervals, to satisfy the target interval availability and minimize the life-cycle cost. We study numerical examples to compare the heuristic method with the genetic algorithm and investigate the effect of model parameters to the optimal solutions.     

Estimation in multiple linear regression Berkson model for processes with uncorrelated increments

This paper presents a method of estimating the regression and variance parameters in the multiple linear regression Berkson model for a continuous-time stochastic process with uncorrelated increments. Under minimal conditions, we establish (i) the Gauss–Markov theorem and the quadratic mean—as well as the strong consistency of the proposed estimate of the regression parameter and (ii) the weak consistency of the proposed estimate of the variance parameter.     

Annealing evolutionary stochastic approximation Monte Carlo for global optimization

In this paper, we propose a new algorithm, the so-called annealing evolutionary stochastic approximation Monte Carlo (AESAMC) algorithm as a general optimization technique, and study its convergence. AESAMC possesses a self-adjusting mechanism, whose target distribution can be adapted at each iteration according to the current samples. Thus, AESAMC falls into the class of adaptive Monte Carlo methods. This mechanism also makes AESAMC less trapped by local energy minima than nonadaptive MCMC algorithms. Under mild conditions, we show that AESAMC can converge weakly toward a neighboring set of global minima in the space of energy. AESAMC is tested on multiple optimization problems. The numerical results indicate that AESAMC can potentially outperform simulated annealing, the genetic algorithm, annealing stochastic approximation Monte Carlo, and some other metaheuristics in function optimization.     

A lower bound based smoothed quasi-Newton algorithm for group bridge penalized regression

In this paper, we propose a lower bound based smoothed quasi-Newton algorithm for computing the solution paths of the group bridge estimator in linear regression models. Our method is based on the quasi-Newton algorithm with a smoothed group bridge penalty in combination with a novel data-driven thresholding rule for the regression coefficients. This rule is derived based on a necessary KKT condition of the group bridge optimization problem. It is easy to implement and can be used to eliminate groups with zero coefficients. Thus, it reduces the dimension of the optimization problem. The proposed algorithm removes the restriction of groupwise orthogonal condition needed in coordinate descent and LARS algorithms for group variable selection. Numerical results show that the proposed algorithm outperforms the coordinate descent based algorithms in both efficiency and accuracy.     

A new metamodel-based method for solving semi-expensive simulation optimization problems

In this article, a new algorithm for rather expensive simulation problems is presented, which consists of two phases. In the first phase, as a model-based algorithm, the simulation output is used directly in the optimization stage. In the second phase, the simulation model is replaced by a valid metamodel. In addition, a new optimization algorithm is presented. To evaluate the performance of the proposed algorithm, it is applied to the (s,S) inventory problem as well as to five test functions. Numerical results show that the proposed algorithm leads to better solutions with less computational time than the corresponding metamodel-based algorithm.     

Analysis of generalized linear mixed models via a stochastic approximation algorithm with Markov chain Monte-Carlo method

In recent years much effort has been devoted to maximum likelihood estimation of generalized linear mixed models. Most of the existing methods use the EM algorithm, with various techniques in handling the intractable E-step. In this paper, a new implementation of a stochastic approximation algorithm with Markov chain Monte Carlo method is investigated. The proposed algorithm is computationally straightforward and its convergence is guaranteed. A simulation and three real data sets, including the challenging salamander data, are used to illustrate the procedure and to compare it with some existing methods. The results indicate that the proposed algorithm is an attractive alternative for problems with a large number of random effects or with high dimensional intractable integrals in the likelihood function.     

Estimation of Wood Fibre Length Distributions from Censored Data through an EM Algorithm

Abstract.  An expectation maximization (EM) algorithm is proposed to find fibre length distributions in standing trees. The available data come from cylindric wood samples (increment cores). The sample contains uncut fibres as well as fibres cut once or twice. The sample contains not only fibres, but also other cells, the so-called 'fines'. The lengths are measured by an automatic fibre-analyser, which is not able to distinguish fines from fibres and cannot tell if a cell has been cut. The data thus come from a censored version of a mixture of the fine and fibre length distributions in the tree. The parameters of the length distributions are estimated by a stochastic version of the EM algorithm, and an estimate of the corresponding covariance matrix is derived. The method is applied to data from northern Sweden. A simulation study is also presented. The method works well for sample sizes commonly obtained from increment cores.     

An alternative algorithm of the empirical likelihood estimation for the parameter of a linear regression model

ABSTRACT

Empirical likelihood (EL) is a nonparametric method based on observations. EL method is defined as a constrained optimization problem. The solution of this constrained optimization problem is carried on using duality approach. In this study, we propose an alternative algorithm to solve this constrained optimization problem. The new algorithm is based on a newton-type algorithm for Lagrange multipliers for the constrained optimization problem. We provide a simulation study and a real data example to compare the performance of the proposed algorithm with the classical algorithm. Simulation and the real data results show that the performance of the proposed algorithm is comparable with the performance of the existing algorithm in terms of efficiencies and cpu-times.     

Partitioned algorithms for maximum likelihood and other non-linear estimation

There are a variety of methods in the literature which seek to make iterative estimation algorithms more manageable by breaking the iterations into a greater number of simpler or faster steps. Those algorithms which deal at each step with a proper subset of the parameters are called in this paper partitioned algorithms. Partitioned algorithms in effect replace the original estimation problem with a series of problems of lower dimension. The purpose of the paper is to characterize some of the circumstances under which this process of dimension reduction leads to significant benefits.Four types of partitioned algorithms are distinguished: reduced objective function methods, nested (partial Gauss-Seidel) iterations, zigzag (full Gauss-Seidel) iterations, and leapfrog (non-simultaneous) iterations. Emphasis is given to Newton-type methods using analytic derivatives, but a nested EM algorithm is also given. Nested Newton methods are shown to be equivalent to applying to same Newton method to the reduced objective function, and are applied to separable regression and generalized linear models. Nesting is shown generally to improve the convergence of Newton-type methods, both by improving the quadratic approximation to the log-likelihood and by improving the accuracy with which the observed information matrix can be approximated. Nesting is recommended whenever a subset of parameters is relatively easily estimated. The zigzag method is shown to produce a stable but generally slow iteration; it is fast and recommended when the parameter subsets have approximately uncorrelated estimates. The leapfrog iteration has less guaranteed properties in general, but is similar to nesting and zigzagging when the parameter subsets are orthogonal.     

On learning strategies for evolutionary Monte Carlo

The real-parameter evolutionary Monte Carlo algorithm (EMC) has been proposed as an effective tool both for sampling from high-dimensional distributions and for stochastic optimization (Liang and Wong, 2001). EMC uses a temperature ladder similar to that in parallel tempering (PT; Geyer, 1991). In contrast with PT, EMC allows for crossover moves between parallel and tempered MCMC chains. In the context of EMC, we introduce four new moves, which enhance its efficiency as measured by the effective sample size. Secondly, we introduce a practical strategy for determining the temperature range and placing the temperatures in the ladder used in EMC and PT. Lastly, we prove the validity of the conditional sampling step of the snooker algorithm, a crossover move in EMC, which extends a result of Roberts and Gilks (1994).     

Implementing particle swarm optimization algorithm to estimate the mixture of two Weibull parameters with censored data

We present the maximum likelihood estimation (MLE) via particle swarm optimization (PSO) algorithm to estimate the mixture of two Weibull parameters with complete and multiple censored data. A simulation study is conducted to assess the performance of the MLE via PSO algorithm, quasi-Newton method and expectation-maximization (EM) algorithm for different parameter settings and sample sizes in both uncensored and censored cases. The simulation results showed that the PSO algorithm outperforms the quasi-Newton method and the EM algorithm in most cases regarding bias and root mean square errors. Two numerical examples are used to demonstrate the performance of our proposed method.     

基于多重尝试Metropolis算法的非线性DSGE模型贝叶斯推断

本文提出一种改进的多重尝试Metropolis算法,用于非线性动态随机一般均衡模型的贝叶斯参数估计和模型选择。多重尝试策略通过每次迭代抽取多个尝试点的方法来提高算法的混合速率,新方法中提出使用近似的方法提高计算速度,并通过接收概率调整偏差。数值实验表明新方法在相同的计算时间内具有更高的估计效率。最后,本文比较了具有不同货币政策设定的模型对中国经济数据的拟合效果,发现中国数据更加支持具有时变通胀目标的模型。