We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem.
- Authors
Chen, Zhongzhu; Fampa, Marcia; Lee, Jon
- Abstract
Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov and of Li and Xie for the NP-hard constrained maximum-entropy sampling problem (CMESP). We demonstrate that this factorization bound is invariant under scaling and independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP, and we demonstrate that its ability to fix is independent of the factorization chosen. We report on successful experiments with a commercial nonlinear programming solver. We further demonstrate that the known "mixing" technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP and with the "linx bound" of Anstreicher. History: Andrea Lodi, area editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3] and the Air Force Office of Scientific Research [Grant A9550-19-1-0175].
- Subjects
MAXIMUM entropy method; NONLINEAR programming; COVARIANCE matrices; OFFICES; FACTORIZATION; AIR forces
- Publication
INFORMS Journal on Computing, 2023, Vol 35, Issue 2, p368
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2022.1264