Abstract:  Algorithms to solve mixed integer linear programs have made incredible progress in the past 20 years. Key to these advances has been a mathematical analysis of the structure of the set of feasible solutions. We argue that a similar analysis is required in the case of mixed integer quadratic programs, like those that arise in sparse optimization in machine learning. One such analysis leads to the so-called perspective relaxation, which significantly improves solution performance on separable instances. Extensions of the perspective reformulation can lead to algorithms that are equivalent to some of the most popular, modern, sparsity-inducing non-convex regularizations in variable selection, such as the minimax concave penalty.

Based on joint work with Hongbo Dong (Washington State Univ.), Oktay Gunluk (IBM), and Kun Chen (Univ. Connecticut).

Bio:  Jeff Linderoth is the Harvey D. Spangler Professor and the chairperson of the department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Dr. Linderoth received his Ph.D. degree from the Georgia Institute of Technology in 1998. He was previous employed in the Mathematics and Computer Science Division at Argonne National Laboratory, with the optimization-based financial products firm of Axioma, and as an Assistant Professor at Lehigh University. His awards include an Early Career Award from the Department of Energy, the SIAM Activity Group on Optimization Prize, and the INFORMS Computing Society (ICS) Prize. In 2016, he was elected to membership as an INFORMS Fellow.