Technical Note—Masking Anstreicher’s linx Bound for Improved Entropy Bounds

Zhongzhu Chen (), Marcia Fampa () and Jon Lee ()
Additional contact information
Zhongzhu Chen: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Marcia Fampa: Programa de Engenharia de Sistemas e Computação, The Alberto Luiz Coimbra Institute for Graduate Studies and Research in Engineering (COPPE), Universidade Federal do Rio de Janeiro, Rio de Janeiro RJ 21941-972, Brazil
Jon Lee: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2024, vol. 72, issue 2, 591-603

Abstract: 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.

Keywords: Optimization; differential entropy; maximum-entropy sampling; environmental monitoring; nonlinear combinatorial optimization; nonlinear integer optimization; convex relaxations (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2324 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:2:p:591-603

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().