Computational and Algebraic Aspects of Convexity

We would like to take this opportunity to express our gratitude to the 2012 Informs Computing Society Prize Committee, which was chaired by Pascal Van Hentenryck and included Daniel Bienstock and Dorit Hochbaum. Thank you Pascal, Dan, and Dorit for this very kind distinction. It is a great honor to receive this prize.

The ICS Prize was awarded for our work in [4], [5], [6] on the study of some very basic questions about convexity. The first paper [4] studies the computational complexity of recognizing convexity of functions and sets in polynomial optimization. The second and third papers [5], [6] are on an algebraic relaxation for convexity, known as sum-of-squares-convexity (sos-convexity), which has links to semidefinite programming and plays a notable role in the emerging field of convex algebraic geometry [9]. Some of the results, we believe, turned out to be interesting|our complexity paper answered an open question of Naum Shor from 1992; our study of sos-convexity revealed an unforeseen connection with a classical result of Hilbert in real algebraic geometry. We welcome your feedback and hope that you also find some aspects of the work interesting. A brief description of the main contributions follows with more details to be found in references mentioned above or in [1].