| |
Maximum Entropy
Sampling
Jon Lee
IBM T.J. Watson Research Centre
Yorktown Heights, NY
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
with applications to spatial 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 optimzation (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. |
