Zaile Li, Weiwei Fan, L. Jeff Hong

Management Science, Vol. 71, 2025

推荐理由

仿真优化是一种结合仿真模型与优化算法的技术，旨在通过计算机仿真实验找到最优决策，已广泛应用于物流、医疗、金融等多个领域。当今，随着实际需求的持续增长和计算能力的快速提升，决策问题所面临的可行解空间规模日益庞大，亟须更高效的仿真优化方法以应对这一挑战。对此，我院管理高等研究院范薇薇副教授与团队开展深入研究。

作者简介

Zaile Li：复旦大学

Weiwei Fan：同济大学经济与管理学

L. Jeff Hong：复旦大学

关键词

ranking and selection, sample optimality, greedy, boundary-crossing

内容简介

随着社会的快速发展和算力的持续提升，现代决策问题往往需要在数量庞大的可行决策集合中选择最优解。在这一背景下，如何设计高效算法来解决大规模排序与择优问题，已经成为仿真优化领域的核心研究方向，并引发了广泛关注。

在大规模选择排序问题中，样本复杂度是衡量算法效率的关键指标。不同于以往主要聚焦于设计复杂精巧算法的研究，本文在数值实验中意外发现，朴素的贪婪算法展现出了最优的样本复杂度，成为解决此类大规模问题的一种重要选择。为理解这一反直觉现象，本文对贪婪算法的运行机制进行了系统分析，发现其采样过程表现出一种边界跨越特性。基于此发现，本文推导出贪婪算法在渐进准确度上的理论下界，并进一步证明了其具有样本复杂度最优性。此外，本文提出了一类广义贪婪算法，在保留样本复杂度最优性的同时，可更高效地求解大规模选择排序问题。

本文通过发现贪婪算法具有样本复杂度最优性这一反直觉的现象，不仅揭示了大规模选择排序问题与传统中小规模问题之间存在本质的区别，也为求解大规模问题开辟了全新的研究思路。同时，本文突破了对贪婪算法的传统认知，系统地分析了其内在采样机制，从理论上揭示了其具有高效性的根本原因。这一研究不仅为仿真优化领域提供了全新的理论基础，还为设计高效算法提供了重要的实践指导，具有一定的学术价值与广阔的应用前景。