Technical Note-Masking Anstreicher's linx Bound for Improved Entropy Bounds

• 成果类型: Article
• 署名作者: Chen, Zhongzhu; Fampa, Marcia; Lee, Jon
• 署名单位: University of Michigan System; University of Michigan; Universidade Federal do Rio de Janeiro
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2324
• 发表日期: 2024
• 关键词: differential entropy; maximum-entropy sampling; environmental monitoring; nonlinear combinatorial optimization; nonlinear integer optimization; convex relaxations

摘要

The maximum-entropy sampling problem is the NP-hard problem of maximizing the (log) determinant of an order-s principal submatrix of a given order n covariance matrix C. Exact algorithms are based on a branch-and-bound framework. The problem has wide applicability in spatial statistics and in particular in environmental monitoring. Probably the best upper bound for the maximum empirically is Anstreicher???s scaled ???linx??? bound. An earlier methodology for potentially improving any upper-bounding method is by masking, that is, applying the bounding method to C ??? M, where M is any correlation matrix. We establish that the linx bound can be improved via masking by an amount that is at least linear in n, even when optimal scaling parameters are used. We also extend an earlier result that the linx bound is convex in the logarithm of a scaling parameter, making a full characterization of its behavior and providing an efficient means of calculating its limiting behavior in all cases.