Sanjay Mehrotra (left), Pablo Parrilo, and Dimitris Bertsimas.
The 2013 Farkas prize is awarded to Pablo Parrilo for his significant and fundamental contributions to the field of optimization. His work builds new bridges between semidefinite optimization and real algebraic geometry, and expands the impact and applications of optimization to new areas of engineering, control theory, and recently machine learning. Parrilo's contributions span areas as diverse as game theory and quantum computation.
In his PhD thesis, building on prior fundamental work by N.Z. Shor and Y. Nesterov, Parrilo showed that semidefinite optimization can be combined with Positivstellensaatze results (in reference to the seminal work of Hilbert around 1900) of real algebraic geometry to solve polynomial optimization problems with arbitrary accuracy. Parrilo has continued to produce a large number of high quality scientific papers at the interface of algorithmic algebra and optimization: an approach for using invariant theory for exploiting symmetry in algebraic problems (with Gatermann); proof of the Lax conjecture (posed in 1958) about determinantal representations of hyperbolic polynomials in three variables (with Lewis and Ramana); a polynomial time approximation scheme for minimizing forms on the simplex (with de Klerk and Laurent); extending Lovasz's theta body of the stable set polytope to convex hulls of arbitrary algebraic varieties (with Gouveia and Thomas); and a complete characterization of the gap between convexity and SOS-convexity, analogous to Hilbert's seminal result for positive polynomials (with Ahmadi).
Dimitris Bertsimas (Chair), George Nemhauser, Yurii Nesterov, Yinyu Ye.