« search calendars« CRM/DIMACS Workshop on Mixed-Integer Nonlinear Programming

« Perspectives on Integer Programming in Sparse Optimization

Perspectives on Integer Programming in Sparse Optimization

October 08, 2019, 2:30 PM - 3:15 PM


Auditorium (Amphitheatre Banque Nationale)

HEC Montreal

Cote-Sainte-Catherine Building

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)