An adaptive simulated annealing algorithm for global optimization over continuous variables

A method is presented for attempting global minimization for a function of continuous variables subject to constraints. The method, calledAdaptive Simulated Annealing (ASA), is distinguished by the fact that the fixed temperature schedules and step generation routines that characterize other implementations are here replaced by heuristic-based methods that effectively eliminate the dependence of the algorithm's overall performance on user-specified control parameters. A parallelprocessing version of ASA that gives increased efficiency is presented and applied to two standard problems for illustration and comparison.This research was supported by the University Research Initiative of the U.S. Army Research Office.     

Stochastic techniques for global optimization: A survey of recent advances

In this paper stochastic algorithms for global optimization are reviewed. After a brief introduction on random-search techniques, a more detailed analysis is carried out on the application of simulated annealing to continuous global optimization. The aim of such an analysis is mainly that of presenting recent papers on the subject, which have received only scarce attention in the most recent published surveys. Finally a very brief presentation of clustering techniques is given.     

Stochastic optimization with averaging of trajectories

A recursive stochastic optimization procedure under dependent disturbances is studied. It is based on the Polyak-Ruppert algorithm with trajectory averaging. Almost sure convergence of the algorithm is proved as well as asymptotic normality of the delivered estimates. It is shown that the presented algorithm attains the highest possible asymptotic convergence rate for stochastic approximation algorithms     

Optimization algorithm with probabilistic estimation

In this paper, we present a stochastic optimization algorithm based on the idea of the gradient method which incorporates a new adaptive-precision technique. Because of this new technique, unlike recent methods, the proposed algorithm adaptively selects the precision without any need for prior knowledge on the speed of convergence of the generated sequence. With this new technique, the algorithm can avoid increasing the estimation precision unnecessarily, yet it retains its favorable convergence properties. In fact, it tries to maintain a nice balance between the requirements for computational accuracy and those for computational expediency. Furthermore, we present two types of convergence results delineating under what assumptions what kinds of convergence can be obtained for the proposed algorithm.The work reported here was supported in part by NSF Grant No. ECS-85-06249 and USAF Grant No. AFOSR-89-0518. The authors wish to thank the anonymous reviewers whose careful reading and criticism have helped them improve the paper considerably.     

Stochastic quasigradient methods for optimization of discrete event systems

In this paper, stochastic programming techniques are adapted and further developed for applications to discrete event systems. We consider cases where the sample path of the system depends discontinuously on control parameters (e.g. modeling of failures, several competing processes), which could make the computation of estimates of the gradient difficult. Methods which use only samples of the performance criterion are developed, in particular finite differences with reduced variance and concurrent approximation and optimization algorithms. Optimization of the stationary behavior is also considered. Results of numerical experiments and convergence results are reported.     

Stochastic viscosity solutions for SPDEs with continuous coefficients

In this note, nonlinear stochastic partial differential equations (SPDEs) with continuous coefficients are studied. Via the solutions of backward doubly stochastic differential equations (BDSDEs) with continuous coefficients, we provide an existence result of stochastic viscosity sub- and super-solutions to this class of SPDEs. Under some stronger conditions, we prove the existence of stochastic viscosity solutions.     

Stochastic approximation algorithm for minimax problems

A stochastic approximation algorithm for minimax optimization problems is analyzed. At each iterate, it performs one random experiment, based on which it computes a direction vector. It is shown that, under suitable conditions, it a.s. converges to the set of points satisfying necessary optimality conditions. The algorithm and its analysis bring together ideas from stochastic approximation and nondifferentiable optimization.     

Stochastic Comparison Algorithm for Discrete Optimization with Estimation of Time-Varying Objective Functions

In this paper, the optimization of time-varying objective functions, known only through estimates, is considered. Recent research defined algorithms for static optimization problems. Based on one of these algorithms, we derive an optimization scheme for the time-varying case. In stochastic optimization problems, convergence of an algorithm to the optimum prevents the algorithm from being efficiently adaptive to changes of the objective function if it is time-varying. So, convergence cannot be required in a time-varying scenario. Rather, we require convergence to the optimum with high probability together with a satisfactory dynamical behavior. Analytical and simulative results illustrate the performance of the proposed algorithm compared with other optimization techniques.     

