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.