TALK    Perspectives on Integer Programming in Sparse Optimization

Date & Time:

Tuesday, July 16, 2019; 12:00 PM

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. Based on joint work with Hongbo Dong (Washington State Univ. ), Oktay Gunluk (IBM), and Kun Chen (Univ. Connecticut).

Speaker:

Prof. Jeff Linderoth
University of Wisconsin-Madison

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, and previously held positions at Argonne National Lab, Axioma, Inc., and Lehigh University. His awards include numerous best paper awards, an Early Career Award from the Department of Energy, the SIAM Activity Group on Optimization Prize, and the INFORMS Computing Society (ICS) Prize. He 2016, he was elected to membership as an INFORMS Fellow.

MERL Host:

Arvind Raghunathan

Research Areas:

Machine Learning, Optimization