LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization and Difference of Convex Programming

Wednesday, September 20, 2017 - 3:00pm

Event Calendar Category

Other LIDS Events

Speaker Name

Georgina Hall


Princeton University

Building and Room Number



How can we prove that a set of polynomial equations and inequalities is infeasible? How can we write a multivariate polynomial as a difference of two convex polynomials? Though these questions may seem unrelated, they have at least two features in common: they both appear in a variety of applications, and can be answered using sum of squares techniques and semidefinite programming. In this talk, we present new algorithms for these two problems that do not rely on semidefinite programming, but instead use linear programming, or second-order cone programming, or are altogether free of optimization.


Georgina Hall is a final-year graduate student and a Gordon Wu fellow in the department of Operations Research and Financial Engineering at Princeton University, where she is advised by Professor Amir Ali Ahmadi. She was the valedictorian of Ecole Centrale, Paris, where she obtained a B.S. and an M.S., in 2011 and 2013 respectively. Her interests lie in the design of convex relaxations for NP-hard problems, particularly those arising in polynomial optimization. She is the recipient of the Médaille de l’Ecole Centrale from the French Académie des Sciences and was chosen for the 2017 Rising Stars in EECS workshop at Stanford. Her paper “DC decomposition of nonconvex polynomials using algebraic techniques” is the recipient of the 2016 INFORMS Computing Society Prize for Best Student Paper. She has also been the recipient of a number of teaching awards, including the Princeton University's Engineering Council Teaching Award, the university-wide Excellence in Teaching Award of the Princeton Graduate School, and the 2017 Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers.

URL: https://scholar.princeton.edu/ghall/home