Maximum-Entropy Sampling
Jon Lee, IBM T.J. Watson Research Center
The maximum-entropy sampling problem is to choose a most
informative
subset, of prespecified cardinality, from a finite set of random
variables. This is a
fundamental problem in statistics (in the design of experiments) with
applications to
spatial monitoring (in particular, environmental monitoring). I will
describe the problem,
its variations, and applications in more detail. The problem is NP-Hard,
and our focus is on
branch-and-bound algorithms to find optimal solutions to moderate-sized
instances. I will
describe heuristics to generate lower bounds and the branching framework,
but the more
interesting part of the work involves different methods to obtain upper
bounds. Techniques
involve:
(i) exploitation of determinant inequalities of Fischer and
Oppenheim,
(ii) eigenvalue
inequalities and nonconvex, nonsmooth, semidefinite programming,
(iii) convex programming,
(iv) combinatorial optimization (eg., b-matching and local-search), and
(v) Lagrangian relaxation and nonsmooth, convex programming.
New work that I will be
highlighting is joint with Kurt Anstreicher.
Chemnitz Workshop
Last modified: Thu Jul 8 20:00:00 CEST 2004