A review of simulation optimization techniques
---
paper_title: Convergence Results for Harmonic Gradient Estimators

paper_content:

Sensitivity analysis of steady state simulation outputs typically involves estimating gradients. This paper presents convergence results for the harmonic gradient estimators. Sufficient conditions are formulated that validate the interchange of the derivative and the expectation operators for these estimators. The relationship between these estimators and finite differences gradient estimators is discussed. In particular, the harmonic estimators are shown to be variations of finite differences gradient estimators. Exploiting the orthogonal property of the trigonometric basis results in harmonic gradient estimation procedures requiring two simulation runs. Computational results with various queueing system simulation models are included to compare and illustrate the different estimators. These results suggest that the harmonic gradient estimation procedures requiring two simulation runs may be an alternative to forward (symmetric) finite differences gradient estimation procedures with common random number streams requiring p + 1 (2 p ) simulation runs. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: Conditional Monte Carlo: Gradient Estimation and Optimization Applications

paper_content:

Preface. Selected Notation. 1. Introduction. 2. Three Extended Examples. 3. Conditional Monte Carlo Gradient Estimation. 4. Links to Other Settings. 5. Synopsis and Preview. 6. Queueing Systems. 7. (s,S) Inventory Systems. 8. Other Applications. References. Index. Corrections to Conditional Monte Carlo: Gradient Estimation and Optimization Applications (Kluwer International Series in Engineering and Computer Science, 392) by Michael C. Fu and Jian-Qiang Hu can be found at the Internet.
---
paper_title: Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method

paper_content:

Preliminaries Sensitivity Analysis and Stochastic Optimization of Discrete Event Static Systems (DESS) Sensitivity Analysis and Stochastic Optimization of Discrete Event Dynamic Systems (DEDS) What Is a Good'' Reference System to Simulate Extensions of the SF Method Statistical Inference of Stochastic Optimization Programs Bibliography Index.
---
paper_title: Stochastic Approximation Methods for Constrained and Unconstrained Systems

paper_content:

I. Introduction.- 1.1. General Remarks.- 1.2. The Robbins-Monro Process.- 1.3. A "Continuous" Process Version of Section 2.- 1.4. Regulation of a Dynamical System a simple example.- 1.5. Function Minimization: The Kiefer-Wolfowitz Procedure.- 1.6. Constrained Problems.- 1.7. An Economics Example.- II. Convergence w.p.1 for Unconstrained Systems.- 2.1. Preliminaries and Motivation.- 2.2. The Robbins-Monro and Kiefer-Wolfowitz Algorithms: Conditions and Discussion.- 2.3. Convergence Proofs for RM and KW-like Procedures.- 2.3.1. A Basic RM-like Procedure.- 2.3.2. One Dimensional RM and Accelerated RM Procedures.- 2.3.3. A Continuous Parameter RM Procedure.- 2.3.4. The Basic Kiefer-Wolfowitz Procedure.- 2.3.5. Random Directions KW Methods.- 2.4. A General Robbins-Monro Process: "Exogenous Noise".- 2.4.1. The Case of Bounded h(*,*).- 2.4.2. Unbounded h(*,*): Exogenous Noise.- 2.5. A General RM Process State Dependent Noise.- 2.5.1. Extensions and Localizations of Theorem 2.5.2.- 2.6. Some Applications.- 2.7. Mensov-Rademacher Estimates.- III. Weak Convergence of Probability Measures.- IV. Weak Convergence for Unconstrained Systems.- 4.1. Conditions and General Discussion.- 4.2. The Robbins-Monro and Kiefer-Wolfowitz Procedures.- 4.2.1. The Basic Robbins-Monro Procedure.- 4.2.2. The One-Dimensional Robbins-Monro Procedure.- 4.2.3. The Kiefer-Wolfowitz Procedure.- 4.2.4. A Case Where the Limit Satisfies a Generalized ODE.- 4.2.5. A Continuous Parameter KW Procedure.- 4.3. A General Robbins-Monro Process: Exogenous Noise.- 4.4. A General RM Process: State Dependent Noise.- 4.5. The Identification Problem.- 4.6. A Counter-Example to Tightness.- 4.7. Boundedness of {Xn} and Tightness of {Xn(*)}.- V. Convergence w.p.1 For Constrained Systems.- 5.1. A Penalty-Multiplier Algorithm for Equality Constraints.- 5.1.1. A Basic RM-like Algorithm, Conditions and Discussion.- 5.1.2. The Noise Condition, Discussion and Generalization.- 5.1.3. Boundedness of {Xn}.- 5.1.4. Proof of the Main Theorem.- 5.1.5. Constrained Function Minimization and Other Extensions.- 5.2. A Lagrangian Method for Inequality Constraints.- 5.2.1. The Algorithm and Conditions.- 5.2.2. The Convergence Theorem 18.- 5.2.3. A Non-Convergent but Useful Algorithm.- 5.2.4. An Application to the Identification Problem.- 5.3. A Projection Algorithm.- 5.4. A Penalty-Multiplier Method for Inequality Constraints.- VI. Weak Convergence: Constrained Systems.- 6.1. A Multiplier Type Algorithm for Equality Constraints.- 6.1.1. Boundedness of {Xn}.- 6.1.2. The Noise Condition, Discussion.- 6.1.3. The Convergence Theorem.- 6.2. The Lagrangian Method.- 6.3. A Projection Algorithm.- 6.4. A Penalty-Multiplier Algorithm for Inequality Constraints.- VII. Rates of Convergence.- 7.1. The Problem Formulation.- 7.2. Conditions and Discussions.- 7.3. Rates of Convergence for Case 1, the KW Algorithm.- 7.4. Discussion of Rates of Convergence for Two KW Algorithms.
---
paper_title: STOCHASTIC APPROXIMATION PROCEDURES WITH RANDOMLY VARYING TRUNCATIONS

