Constrained Optimization in Random Simulation: Efficient Global Optimization and Karush-Kuhn-Tucker Conditions

Ebru Angun, Jack Kleijnen

Research output: Working paperDiscussion paperOther research output

204 Downloads (Pure)

Abstract

We develop a novel method for solving constrained optimization problems in random (or stochastic) simulation; i.e., our method minimizes the goal output subject to one or more output constraints and input constraints. Our method is indeed novel, as it combines the Karush-Kuhn-Tucker (KKT) conditions with the popular algorithm called "effciient global optimization" (EGO), which is also known as "Bayesian optimization" and is related to “active learning". Originally, EGO solves non-constrained optimization problems in deterministic simulation; EGO is a sequential algorithm that uses Kriging (or Gaussian process) metamodeling of the underlying simulation model, treating the simulation as a black box. Though there are many variants of EGO - for these non-constrained deterministic problems and for variants of these problems - none of these EGO-variants use the KKT conditions - even though these conditions are well-known (first-order necessary) optimality conditions in white-box problems. Because the simulation is random, we apply stochastic Kriging. Furthermore, we allow for variance heterogeneity and apply a popular sample allocation rule to determine the number of replicated simulation outputs for selected combinations of simulation inputs. Moreover, our algorithm can take advantage of parallel computing. We numerically compare the performance of our algorithm and the popular proprietary OptQuest algorithm, in two familiar examples (namely, a mathematical toy example and a practical inventory system with a service-level constraint); we conclude that our algorithm is more efficient (requires fewer expensive simulation runs) and effective (gives better estimates of the true global optimum).

Original languageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages46
Volume2022-022
Publication statusPublished - 30 Aug 2022

Publication series

NameCentER Discussion Paper
Volume2022-022

Keywords

  • Simulation
  • design of experiments
  • simulation
  • statistical analysis
  • artificial intelligence
  • computational- experiments
  • inventory-production

Fingerprint

Dive into the research topics of 'Constrained Optimization in Random Simulation: Efficient Global Optimization and Karush-Kuhn-Tucker Conditions'. Together they form a unique fingerprint.

Cite this