Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees
Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees
复制标题
DOI：
10.1287/opre.2023.2488
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
本文研究了一个经典的最大熵抽样问题，即从协方差矩阵中选择一个给定大小的信息量最大的主子矩阵。MESP已广泛应用于医疗保健、电力系统、制造业和数据科学等多个领域。通过研究其拉格朗日对偶和原始特征，我们得到了一个新的凸整数规划MESP，并表明其连续松弛产生一个近最优解。这些结果促使我们研究一种有效的采样算法，并给出了它的近似界，改进了文献中最著名的界。然后，我们提供了一个有效的确定性实现的采样算法具有相同的近似界。通过开发新的数学工具的奇异矩阵和分析提出的凸整数规划的拉格朗日对偶，我们研究了广泛使用的局部搜索算法，并证明了它的第一个已知的近似界的MESP。证明技术进一步启发我们与一个有效的实现本地搜索算法。我们的数值实验表明，这些近似算法可以有效地解决中型和大型的情况下，近最优性。我们提出的算法被编码并作为开源软件发布。最后，我们将分析扩展到A-最优MESP（A-MESP），其目标是最小化所选主子矩阵的逆的迹。
This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP. The proof techniques further inspire us with an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-sized and large-scale instances to near-optimality. Our proposed algorithms are coded and released as open-source software. Finally, we extend the analyses to the A-Optimal MESP (A-MESP), where the objective is to minimize the trace of the inverse of the selected principal submatrix.