paper_content:

In this paper, we propose a new procedure with randomly varying truncations to search for zeros or extreme of a regression function. Under quite weak conditions imposed on the regression function, we prove the global convergence of the procedure when the measurement errors belong to a class of dependent random sequences including the stationary ARMA(Autoregressive and Moving Average) process as its special case.
---
paper_title: Stochastic algorithms with Armijo stepsizes for minimization of functions

paper_content:

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratexi, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratexi+1. For an appropriate optimality function σ, corresponding to an optimality condition, it is shown that, ifn(i) → ∞, then σ(xi) → 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.
---
paper_title: Accelerated Stochastic Approximation

paper_content:

A technique to accelerate convergence of stochastic approximation algorithms is studied. It is based on Kesten’s idea of equalization of the gain coefficient for the Robbins–Monro algorithm. Convergence with probability 1 is proved for the multidimensional analog of the Kesten accelerated stochastic approximation algorithm. Asymptotic normality of the delivered estimates is also shown. Results of numerical simulations are presented that demonstrate the efficiency of the acceleration procedure.
---
paper_title: Adaptive Design and Stochastic Approximation

paper_content:

When y= M(x) + e, where M may be nonlinear, adaptive stochastic approximation schemes for the choice of the levels x 1, x 2, ··· at which y 1, y 2, ··· are observed lead to asymptotically efficient estimates of the value θ of x for which M(θ) is equal to some desired value. More importantly, these schemes make the “cost” of the observations, defined at the nth stage to be Σ 1 n (x i - θ)2, to be of the order of log n instead of n, an obvious advantage in many applications. A general asymptotic theory is developed which includes these adaptive designs and the classical stochastic approximation schemes as special cases. Motivated by the cost considerations, some improvements are made in the pairwise sampling stochastic approximation scheme of Venter.
---
paper_title: Stochastic Approximation and Optimization of Random Systems

paper_content:

I Foundations of stochastic approximation.- 1 Almost sure convergence of stochastic approximation procedures.- 2 Recursive methods for linear problems.- 3 Stochastic optimization under stochastic constraints.- 4 A learning model recursive density estimation.- 5 Invariance principles in stochastic approximation.- 6 On the theory of large deviations.- References for Part I.- II Applicational aspects of stochastic approximation.- 7 Markovian stochastic optimization and stochastic approximation procedures.- 8 Asymptotic distributions.- 9 Stopping times.- 10 Applications of stochastic approximation methods.- References for Part II.- III Applications to adaptation algorithms.- 11 Adaptation and tracking.- 12 Algorithm development.- 13 Asymptotic Properties in the decreasing gain case.- 14 Estimation of the tracking ability of the algorithms.- References for Part III.
---
paper_title: Stochastic Approximation Algorithms and Applications

paper_content:

Applications and issues application to learning, state dependent noise and queueing applications to signal processing and adaptive control mathematical background convergence with probability one - Martingale difference noise convergence with probability one - correlated noise weak convergence - introduction weak convergence methods for general algorithms applications - proofs of convergence rate of convergence averaging of the iterates distributed/decentralized and asynchronous algorithms.
---
paper_title: On extensions of Polyak's averaging approach to stochastic approximation

