HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
IMA Annual Program Year Workshop
Optimization and Control
January 16-20, 2007

Dimitris BertsimasMassachusetts Institute of Technology
J. William HeltonUniversity of California, San Diego
Jean LasserreCentre National de la Recherche Scientifique (CNRS)
Mihai PutinarUniversity of California
Group Photo

In the last decade there have been several exciting new developments in continuous, discrete, and dynamic optimization using ideas and concepts originated in algebraic geometry. 

Starting in the early 1990s with the work of Conti and Traverso on toric ideals, algebraic-geometric methods have suggested intriguing new approaches to integer programming, with sustained efforts in this direction appearing every year. More recently, new relaxations have been proposed for general polynomial optimization problems over polynomial inequalities. Note that this class of problems includes 0-1 discrete optimization as a special case. Using sums of squares decompositions from real algebraic geometry and semidefinite optimization as the computational tool, several researchers (Lasserre, Parrilo and Shor) have presented strong relaxations for these problems that improve and unify earlier bounds. By their generality, these techniques have found applications in several different areas; the differential inequalities appearing in dynamical systems and control theory being a prime example. On the stochastic side, an important class of moment problems that arise in many areas of mathematics, operations research, probability theory and finance can be formulated and effectively solved using real algebraic geometry methods and semidefinite programming as the computational tool. The suitability of the algebraic geometry approach in optimization has been newly illustrated by the recent complete characterization by Helton and Vinnikov of two-dimensional semialgebraic sets representable as the feasible set of semidefinite programs, a problem with important consequences in applications such as robust control theory. 

Other application areas include enumeration problems, equilibrium problems in game theory, options pricing in financial economics, and robust optimization. It is only fair to say that techniques originally thought to be of interest only for the algebraic geometry community have led to exciting new results in optimization, control theory, finance and economics and have had a decisive impact so far. 

Anticipating even more progress, as evidenced by the current level of interest and activity, we are hoping that a workshop in this area bringing together both the people who develop theorems in algebraic geometry (for instance, Brion, Putinar, Schmü and the researchers who use them can facilitate progress in this interface and lead to further exciting new developments and collaborations.


Connect With Us: