It is frequently the case that deterministic optimization models could be made more practical by explicitly incorporating uncertainty. The resulting stochastic optimization problems are in general more difficult to solve than their deterministic counterparts, because the objective function cannot be evaluated exactly and/or because there is no explicit relation between the objective function and the corresponding decision variables. This thesis develops random search algorithms for solving optimization problems with continuous decision variables when the objective function values can be estimated with some noise via simulation. Our algorithms will maintain a set of sampled solutions, and use simulation results at these solutions to guide the search for better solutions. In the first part of the thesis, we propose an Adaptive Search with Resampling and Discarding (ASRD) approach for solving continuous stochastic optimization problems. Our ASRD approach is a framework for designing provably convergent algorithms that are adaptive both in seeking new solutions and in keeping or discarding already sampled solutions. The framework is an improvement over the Adaptive Search with Resampling (ASR) method of Andradottir and Prudius in that it spends less effort on inferior solutions (the ASR method does not discard already sampled solutions). We present conditions under which the ASRD method is convergent almost surely and carry out numerical studies aimed at comparing the algorithms. Moreover, we show that whether it is beneficial to resample or not depends on the problem, and analyze when resampling is desirable. Our numerical results show that the ASRD approach makes substantial improvements on ASR, especially for difficult problems with large numbers of local optima. In traditional simulation optimization problems, noise is only involved in the objective functions. However, many real world problems involve stochastic constraints. Such problems are more difficult to solve because of the added uncertainty about feasibility. The second part of the thesis presents an Adaptive Search with Discarding and Penalization (ASDP) method for solving continuous simulation optimization problems involving stochastic constraints. Rather than addressing feasibility separately, ASDP utilizes the penalty function method from deterministic optimization to convert the original problem into a series of simulation optimization problems without stochastic constraints. We present conditions under which the ASDP algorithm converges almost surely from inside the feasible region, and under which it converges to the optimal solution but without feasibility guarantee. We also conduct numerical studies aimed at assessing the efficiency and tradeoff under the two different convergence modes. Finally, in the third part of the thesis, we propose a random search method named Gaussian Search with Resampling and Discarding (GSRD) for solving simulation optimization problems with continuous decision spaces. The method combines the ASRD framework with a sampling distribution based on a Gaussian process that not only utilizes the current best estimate of the optimal solution but also learns from past sampled solutions and their objective function observations. We prove that our GSRD algorithm converges almost surely, and carry out numerical studies aimed at studying the effects of utilizing the Gaussian sampling strategy. Our numerical results show that the GSRD framework performs well when the underlying objective function is multi-modal. However, it takes much longer to sample solutions, especially in higher dimensions.

We consider the problem of identifying solutions to a stochastic system under multiple constraints. The objective function and the constraints are expressed in terms of performance measures of the system that are observable only via a simulation model parameterized by a finite number of decision variables. In solving for such a system, one faces the much harder challenge of verifying the feasibility of a potential solution. Toward this, we present cgR-SPLINE, a multistart simulation optimization (SO) algorithm on integer spaces. cgR-SPLINE sequentially solves random restarts of a gradient-based local search routine with increasing precision. The local search routine in turn solves progressively stricter outer approximations of the underlying problem. The local solution estimator from a recently ended restart is probabilistically compared against an incumbent solution, thus generating a sequence of global solution estimators. The optimal convergence rate of the solution iterates is observed to be sub-exponential, slower than the exponential rate observed for SO problems on unconstrained discrete spaces. Additionally, efficiency for cgR-SPLINE dictates that the number of multistarts and the total simulation budget be sublinearly related, implying an increased emphasis on exploration than is prescribed in the continuous context. Heuristics for choosing constraint relaxations and solution reporting demonstrate good finite-time performance on three SO problems, of which two are nontrivial. The extension of cgR-SPLINE's framework to mixed spaces seems a natural next step. The presence of infeasible points arbitrarily close to the stochastic boundary, however pose challenges for consistency. We present a general framework for mixed spaces that is very much along the lines of cgR-SPLINE and propose ideas for specific algorithmic refinements and solution reporting. Strategically locating the restarts of a multistart SO algorithm appears to be a largely unexplored research topic. Toward achieving efficiency during the exploration phase, we present ideas for ``antithetically" generating the restarts from probability measures constructed from the SO algorithm's performance trajectory. Asymptotic behavior of the proposed sampling strategy and policies for optimal parameter selection are presently conjectural, but appear promising based on the outcomes of preliminary experiments. / Ph. D.

In this thesis, we first develop a new method called penalty function with memory (PFM). PFM consists of a penalty parameter and a measure of constraint violation and it converts a discrete optimization via simulation (DOvS) problem with stochastic constraints into a series of DOvS problems without stochastic constraints. PFM determines a penalty of a visited solution based on past results of feasibility checks on the solution. Specifically, assuming a minimization problem, a penalty parameter of PFM, namely the penalty sequence, diverges to infinity for an infeasible solution but converges to zero almost surely for any strictly feasible solution under certain conditions. For a feasible solution located on the boundary of feasible and infeasible regions, the sequence converges to zero either with high probability or almost surely. As a result, a DOvS algorithm combined with PFM performs well even when optimal solutions are tight or nearly tight. Second, we design an optimal water quality monitoring network for river systems. The problem is to find the optimal location of a finite number of monitoring devices, minimizing the expected detection time of a contaminant spill event while guaranteeing good detection reliability. When uncertainties in spill and rain events are considered, both the expected detection time and detection reliability need to be estimated by stochastic simulation. This problem is formulated as a stochastic DOvS problem with the objective of minimizing expected detection time and with a stochastic constraint on the detection reliability; and it is solved by a DOvS algorithm combined with PFM. Finally, we improve PFM by combining it with an approximate budget allocation procedure. We revise an existing optimal budget allocation procedure so that it can handle active constraints and satisfy necessary conditions for the convergence of PFM.