Oberwolfach Seminar

New trends in algorithms for real algebraic geometry

November 23--27 2009

Presentation

Algorithms in real algebraic geomety enjoy currently a quick development in various directions.

The aim of the seminar is to introduce the participants to a variety of  newly developed  methods for algorithms in real algebraic geometry, linking the topic to several other fields of pure and applied mathematics.

The lecturers will base their talks on available documents: survey papers, recent publications and will make every effort to be accessible to non specialists.

Saugata Basu, (Purdue), "Algorithmic semialgebraic topology"

 In these lectures, we will describe quantitative results on the topological complexity of semi-algebraic sets,  as well as efficient algorithms for computing topological invariants of semi-algebraic sets (such as the number of connected components, the Euler-Poincar\'e characteristic, all Betti numbers etc).

We will develop the necessary tools from algebraic topology (such as simplicial homology theory,
Mayer-Vietoris sequence, spectral sequences etc.) as part of the course.

We will also discuss extensions of the quantitative results to the more  general setting of o-minimal structures.

Finally, we will discuss applications in discrete and computational geometry, as well as in  computational complexity theory.  

Monique Laurent, (CWI, Amsterdam), "Sums of squares, moment matrices and optimization over polynomials"

Polynomial optimization deals with  minimizing a multivariate polynomial over a basic closed semi-algebraic set.
While easy to solve when all polynomials are linear (via linear programming), the problem becomes hard as soon as it involves non-linear polynomials.

A natural approach is to relax the problem and to consider easier to solve,  convex relaxations. The basic idea, which goes back to work of Hilbert, is to relax non-negative polynomials by sums of squares of polynomials, a notion which can be tested efficiently (using semidefinite programming algorithms). On the dual side, one views points as (atomic) measures and one searches for efficient conditions characterizing sequences of moments of non-negative measures on the semi-algebraic set.

We will present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions, and illustrate the method on several problem classes.  

The main mathematical tools underlying these properties will be reviewed: In particular,
(1) results from real algebraic geometry about sums of squares representations for positive polynomials,
(2) results from moment theory dealing with atomic measures and finite rank moment matrices,
(3) results from commutative algebra for solving systems of polynomial equations.

Marie-Francoise Roy, (Rennes), "Certificates of positivity"

A certificate of positivity is an algebraic expression proving that a given polynomial P is positive. For example, writing P as a sum of squares is a certificate of positivity for P.

Artin proved that every positive polynomials is a sum of squares, giving thus a positive answer to Hilbert 17-th problem. His proof, based on Zorn's lemma, is highly non constructive and finding explicitly the sum of squares is a very difficult task. The method we use consists in proving algorithmically that the set where the polynomial is negative is empty, and transforming this algorithmic proof into an algebraic identity. We shall present what is currently known on effective Hilbert 17-th problem, insisting on the fact that the methods are valid in a general real closed field and provide uniform bounds (the degrees in the output do not depend on the bitsize of the input coefficients, but only in the degree and number of variables).

Other certificates of positivity (on the positive orthant, or on the simplex) are based on results by Polya and Bernstein. Berstein polynomials, for example, are positive on the simplex, and a positive combination of them is positive as well. A partial reciprocal is true,  by ncreasing the degree of the Bernstein, or by subdividing the simplex. This gives two different kinds of certificates, the approach by subdivision being much more efficient.
These certificates are not uniform, since the size of the certificate output depends on the bitsize of the coefficients, and Polya and Bernstein results are not valid in a general real closed field.



Frank Sottile, (Texas A&M), "Numerical real algebraic geometry"


Numerical homotopy continuation gives efficient and naturally parallel algorithms to find all complex solutions to a system of polynomial equations.  The real solutions are obtained by sifting the complex solutions, selecting those with small imaginary part.

In contrast, the Khovanskii-Rolle algorithm is a different numerical continuation algorithm that only
follows real solutions and is naturally parallel. This new continuation algorithm is based on the proof of the current best bounds for the number of real solutions to a system of sparse polynomial equations, including the gale dual transformation of polynomial systems.

These lectures will discuss numerical homotopy continuation, Gale duality, the new fewnomial bounds, and then present the Khovanskii-Roll continuation algorithm. Augmenting the lectures will be computer exercises, challenges, and open problems.

Organization

16 hours of lectures (four hours per lecturer)

Problem sessions will be organized

Mini-projects (some including the use of software) will be proposed

Note that Oberwolfachsseminars are for young researchers (pre- and post-doc)

Deadline 15 October
Apply directly to Oberwolfach (go to http://www.mfo.de/ and then choose Oberwolfach Seminars in the left menu).