THEORY AND METHODS FOR GLOBAL MULTI-OBJECTIVE SIMULATION OPTIMIZATION ON COMPACT SETS

A Multi-Objective Simulation Optimization (MOSO) problem is an optimization problem in which multiple conflicting objectives can only be observed with stochastic error through a Monte Carlo simulation oracle. The solution to a MOSO problem is the efficient set, which consists of feasible decision points where no other feasible point is at least as good in all objectives and strictly better in at least one. The image of the efficient set is the Pareto set. Characterizing and computing these sets is a challenge in many settings. Advances in MOSO theory and methods are helping to address these challenges, but the field is still developing, operating at the intersection of Single-Objective Simulation Optimization (SOSO) and Multi-Objective Optimization (MOO), with many fundamental questions yet to be answered. This thesis considers global MOSO problems on a continuous and compact feasible set, where each decision variable can take any value within an interval subset of the real numbers. If computing resources are plentiful, the simulation model runs quickly, or there is no exploitable structure in the MOSO problem, one might implement a simple algorithm which consists of selecting m feasible points in the decision space using a space-filling design, expending n simulation replications per point to estimate the objective function values, and returning the discretized estimated efficient and Pareto sets under a total simulation budget b, which equals m times n. For these problems, how should one trade off the number of decision points to sample, m, with the number of simulation replications per sampled point, n, to ensure that the estimated Pareto set converges to the true Pareto set at the fastest possible rate?

To answer this question, one must first establish a performance indicator to measure convergence in a MOSO setting. A natural choice is the Hausdorff distance between the global Pareto set and the true image of the estimated discretized efficient set, which facilitates splitting the optimality gap into two components through the triangle inequality: the discretization error and the selection error. The first study establishes upper bounds on the discretization error in both the decision and objective spaces for the simplest case of bi- objective convex quadratic optimization. This study provides upper bounds to characterize the optimality gap measured by Hausdorff distance in terms of dispersion. However, because of the inherent complexity and computational challenges associated with the general use of the Hausdorff distance, alternative performance indicators are considered in subsequent analyses.

The second study addresses the challenge of ensuring convergence in MOSO by introducing a novel and tractable performance indicator. This allows for the derivation of upper bounds on both discretization and selection errors, and crucially, determination of the optimal balance between the number of feasible points (m) and the simulation replications per point (n) required for fast convergence of the optimality gap to zero in probability. A key aspect of this study’s primary contribution is the introduction and examination of the modified coverage error. By decomposing the modified coverage error between Pareto set and true image of estimated discretized efficient set into deterministic and stochastic components, particularly under Lipschitz-continuous objective functions, the analysis provides valuable insights. A key contribution is the proposed one-shot algorithm, which strategically selects m points by leveraging low-dispersion point sets to discretize the continuous decision space and simulates objective values with n replications per point, thereby providing an estimated efficient set and its image with a probabilistic guarantee that is informed by the underlying trade-off between m and n. Furthermore, the derived results establish both an upper bound on the convergence rate for simpler algorithms and a lower bound for more sophisticated global MOSO algorithms that exploit problem structure. Consequently, this research offers actionable guidance on selecting the total simulation budget (b = m × n) and strategically allocating m and n based on problem characteristics, such as the dimension, to achieve a desired optimality gap and probabilistic guarantee. Numerical examples are also conducted, and to further optimize the results, heuristic parameter selection is recommended.

In summary, this dissertation contributes to addressing foundational questions within MOSO, specifically concerning the allocation of computational budgets for global continuous optimization problems. The insights developed are valuable for both academic researchers and practitioners tackling complex decision optimization tasks that involves stochasticity.