Mixing convex-optimization bounds for maximum-entropy sampling

• 成果类型: Article
• 署名作者: Chen, Zhongzhu; Fampa, Marcia; Lambert, Amelie; Lee, Jon
• 署名单位: University of Michigan System; University of Michigan; Universidade Federal do Rio de Janeiro; heSam Universite; Conservatoire National Arts & Metiers (CNAM)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01588-w
• 发表日期: 2021
• 页码: 539-568
• 关键词: relaxations

摘要

The maximum-entropy sampling problem is a fundamental and challenging combinatorial-optimization problem, with application in spatial statistics. It asks to find a maximum-determinant order-s principal submatrix of an order-n covariance matrix. Exact solution methods for this NP-hard problem are based on a branch-and-bound framework. Many of the known upper bounds for the optimal value are based on convex optimization. We present a methodology for mixing these bounds to achieve better bounds.