On Algorithmic Advances for Maximum-Entropy Sampling

Abstract

The maximum-entropy sampling problem (MESP) is a fundamental and challenging combinatorial-optimization problem, at the intersection of information theory, machine learn- ing, and optimization. The goal is to find a maximum-entropy subset of s random variables, from a universe of n correlated Gaussian random variables, which is a means of choosing the s-subset with maximum information. MESP finds application in experimental design (Shewry and Wynn, 1987), spatial statistics (Zidek, Sun, and Le, 2000), financial portfolio selection (Bera and Park, 2008), feature selection (Song and Li`o, 2010), active learning (Qiu, Miller, and Kesidis, 2016), and many references in (Fampa and Lee, 2022, Chapter 4). MESP is an NP-hard problem. Research in this area often focuses on exact algorithms within a branch-and-bound (B&B) framework, as introduced by (Ko, Lee, and Queyranne, 1995). This framework involves the implicit enumeration of potential solutions while main- taining upper and lower bounds on the optimal value of MESP to efficiently discard non- optimal solutions. Consequently, the solution speed of the B&B method heavily relies on the tightness of these bounds. In this dissertation, we propose enhanced upper- and lower- bounding techniques to expedite the branch-and-bound framework when applied to MESP, facilitating the handling of large-size instances. Our approach includes a “mixing” method- ology for combining multiple convex-relaxation upper bounds of MESP to derive superior bounds. We also present a generalization of upper bounds from (Nikolov, 2015; Li and Xie, 2023), which turns out to be the best for many instances. Moreover, we introduce a “general scaling” technique for reducing the integrality gap further, compared to one of the most pow- erful techniques, “scaling” (Anstreicher, Fampa, Lee, and Williams, 1996). We also address the theoretical void in the “masking” technique, a promising method without much explo- ration. Additionally, we introduce an efficient, limited-memory quasi-Newton algorithm for finding nearly optimal masks.