Speaker

Pablo Parrilo

ETH, Zurich

Part 1: Sum of squares and semidefinite programming

1. Computing sum of squares decomposition via SDP
2. Sum of squares programs: optimizing over affine families of polynomials, under SOS constraints
3. Polya's theorem and matrix copositivity
4. Theorems of alternatives: Farkas, Nullstellensatz, Positivstellensatz.
5. Proving emptiness of semialgebraic sets via the Positivstellensatz. The links with optimization.
6. Interpretations: convex relaxations, liftings, proof systems.

Part 2: Exploiting structure for numerical computation

1. Why exploit structure?
2. Sparsity and Newton polytopes.
3. Equality constraints: SOS on quotient rings. The zero dimensional case.
4. Symmetric polynomials, and connections with representation and invariant theory.
5. Numerical aspects.
6. Applications, additional structures and SOSTOOLS software.