paper_content:

Stochastic approximation algorithms are considered and Polyak's averaging approach (cf. [1]) is revisited. Under much weaker conditions, convergence and rate of convergence results are developed. In lieu of uncorrelated noise, φ-mixing type of random disturbances are treated. By means of weak convergence methods, it is shown that the multistage algorithms via averaging have asymptotically optimal convergence speed and are efficient procedures
---
paper_title: Convergence analysis of stochastic algorithms

paper_content:

This paper investigates asymptotic convergence to stationary points of gradient descent algorithms where the functions involved are not available in closed form but are approximated by sequences of random functions. The algorithms take large stepsizes and use progressively finer precision at successive iterations. Two kinds of optimization algorithms are considered: one, where the limiting function to be minimized is differentiable but the random approximating functions can be nondifferentiable, and the other, where both the limiting and approximating functions are nondifferentiable and convex. Such functions often arise in discrete event dynamic system-models in various application areas. ::: ::: The analysis brings together ideas and techniques from the disciplines of nonlinear programming and nondifferentiable optimization on one hand, and stochastic processes and especially uniform laws of large numbers, on the other hand. A general algorithmic frame-work is first developed and analyzed, and then applied to the specific algorithms considered. The analysis extends the results derived to date for similar algorithms, and has a potential for further extensions in proving convergence of other algorithms as well.
---
paper_title: Almost sure convergence of stochastic approximation algorithms with non-additive noise

paper_content:

Abstract Stochastic approximation algorithms with non-additive noise are discussed. In studying strong convergence of such algorithms, traditionally one assumes that the iterates return to a bounded or compact set infinitely often, or that the function under consideration grows with certain rate. The usual projection algorithms require that the bounded projection region is known beforehand. It is desirable to weaken these ‘boundedness’ conditions. By introducing randomly varying truncations, Chen and Zhu (1986) achieved this for stochastic approximation algorithms with additive noise. Here, we extend their result to a more general setting.
---
paper_title: stochastic quasigradient methods and their application to system optimization†

paper_content:

This paper systematically surveys the development of stochastic quasigradient (SQG) methods.These methods make it possible to solve optimization problems without calculating the precise valuesw of objectives and constraints (let alone of their derivatives). For deterministic nonlinear optimization problems, these methods can be regarded as methods of random search. For stochastic programming problems. SQG methods generalize the well-known stochastic approximation methods for unconstrained optimization of the expectation of a random function to problems involving general constraints.
---
paper_title: A Stochastic Approximation Method

paper_content:

Let M(x) denote the expected value at level x of the response to a certain experiment. M(x) is assumed to be a monotone function of x but is unknown to the experimenter, and it is desired to find the solution x = θ of the equation M(x) = α, where a is a given constant. We give a method for making successive experiments at levels x1, x2, ··· in such a way that xn will tend to θ in probability.
---
paper_title: An optimization algorithm with probabilistic estimation

paper_content:

The authors present a stochastic optimization algorithm based on the idea of the gradient method which incorporates a novel adaptive-precision 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. 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. The authors present two types of convergence results delineating under what assumptions various kinds of convergence can be obtained for the proposed algorithm. They also present a parallel version of the proposed algorithm.<<ETX>>
---
paper_title: Stochastic approximation for Monte Carlo optimization

paper_content:

In this paper, we introduce two convergent Monte Carlo algorithms for optimizing complex stochastic systems. The first algorithm, which is applicable to regenerative processes, operates by estimating finite differences. The second method is of Robbins-Monro type and is applicable to Markov chains. The algorithm is driven by derivative estimates obtained via a likelihood ratio argument.
---
paper_title: Acceleration of Stochastic Approximation by Averaging

paper_content:

A new recursive algorithm of stochastic approximation type with the averaging of trajectories is investigated. Convergence with probability one is proved for a variety of classical optimization and identification problems. It is also demonstrated for these problems that the proposed algorithm achieves the highest possible rate of convergence.
---
paper_title: Convergence analysis of gradient descent stochastic algorithms

paper_content:

This paper proves convergence of a sample-path based stochastic gradient-descent algorithm for optimizing expected-value performance measures in discrete event systems. The algorithm uses increasing precision at successive iterations, and it moves against the direction of a generalized gradient of the computed sample performance function. Two convergence results are established: one, for the case where the expected-value function is continuously differentiable; and the other, when that function is nondifferentiable but the sample performance functions are convex. The proofs are based on a version of the uniform law of large numbers which is provable for many discrete event systems where infinitesimal perturbation analysis is known to be strongly consistent.
---
paper_title: Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method

