Stochastic Localization Methods for Convex Discrete Optimization via Simulation
针对大规模凸离散仿真优化问题，提出基于定位和切割平面思想的随机算法，其计算复杂度与决策空间维度和规模呈多项式关系，且仿真成本与目标函数无关，数值表现优于现有方法。
Solving Convex Discrete Optimization via Simulation via Stochastic Localization Algorithms Many decision-making problems in operations research and management science require the optimization of large-scale complex stochastic systems. 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 “Stochastic Localization Methods for Convex Discrete Optimization via Simulation,” Zhang, Zheng, and Lavaei propose provably efficient simulation-optimization algorithms for general large-scale convex discrete optimization via simulation problems. By utilizing the convex structure and the idea of localization and cutting-plane methods, the developed stochastic localization algorithms demonstrate a polynomial dependence on the dimension and scale of the decision space. In addition, the simulation cost is upper bounded by a value that is independent of the objective function. The stochastic localization methods also exhibit a superior numerical performance compared with existing algorithms.