Extended-variable relaxations for the constrained generalized maximum-entropy sampling problem

Gabriel Ponte; Kurt Anstreicher; Marcia Fampa; Jon Lee

doi:10.48550/arxiv.2605.03959

Back

Extended-variable relaxations for the constrained generalized maximum-entropy sampling problem

Preprint

Open access

Extended-variable relaxations for the constrained generalized maximum-entropy sampling problem

Gabriel Ponte, Kurt Anstreicher, Marcia Fampa and Jon Lee

ArXiv.org

Cornell University

05/05/2026

DOI: 10.48550/arxiv.2605.03959

Files and links (1)

url

https://doi.org/10.48550/arxiv.2605.03959View

Preprint (Author's original) This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

The constrained generalized maximum-entropy sampling problem (CGMESP) is to select an order-s principal submatrix from an order-n covariance matrix, subject to some linear side constraints, so as to maximize the product of its t greatest eigenvalues, 0 < t <= s <n. GMESP refers to the version with no side constraints. Introduced more than 25 years ago, CGMESP is a natural generalization of two fundamental problems in statistical design theory: (i) constrained maximum-entropy sampling problem (CMESP); (ii) binary D-optimality (D-Opt). In the general case, it can be motivated by a selection problem in the context of principal component analysis (PCA). We present novel non-convex extended variable formulations for CGMESP. Using these formulations as points of departure, we present, first non-convex and then convex, continuous relaxations for CGMESP. We demonstrate many relations between different upper bounds for CGMESP, including upper bounds from the literature and our new upper bounds. We investigate the behavior of our relaxations related to the constraints linking the natural variables with the extended variables. We propose and investigate a generalized scaling technique for bound improvement. In the context of branch-and-bound, we determine the better of two natural branching techniques for fixing variables to zero. Finally, we present numerical experiments illustrating the value of our methods.

Mathematics - Optimization and Control

Details

Title: Subtitle: Extended-variable relaxations for the constrained generalized maximum-entropy sampling problem
Creators: Gabriel Ponte
Kurt Anstreicher
Marcia Fampa
Jon Lee
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2605.03959
ISSN: 2331-8422
Publisher: Cornell University; Ithaca, New York
Language: English
Date posted: 05/05/2026
Academic Unit: Business Analytics
Record Identifier: 9985159131202771

Metrics

1 Record Views