Generalized Scaling for the Constrained Maximum-Entropy Sampling Problem

Zhongzhu Chen, Marcia Fampa, Jon LeeACDA 2023 · DOI

TL;DR

This paper introduces "generalized scaling" (g-scaling) as a novel technique to improve existing bounds for the constrained maximum-entropy sampling problem (CMESP). By applying g-scaling, the authors demonstrate significant improvements in the tightness of these bounds and the ability to fix more variables in branch-and-bound algorithms, particularly for CMESP.

What Problem Does This Paper Address?

The maximum-entropy sampling problem (MESP) is a crucial task in experimental design, aiming to select a subset of sensors to maximize the differential entropy of a Gaussian random vector. The constrained version (CMESP) adds practical limitations like budgets or geographical constraints. Solving CMESP is generally NP-hard, and researchers often rely on continuous relaxations to derive upper bounds, which are then used in branch-and-bound (B&B) algorithms. A common technique to strengthen these bounds is "scaling," where the objective function is modified by multiplying the covariance matrix by a scaling factor. However, this standard "ordinary scaling" (o-scaling) has limitations. This paper addresses the question of whether a more general form of scaling, "generalized scaling" (g-scaling), can provide further improvements over o-scaling for CMESP.

Methods

The core contribution is the introduction and analysis of generalized scaling (g-scaling) for three specific convex relaxations of CMESP: the BQP bound, the linx bound, and the DDFact bound. G-scaling involves using a vector of scaling factors ($\Upsilon$) instead of a single scalar, allowing for more flexible modifications of the covariance matrix. The authors prove that the g-scaled versions of the BQP and linx bounds are convex in the logarithm of the scaling vector. This convexity is key, as it allows for efficient optimization of the scaling vector using standard quasi-Newton methods like BFGS. For the DDFact bound, they establish differentiability results that also support efficient optimization. They also provide theoretical results showing that g-scaling can improve the DDFact bound for CMESP, a feat that o-scaling cannot achieve.

Datasets

The paper uses benchmark instances of MESP with covariance matrices of sizes $n=63, 90, 124,$ and $300$. For CMESP, they generated five side constraints for each instance, as no standard benchmark datasets for these constraints exist. The right-hand sides of these constraints were carefully chosen to ensure that the best known solutions to the MESP instances were violated by at least one constraint.

Key Insights and Ideas

  • G-scaling offers a more powerful tool: The paper demonstrates that generalized scaling (using a vector of scaling factors) can provide greater improvements than ordinary scaling (using a single scalar factor) for CMESP.
  • Convexity is key for tractability: Proving that the g-scaled bounds are convex in the log of the scaling vector is crucial. This mathematical property enables the efficient use of powerful optimization algorithms (like BFGS) to find the optimal scaling parameters.
  • DDFact bound benefits significantly: G-scaling is shown to improve the DDFact bound for CMESP, a result that o-scaling could not achieve. This highlights the novel capabilities of g-scaling.
  • Improved variable fixing: The enhanced bounds achieved through g-scaling directly translate to a greater ability to fix variables to their binary values (0 or 1) within branch-and-bound algorithms, leading to more efficient problem solving.
  • MESP vs. CMESP: While g-scaling shows promise for CMESP, the paper suggests it might not be as beneficial for the unconstrained MESP, hinting at the importance of the added constraints.

Key Results

  • Improved Upper Bounds: G-scaling consistently leads to tighter upper bounds for the linx bound in MESP and for all tested bounds (linx, DDFact, and complementary DDFact) in CMESP, especially when side constraints are present.
  • Increased Variable Fixing: For CMESP, g-scaling significantly increases the number of variables that can be fixed at the root node of a B&B algorithm. For instance, for $n=124$, g-scaling led to fixing 33 variables compared to 9 with o-scaling, a 266.67% improvement.
  • Efficiency of Optimization: The convexity results allow for efficient optimization of the scaling vector using quasi-Newton methods, making g-scaling practical for use in B&B algorithms.
  • Theoretical Guarantees: The paper provides theoretical proofs for the convexity of g-scaled BQP and linx bounds and differentiability results for the g-scaled DDFact bound.

Limitations and Future Work

  • MESP vs. CMESP: The paper notes that g-scaling's benefit for the unconstrained MESP is less pronounced compared to CMESP. Thm. 5.iv provides a partial theoretical result suggesting g-scaling might not help the DDFact bound for MESP.
  • NLP Bound: The authors mention that another convex relaxation, the "NLP bound," is more challenging to analyze with g-scaling, suggesting this as a future research direction.
  • Practical Implementation: While the paper demonstrates the effectiveness of g-scaling, future work will focus on implementing it efficiently within a B&B algorithm, including strategies for warm-starting scaling vector optimization for child nodes.
  • Further Exploration of DDFact for MESP: The question of whether g-scaling can help the DDFact bound for MESP remains open, despite some theoretical indications.

Summary updated

BibTeX
@inproceedings{chen2023generalized,
  author = {Zhongzhu Chen and Marcia Fampa and Jon Lee},
  title = {{Generalized Scaling for the Constrained Maximum-Entropy Sampling Problem}},
  booktitle = {ACDA},
  year = {2023},
  doi = {10.1137/1.9781611977714.10},
}
Figure