McMaster University

For registration information
please contact:

Janet Delsey
905-525-9140, ext. 24910



4th Annual McMaster Optimization Conference: Theory and Applications

July 28-30, 2004

    McMaster University, Hamilton, ON Canada

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.

Contact Us | Legal & Privacy Policy