Gradient-Based Simulation Optimization Algorithms via Multi-Resolution System Approximations

Jingxu Xu () and Zeyu Zheng ()
Additional contact information
Jingxu Xu: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
Zeyu Zheng: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720

INFORMS Journal on Computing, 2023, vol. 35, issue 3, 633-651

Abstract: We propose gradient-based simulation-optimization algorithms to optimize systems that have complicated stochastic structure. The presence of complicated stochastic structure, such as the involvement of infinite-dimensional continuous-time stochastic processes, may cause the exact simulation of the system to be costly or even impossible. On the other hand, for a complicated system, one can sometimes construct a sequence of approximations at different resolutions, where the sequence has finer and finer approximation resolution but higher and higher cost to simulate. With the goal of optimizing the complicated system, we propose algorithms that strategically use the approximations with increasing resolution and higher simulation cost to construct stochastic gradients and perform gradient search in the decision space. To accommodate scenarios where approximations cause discontinuities and lead path-wise gradient estimators to have an uncontrollable bias, stochastic gradients for the proposed algorithms are constructed through finite difference. As a theory support, we prove algorithm convergence, convergence rate, and optimality of algorithm design under the assumption that the objective function for the complicated system is strongly convex, whereas no such assumptions are imposed on the approximations of the complicated system. We then present a multilevel version of the proposed algorithms to further improve convergence rates, when in addition the sequence of approximations can be naturally coupled.

Keywords: gradient-based simulation-optimization algorithms; approximating systems; multilevel algorithms; convergence rates (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1279 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:3:p:633-651

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().