ACO The ACO Seminar (2022–2023)

February 16, 3:30pm, Wean 8220
Kevin Shu, Georgia Tech
Sparse Quadratic Programs via Polynomial Roots


We will consider the problem of optimizing a quadratic function subject to quadratic constraints, in addition to a sparsity constraint that requires that solutions have only a few nonzero entries. Such problems include sparse versions of linear regression and principal components analysis. We'll see that the solutions to these problems are intimately related to the roots of certain polynomials that generalize the determinant, which arose from the study of hyperbolic polynomials. We'll also describe a fast algorithm for such problems, which performs well in practical situations. Connections to semidefinite programming and volume sampling will be mentioned.

Back to the ACO home page Back to the ACO Seminar schedule