paper_content:

Preliminaries Sensitivity Analysis and Stochastic Optimization of Discrete Event Static Systems (DESS) Sensitivity Analysis and Stochastic Optimization of Discrete Event Dynamic Systems (DEDS) What Is a Good'' Reference System to Simulate Extensions of the SF Method Statistical Inference of Stochastic Optimization Programs Bibliography Index.
---
paper_title: Retrospective simulation response optimization

paper_content:

An approach to simulation response optimization in which a simulation experiment is run in such a manner as to generate optimal solutions is presented. Once the stochastic sample path of a simulation run has been generated, it is sometimes possible to retrospectively solve a deterministic optimization problem or a closely related problem. As demonstrated with some examples from communications and manufacturing, this approach can greatly simplify both the simulation experiment and the simulation model. >
---
paper_title: Analysis of Sample-Path Optimization

paper_content:

Sample-path optimization is a method for optimizing limit functions occurring in stochastic modeling problems, such as steady-state functions in discrete-event dynamic systems. It is closely related to retrospective optimization techniques and to M-estimation. The method has been computationally tested elsewhere on problems arising in production and in project planning, with apparent success. In this paper we provide a mathematical justification for sample-path optimization by showing that under certain assumptions---which hold for the problems just mentioned---the method will almost surely find a point that is, in a specified sense, sufficiently close to the set of optimizers of the limit function.
---
paper_title: Stochastic discrete optimization

paper_content:

In this paper a stochastic search method is proposed for finding a global solution to the stochastic discrete optimization problem in which the objective function must be estimated by Monte Carlo simulation. Although there are many practical problems of this type in the fields of manufacturing engineering, operations research, and management science, there have not been any nonheuristic methods proposed for such discrete problems with stochastic infrastructure. The proposed method is very simple, yet it finds a global optimum solution. The method exploits the randomness of Monte Carlo simulation and generates a sequence of solution estimates. This generated sequence turns out to be a nonstationary Markov chain, and it is shown under mild conditions that the Markov chain is strongly ergodic and that the probability that the current solution estimate is global optimum converges to one. Furthermore, the speed of convergence is also analyzed.
---
paper_title: Simulated annealing with noisy or imprecise energy measurements

paper_content:

The annealing algorithm (Ref. 1) is modified to allow for noisy or imprecise measurements of the energy cost function. This is important when the energy cannot be measured exactly or when it is computationally expensive to do so. Under suitable conditions on the noise/imprecision, it is shown that the modified algorithm exhibits the same convergence in probability to the globally minimum energy states as the annealing algorithm (Ref. 2). Since the annealing algorithm will typically enter and exit the minimum energy states infinitely often with probability one, the minimum energy state visited by the annealing algorithm is usually tracked. The effect of using noisy or imprecise energy measurements on tracking the minimum energy state visited by the modified algorithms is examined.
---
paper_title: Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimize buffer sizes in automatic assembly systems

paper_content:

Selecting appropriate buffer sizes for the transport systems of automated manufacturing systems is a complex task that must account for random fluctuations in production rates by individual machines as well as the transport delays that are a part of the material handling system. If the buffer sizes are too large then the transport delays are excessive and more in-process inventories must be loaded into the system to accomodate the large buffer sizes. If the buffer sizes are too small then small processing delays will cause the buffers to fill and upstream workstations will be blocked from releasing completed workpieces. This paper integrates an extension of the simulated annealing algorithm used in combinatorial optimization with a discrete event simulation of the manufacturing system to find optimal buffer sizes for asynchronous assembly systems which involve automated inspection as well as automated assembly.
---
paper_title: Simulation optimization using simulated annealing

paper_content:

Abstract The purpose of this study is to investigate the feasibility of using a simulated annealing algorithm in conjunction with a simulation model to find the optimal parameter levels at which to operate a system. In particular, we discuss an effort to use simulated annealing to find a combination of input parameter values for a model which optimizes a nonconvex, nonconcave objective function of the input parameters. In the absence on an optimal annealing schedule, we demonstrate that multiple runs of the simulated annealing algorithm can result in an optimal or near-optimal solution to the problem.
---
paper_title: Simulated Annealing for noisy cost functions

paper_content:

