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].

By: Amir Ali Ahmadi

Published in: RC25395 in 2013


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .