Grad Student Seminar: Gabor Pataki, Bryan Davis

Gabor Pataki
UNC-Chapel Hill

Bad semidefinite programs with short proofs, and elementary linear algebra

Semidefinite programs (SDPs) – optimization problems with linear constraints, linear objective, and semidefinite matrix variables –  are some of the most useful, versatile, and pervasive optimization problems to emerge in the last 30 years. They find applications in combinatorial optimization, machine learning, and statistics, to name just a few areas.

Unfortunately, SDPs often behave pathologically: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are theoretically interesting and numerically often difficult, or impossible to solve. Yet, the pathological SDPs in the literature look strikingly similar, and our recent paper (Pataki: Bad semidefinite programs: they all look the same, SIAM J. Opt 2017)) explained why: it characterized pathological semidefinite systems by certain {\em excluded matrices}, which are easy to spot in all published examples.

Here we give short and elementary proofs of these results using mostly techniques from elementary linear algebra. Our main tool is a standard (canonical) form of semidefinite systems, from which their pathological behavior is easy to verify. The standard form is constructed in a surprisingly simple manner, using mostly elementary row operations inherited from Gaussian elimination.

URL of the paper is: https://arxiv.org/abs/1709.02423

Bryan Davis
Indeed

SEM Portfolio Optimization

This talk will introduce the basic format and mechanisms of Search Engine Marketing and introduce the business motivations for its utilization. It will then delve into ongoing work at Indeed aimed at optimizing the distribution of budget over different queries, and will highlight the different modeling and engineering components of this work.