We generalize a classical convergence result for the Simulated Annealing algorithm to a stochastic optimization context, i.e., to the case where cost function observations are disturbed by random noise. It is shown that for a certain class of noise distributions, the convergence assertion remains valid, provided that the standard deviation of the noise is reduced in the successive steps of cost function evaluation (e.g., by repeated observation) with a speed O(k -γ ), where γ is an arbitrary constant larger than one.
---
paper_title: Stochastic comparison algorithm for discrete optimization with estimation

paper_content:

An iterative discrete optimization algorithm that works with Monte Carlo estimation of the objective function is developed. Two algorithms, the simulated annealing algorithm and the stochastic ruler algorithm, are considered. The authors examine some of the problems of their use and combine the advantages of both algorithms to form an iterative random search algorithm called the stochastic comparison (SC) algorithm. The SC algorithm actually solves an alternative optimization problem, and it is shown under symmetry assumption that the alternative problem is equivalent to the original one. The convergence of the SC algorithm is proved based on time-inhomogeneous Markov chain theory. Results of numerical experiments on a testbed problem with randomly generated objective function are presented. >
---
paper_title: stochastic quasigradient methods and their application to system optimization†

paper_content:

This paper systematically surveys the development of stochastic quasigradient (SQG) methods.These methods make it possible to solve optimization problems without calculating the precise valuesw of objectives and constraints (let alone of their derivatives). For deterministic nonlinear optimization problems, these methods can be regarded as methods of random search. For stochastic programming problems. SQG methods generalize the well-known stochastic approximation methods for unconstrained optimization of the expectation of a random function to problems involving general constraints.
---
paper_title: Discrete stochastic optimization using variants of the stochastic ruler method

paper_content:

We present two random search methods for solving discrete stochastic optimization problems. Both of these methods are variants of the stochastic ruler algorithm. They differ from our earlier modification of the stochastic ruler algorithm in that they use different approaches for estimating the optimal solution. Our new methods are guaranteed to converge almost surely to the set of global optimal solutions under mild conditions. We discuss under what conditions these new methods are expected to converge faster than the modified stochastic ruler algorithm. We also discuss how these methods can be used for solving discrete optimization problems when the values of the objective function are estimated using either transient or steady-state simulation. Finally, we present numerical results that compare the performance of our new methods with that of the modified stochastic ruler algorithm when applied to solve buffer allocation problems. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.
---
paper_title: On Optimal Allocation of Indivisibles under Uncertainty

paper_content:

The optimal allocation of indivisible resources is formalized as a stochastic optimization problem involving discrete decision variables. A general stochastic search procedure is proposed, which develops the concept of the branch-and-bound method. The main idea is to process large collections of possible solutions and to devote more attention to the most promising groups. By gathering more information to reduce the uncertainty and by narrowing the search area, the optimal solution can be found with probability one. Special techniques for calculating stochastic lower and upper bounds are discussed. The results are illustrated by a computational experiment.
---

Title: A Review of Simulation Optimization Techniques

Section 1: INTRODUCTION
Description 1: Write an introduction to the concept of simulation optimization and outline the scope and organization of the paper.

Section 2: CONTINUOUS PARAMETER SIMULATION OPTIMIZATION
Description 2: Discuss techniques for optimizing systems with continuous parameters, including gradient estimation, stochastic approximation, and sample path optimization.

Section 3: Gradient Estimation
Description 3: Describe methods for estimating the gradient of the performance concerning continuous parameters, including finite differences, perturbation analysis, and likelihood ratio method.

Section 4: Stochastic Approximation
Description 4: Review stochastic approximation methods for solving continuous parameter simulation optimization problems, focusing on the Robbins-Monro algorithm and its variants.

Section 5: Sample Path Optimization
Description 5: Discuss methods that approximate the original simulation optimization problem with a deterministic optimization problem.

Section 6: DISCRETE PARAMETER SIMULATION OPTIMIZATION
Description 6: Provide a review of random search methods for optimizing systems with discrete parameters and discuss other recent developments.

Section 7: Random Search
Description 7: Discuss random search methods such as the stochastic ruler algorithm and simulated annealing for discrete simulation optimization.

Section 8: Other Recent Developments
Description 8: Describe additional advancements in discrete parameter simulation optimization, including branch-and-bound methods and the use of confidence sets.

Section 9: CONCLUSION
Description 9: Summarize the key points discussed in the paper and highlight the need for further research to enhance the efficiency and user-friendliness of simulation optimization techniques.

Section 10: ACKNOWLEDGMENT
Description 10: Acknowledge the funding and support received for the research work.