University of Houston Cullen College of Engineering

Department Event / Seminar

[IE] Perspectives on Integer Programming in Sparse Optimization


Friday, November 2, 2018 - 1:00pm to 2:00pm


D3 W122, College of Engineering, University of Houston

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 reform-ulation 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.