TITLE: Quadratic Programs with On-Off Constraints

SPEAKER:  Dr. Jeff Linderoth

ABSTRACT:

We study optimization problems that involve both quadratic functional relationships between decision variables and 0-1 indicator variables that turn on and off these relationships. Problems of this class occur in many areas, including statistics, financial engineering, and engineering design. After reviewing earlier work on a reformulation technique applicable to the case when the quadratic functions are separable, we discuss on-going research aimed at attacking the non-separable case. We introduce an important set to study in this context that generalizes both the BoxQP set, studied by Burer and Letchford, and the well-known Boolean Quadric Polytope. We discuss the relative importance of families of valid inequalities for this set, and we show how one important class can be separated in polynomial time if the dimension is fixed. We conclude with computational results to demonstrate the utility of these inequalities on practical portfolio optimization instances. This is joint work with Hongbo Dong.

Bio: 

Jeff Linderoth is a Professor in the departments of Industrial and Systems Engineering and Computer Sciences (by courtesy) at the University of Wisconsin-Madison, joining both departments in 2007. Dr. Linderoth received his Ph.D. degree from the Georgia Institute of Technology in 1998. From 1998-2000, he was employed with the Mathematics and Computer Science Division at Argonne National Laboratory, and from 2000-2002, he was a Senior Consultant with the optimization-based financial products firm of Axioma Inc. Prior to joining University of Wisconsin-Madison, from 2002-2007, he was a Assistant Professor at Lehigh University, where he co-founded COR@L (the Center for Optimization Research @ Lehigh). In 1999, Dr. Linderoth was named the Enrico Fermi Scholar at Argonne National Lab. In 2002, Dr. Linderoth was a co-recipient of the SIAM/Activity Group on Optimization Prize, and in 2005 he was awarded an Early Career Development Award from the Department of Energy and an IBM Faculty Partnership award. Dr. Linderoth currently serves on the editorial boards of 4 journals.