Stochastic optimization for allocation problems with shortfall risk constraints

One of the crucial aspects in asset allocation problems is the assumption concerning the probability distribution of asset returns. Financial managers generally suppose normal distribution, even if extreme realizations usually have an higher frequency than in the Gaussian case. The aim of this paper is to propose a general Monte Carlo simulation approach able to solve an asset allocation problem with shortfall constraint, and to evaluate the exact portfolio risk‐level when managers assume a misspecified return behaviour. We assume that returns are generated by a multivariate skewed Student‐t distribution where each marginal can have different degrees of freedom. The stochastic optimization allows us to value the effective risk for managers. In the empirical application we consider a symmetric and heterogeneous case, and interestingly note that a multivariate Student‐t with heterogeneous marginal distributions produces in the optimization problem a shortfall probability and a shortfall return level that can be adequately approximated by assuming a multivariate Student‐t with common degrees of freedom. Thus, the proposed simulation‐based approach could be an important instrument for investors who require a qualitative assessment of the reliability and sensitivity of their investment strategies in the case their models could be potentially misspecified. Copyright © 2007 John Wiley & Sons, Ltd.     

A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*

We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-backs classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565).     

随机需求下多供应商和多零售商的生产-库存-运输联合优化模型

考虑随机需求下多供应商和多零售商的生产-库存-运输联合优化问题.在联合优化时,首先利用最近邻算法将各零售商分成不同区域,分区后问题转化为随机需求下单供应商对多零售商的生产-库存-运输联合优化问题.在每个分区内,由供应商统一决策其分区内各零售商的送货量和送货时间.利用粒子群算法和模拟退火算法相结合的两阶段算法求出最优送货量、最优运输路径和最大期望总利润.然后采用收入共享契约将增加的利润合理分配给各供应商和各零售商,使各方利润都得到增加,从而促使各方愿意合作.通过数值算例验证了联合优化模型优于独立决策模型.     

Modeling and solution strategies for unconstrained stochastic optimization problems

We review some modeling alternatives for handling risk in decision-making processes for unconstrained stochastic optimization problems. Solution strategies are discussed and compared.Invited lecture at the International Institute on Stochastics and Optimization, Gargnano, Italy, September 1–10, 1982.Supported in part by a Guggenheim Fellowship and a grant of the National Science Foundation.     

A smoothing stochastic algorithm for quantile estimation

In this paper, we provide the almost-sure convergence and the asymptotic normality of a smooth version of the Robbins–Monro algorithm for the quantile estimation. A Monte Carlo simulation study shows that our proposed method works well within the framework of a data stream.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

Single observation adaptive search for discrete and continuous stochastic optimization

Solving a stochastic optimization problem often involves performing repeated noisy function evaluations at points encountered during the algorithm. Recently, a continuous optimization framework for executing a single observation per search point was shown to exhibit a martingale property so that associated estimation errors are guaranteed to converge to zero. We generalize this martingale single observation approach to problems with mixed discrete–continuous variables. We establish mild regularity conditions for this class of algorithms to converge to a global optimum.     

Implicit Simulation Methods for Stochastic Chemical Kinetics

In biochemical systems some of the chemical species are present with only small numbers of molecules. In this situation discrete and stochasticsimulation approaches are more relevant than continuous and deterministic ones. The fundamental Gillespie’s stochastic simulation algorithm (SSA) accounts for every reaction event, which occurs with a probability determined by the configuration of the system. This approach requires a considerable computational effort for models with many reaction channels and chemical species.In order to improve efficiency, tau-leaping methods represent multiple firings of each reaction during a simulation step by Poisson random variables. For stiff systems the mean of this variable is treated implicitly in order to ensure numerical stability. This paper develops fully implicit tau-leaping-like algorithms that treat implicitly both the mean and the variance of the Poisson variables. The construction is based on adapting weakly convergent discretizations of stochastic differential equations to stochastic chemical kinetic systems. Theoretical analyses of accuracy and stability of the new methods are performed on a standard test problem. Numerical results demonstrate the performance of the proposed tau-leaping methods.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.