The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a prespecified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on the concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of [27] and a recent upper bound proposed by [24]. Furthermore, we provide theoretical guarantees that quantify how much the proposed augmented factorization bound improves the two existing ones and establish sufficient conditions for when the improvement is strictly attained. These results allow us to refine the celebrated approximation bounds for the two approximation algorithms of MESP. Motivated by the strength of the augmented factorization bound, we develop a variable fixing logic for MESP from a primal perspective. Finally, our numerical experiments demonstrate that the augmented factorization bound achieves smaller integrality gaps and fixes more variables than the tightest bounds in the MESP literature on most benchmark instances, with the improvement being particularly significant when the condition number of the covariance matrix is small.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Augmented Factorization Bound for Maximum-Entropy Sampling

  • Yongchun Li

摘要

The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a prespecified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on the concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of [27] and a recent upper bound proposed by [24]. Furthermore, we provide theoretical guarantees that quantify how much the proposed augmented factorization bound improves the two existing ones and establish sufficient conditions for when the improvement is strictly attained. These results allow us to refine the celebrated approximation bounds for the two approximation algorithms of MESP. Motivated by the strength of the augmented factorization bound, we develop a variable fixing logic for MESP from a primal perspective. Finally, our numerical experiments demonstrate that the augmented factorization bound achieves smaller integrality gaps and fixes more variables than the tightest bounds in the MESP literature on most benchmark instances, with the improvement being particularly significant when the condition number of the covariance matrix is small.