Gradient-Based Algorithms for Convex Discrete Optimization via Simulation

DOI10.1287/OPRE.2022.2295MaRDI QIDQ6195081zbMATH OpenOpenAlexFDO

Authors Haixiang Zhang, Zeyu Zheng, Javad Lavaei

Publication date 12 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.16250

zbMATH Keywords

biased gradient estimatorsdiscrete convex functionsdiscrete optimization via simulationsequential simulation-optimization algorithmssimulation costs

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

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.

Recommendations

• Gradient-Based Simulation Optimization Algorithms via Multi-Resolution System Approximations
• Discrete Optimization via Simulation Using COMPASS
• Gradient-based adaptive stochastic search for simulation optimization over continuous space
• Gradient-based simulation optimization under probability constraints
• Gradient methods of maximization of convex functions on discrete structures

Cited in

(5)

• Rapid Discrete Optimization via Simulation with Gaussian Markov Random Fields
• Gradient-Based Simulation Optimization Algorithms via Multi-Resolution System Approximations
• Projected Gaussian Markov improvement algorithm for high-dimensional discrete optimization via simulation
• Review of large-scale simulation optimization
• Nonparametric estimation via partial derivatives

This page was built for publication: Gradient-Based Algorithms for Convex Discrete Optimization via Simulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195081)