Jeff Linderoth, University of Wisconsin, Madison

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. 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)