Gradient-Based Algorithms for Convex Discrete Optimization via Simulation

Haixiang Zhang (), Zeyu Zheng () and Javad Lavaei ()
Additional contact information
Haixiang Zhang: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720
Zeyu Zheng: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720
Javad Lavaei: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720

Operations Research, 2023, vol. 71, issue 5, 1815-1834

Abstract: We propose new sequential simulation–optimization algorithms for general convex optimization via simulation problems with high-dimensional discrete decision space. The performance of each choice of discrete decision variables is evaluated via stochastic simulation replications. If an upper bound on the overall level of uncertainties is known, our proposed simulation–optimization algorithms utilize the discrete convex structure and are guaranteed with high probability to find a solution that is close to the best within any given user-specified precision level. The proposed algorithms work for any general convex problem, and the efficiency is demonstrated by proven upper bounds on simulation costs. The upper bounds demonstrate a polynomial dependence on the dimension and scale of the decision space. For some discrete optimization via simulation problems, a gradient estimator may be available at low costs along with a single simulation replication. By integrating gradient estimators, which are possibly biased, we propose simulation–optimization algorithms to achieve optimality guarantees with a reduced dependence on the dimension under moderate assumptions on the bias.

Keywords: Simulation; discrete optimization via simulation; discrete convex functions; sequential simulation–optimization algorithms; simulation costs; biased gradient estimators (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2295 (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:oropre:v:71:y:2023:i:5:p:1815-1834

Access Statistics for this article

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