This monograph presents a comprehensive treatment of the maximum-entropy sampling problem (MESP), which is a fascinating topic at the intersection of mathematical optimization and data science. The text situates MESP in information theory, as the algorithmic problem of calculating a sub-vector of pre-specificed size from a multivariate Gaussian random vector, so as to maximize Shannon's differential entropy. The text collects and expands on state-of-the-art algorithms for MESP, and addresses its application in the field of environmental monitoring. While MESP is a central optimization problem in the theory of statistical designs (particularly in the area of spatial monitoring), this book largely focuses on the unique challenges of its algorithmic side. From the perspective of mathematical-optimization methodology, MESP is rather unique (a 0/1 nonlinear program having a nonseparable objective function), and the algorithmic techniques employed are highly non-standard. In particular, successful techniques come from several disparate areas within the field of mathematical optimization; for example: convex optimization and duality, semidefinite programming, Lagrangian relaxation, dynamic programming, approximation algorithms, 0/1 optimization (e.g., branch-and-bound), extended formulation, and many aspects of matrix theory. The book is mainly aimed at graduate students and researchers in mathematical optimization and data analytics.
Author(s): Marcia Fampa, Jon Lee
Series: Springer Series in Operations Research and Financial Engineering
Publisher: Springer
Year: 2022
Language: English
Pages: 205
City: Cham
Preface
Overview
Notation
Contents
The problem and basic properties
Differential entropy
The MESP and the CMESP
Hardness
A solvable case
The complementary problem
Scaling
Masks
Submodularity
Branch-and-bound
The branch-and-bound algorithmic framework for MESP
Global upper bound for early termination
Good lower bounds
Greedy
Swapping
Approximation algorithm
The branch-and-bound algorithmic framework for CMESP
Upper bounds
Spectral bounds
Unconstrained
Constrained
Integer linear optimization
An ILP-based diagonal bound for CMESP
An ILP-based partition bound for MESP
linx bound
Convexity of linx
Duality for linx
Fixing variables in linx
Computing linx and Dlinx solutions
Scaling for linx
The complementary problem of linx-gamma
Factorization bound
The Lagrangian dual of Fact
Duality for DFact
Fixing variables in DDFact
Computing DDFact and DFact solutions
Properties of the factorization bound
NLP bound
Convexity of NLP
Scaling for NLP
Good parameters for NLPgamma
Strategies to select parameters for NLPgamma
Duality and the logarithmic-barrier problem for gNLP
Fixing variables in gNLP
The logarithmic-barrier algorithm for gNLP
NLP-gamma in the branch-and-bound algorithm
BQP bound
Convexity of BQP
Duality for BQP
Fixing variables in BQP
A good feasible solution of DBQP from BQP
Scaling for BQP
Mixing bounds
The mixing framework
Optimizing the mixing parameters
Duality for mixing
Fixing variables in mix
A good feasible solution of Dmix from mix
Mixing the BQPgamma bound with the complementary BQPgamma bound
Duality for smBQP
Fixing variables in smBQP
A good feasible solution of DsmBQP from smBQP
Comparison of bounds
Environmental monitoring
The setting
MESP within statistics and optimal experimental design
MESP and environmental statistics
From raw data to covariance matrices
An example
Opportunities
Developing algorithmic advances for MESP/CMESP
Variable fixing and branch-and-bound: state of the art
Optimizing gamma for NLPgamma
Solvable cases of MESP and mask optimization
OA for CMESP
MESP/CMESP variations and cousins
Applications
Basic formulae and inequalities
Preliminary miscellany
Square matrices
Symmetric matrices
Positive definite and semidefinite matrices
References
Index
