International Press of Boston - publishers of scholarly mathematical and scientific journals and books

We present a gradient-based algorithm for solving a class of simulation optimization problems in which the objective function is the quantile of a simulation output random variable. In contrast with existing quantile (quantile derivative) estimation techniques, which aim to eliminate the estimator bias by gradually increasing the simulation sample size, our algorithm incorporates a novel recursive procedure that only requires a single simulation sample at each step to simultaneously obtain quantile and quantile derivative estimators that are asymptotically unbiased. We show that these estimators, when coupled with the standard gradient descent method, lead to a multitime-scale stochastic approximation type of algorithm that converges to an optimal quantile value with probability one. In our numerical experiments, the proposed algorithm is applied to optimal investment portfolio problems, resulting in new solutions that complement those obtained under the classical Markowitz mean-variance framework. History: Accepted by Alice E. Smith, Editor-in-Chief; Bruno Tuffin, Area Editor for Simulation. Funding: The work of Y. Peng was supported in part by the National Natural Science Foundation of China (NSFC) [Grants 72022001, 92146003, and 71901003], and by the Key Research and Development Programof Beijing Municipal Science and Technology Commission. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1214 .

The Annealing Adaptive Search (AAS) algorithm for global optimization searches the solution space by sampling from a sequence of Boltzmann distributions. For a class of optimization problems, it has been shown that the complexity of AAS increases at most linearly in the problem dimension. However, despite its desirable property, sampling from a Boltzmann distribution at each iteration of the algorithm remains a practical challenge. Prior work to address this issue has focused on embedding Markov chain-based sampling techniques within the AAS framework. In this article, based on ideas from the recent Cross-Entropy method and Model Reference Adaptive Search, we propose an algorithm, called Model-based Annealing Random Search (MARS), that complements prior work by sampling solutions from a sequence of surrogate distributions that iteratively approximate the target Boltzmann distributions. We establish a novel connection between MARS and the well-known Stochastic Approximation method. By exploiting this connection, we prove the global convergence of MARS and characterize its asymptotic convergence rate behavior. Our empirical results indicate promising performance of the algorithm in comparison with some of the existing methods. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011

We propose an adaptive search algorithm for solving simulation optimization problems with Lipschitz continuous objective functions. The method combines the strength of several popular strategies in simulation optimization. It employs the shrinking ball method to estimate the performance of sampled solutions and uses the performance estimates to fit a surrogate model that iteratively approximates the response surface of the objective function. The search for improved solutions at each iteration is then based on sampling from a promising region (a subset of the decision space) adaptively constructed to contain the point that optimizes the surrogate model. Under appropriate conditions, we show that the algorithm converges to the set of local optimal solutions with probability one. A computational study is also carried out to illustrate the algorithm and to compare its performance with some of the existing procedures.

Black-Box Quantile Optimization via Finite-Difference-Based Gradient Approximation Risk management necessitates consideration of metrics such as quantiles to supplement conventional mean performance measures. In “Quantile Optimization via Multiple-Timescale Local Search for Black-Box Functions,” J. Hu, M. Song, and M. C. Fu consider the problem where the goal is to optimize the quantile of a black-box output. They introduce two new iterative multitimescale stochastic approximation algorithms utilizing finite-difference-based gradient estimators. The first algorithm requires 2d + 1 samples of the black-box function per iteration, where d is the number of decision variables. The second employs a simultaneous-perturbation-based gradient estimator that uses only three samples per iteration, irrespective of the number of decision variables. The authors prove strong local convergence for both algorithms and analyze their finite-time convergence rates through a novel fixed-point argument. These algorithms perform well across a varied set of benchmark problems.