Convex Algebraic Geometry (10w5007)

Arriving in Banff, Alberta Sunday, February 14 and departing Friday February 19, 2010

Organizers

(Universitat Konstanz)

(University of California at Berkeley)

(University of Washington)

Objectives

The main objectives of this workshop are to explore different mathematical and computational approaches to understanding convexity in real algebraic geometry. More concretely, we hope to target the following directions: (1) the role of semidefinite programming and sums of squares in convex algebraic geometry, (2) the use of geometry, algebra and combinatorics in the study of convex hulls of real algebraic varieties, (3) how to exploit sparsity and graphical structure in the defining data, (4) the use of numerical polynomial optimization in convex real algebraic geometry, (5) deformations and variation of parameters in this context, and (6) the interplay with classical algebraic geometry over the complex numbers. The idea is to focus on the development of a comprehensive theory and practical new algorithms for convex sets defined by polynomial inequalities. Specific problems and techniques include the formulation of semidefinite descriptions of convex hulls of real algebraic varieties, determinantal representations of hyperbolic polynomials, sparse polynomials and their symmetries, tropical geometry and homotopy techniques, and geometric programming.

Although a number of the questions in convex algebraic geometry can be described in relatively elementary language, it appears that they cannot be satisfactorily addressed using the current knowledge in convex, polyhedral and algebraic geometry. New mathematics, and the associated computational methods, need to be developed. In recent years there have been substantial advances in the core theory of semidefinite programming, sum of squares, and their associated relaxations. These methods have enabled the application of convexity-based techniques to large-scale, nonconvex optimization problems, once thought to be completely out of reach. Secondly, there have been significant connections with other areas of mathematics, that have illuminated and deepened the interaction between real algebraic questions and convexity. Among them, we mention operator theory, model theory, tropical geometry, probability theory, etc. Some of these connections, and their classical roots, are described in the recent survey by Helton and Putinar. Finally, on the computational side, there are now much improved hardware capabilities, wide
availability of computational resources, and very efficient numerical linear algebra packages (e.g., BLAS, LAPACK, and ATLAS). The possibility of performing non-linear algebraic computations, but without having to pay the big fixed costs associated with symbolic manipulation, is one of the best arguments why the mathematical techniques we hope to explore need to be much better understood. For all these reasons, the time is right for a meeting on this topic.

Bill Helton, Jiawang Nie, Pablo Parrilo, Bernd Sturmfels and Rekha Thomas have been awarded a Focussed Research Group grant for 2008-11 from the U.S. National Science Foundation for a project titled ``Semidefinite optimization and convex algebraic geometry''. This workshop is being proposed as part of the activities around this research effort. A web page can be found at:

http://www.math.washington.edu/~thomas/frg/frg.html

The list of participants come from various backgrounds and do not naturally interact otherwise except perhaps in small groups. The areas of expertise span optimization, real algebraic geometry, commutative algebra, computational mathematics, combinatorics, polyhedral geometry, complexity and algorithms. While the applied sides of these questions are relevant to an even larger group of people, our aim here is to focus on the theoretical aspects of convexity in real algebraic geometry to focus the meeting on foundational questions.