Gradient-Based Algorithms for Convex Discrete Optimization via Simulation
针对高维离散决策空间的凸仿真优化问题，提出了多项式时间复杂度的随机搜索算法，并推导了信息论下界，展示了算法设计的极限。
Solving Convex Discrete Optimization via Simulation via Stochastic Search Algorithms Many decision-making problems in operations research and management science require the optimization of large-scale complex stochastic systems with high-dimensional discrete decision variables. For a number of applications, the objective function exhibits convexity in the discrete decision variables, or the problem can be transformed into a convex one. In “Gradient-Based Algorithms for Convex Discrete Optimization via Simulation,” Zhang, Zheng, and Lavaei propose provably efficient simulation–optimization algorithms for general convex optimization via simulation problems with high-dimensional discrete decision space. By utilizing the convex structure, the developed algorithms demonstrate a polynomial dependence on the dimension and scale of the decision space. In addition, information-theoretic lower bounds are derived to show the limit of algorithm design. In the case when possibly biased gradient estimators are available, they propose simulation–optimization algorithms to achieve optimality guarantees with a reduced dependence on the dimension.