Jon Lee, University of Michigan

Abstract

The maximum-entropy sampling problem (MESP) is to select a subset, of given size s, from a set of n correlated Gaussian random variables, so as to maximize the differential entropy. If C is the covariance matrix, then we are simply seeking to maximize the determinant of an order-s principal submatrix. A key application is for the contraction of an environmental-monitoring network. MESP sits within the intersection of optimization and data science, and so it has attracted a lot of recent attention. The problem is NP-hard, and there have been algorithmic attacks aimed at exact solution of moderate-sized instance for three decades. It is a fascinating problem from the perspective of integer nonlinear optimization, as it does not fit within a framework that is successfully attacked via available general-purpose paradigms. I will give a broad overview of algorithmic work, concentrating on the many useful techniques related to various convex relaxations.

[Video]