October 08, 2019, 2:30 PM - 3:15 PM
Auditorium (Amphitheatre Banque Nationale)
Click here for map.
Jeff Linderoth, University of Wisconsin, Madison
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. The most novel contribution of this work is a demonstration that extensions of the perspective reformulation can lead to algorithms that are *equivalent* to popular, modern, sparsity-inducing non-convex regularizations in variable selection.
Based on joint work with Hongbo Dong (Washington State Univ. ), Oktay Gunluk (IBM), and Kun Chen (Univ. Connecticut)