Cours spécialisé ()

# Algebraic techniques in optimization

### Elias Tsigaridas

Contact : elias.tsigaridas à imj-prg.fr

Pas de notes de cours prévues.

## Présentation

We present the main ingredients of the mathematical and algorithmic framework to study polynomial optimization problems, with a (slight) emphasis on semidefinite programming.

## Contenu

• Introduction to semidefinite programming, binary quadratic programming (relaxation + max cut)
• Univariate polynomials, resultants and discriminants, binomial equations, Newton polytopes, and BKK.
• Sum of squares and applications, duality and moments.
• Ideals, varieties and monomial ordering, Groebner bases, zero dimensional systems and SOS on quotients.
• Quantifier elimination, representation of positive polynomials.

## Prérequis

Linear algebra and algebra, introductory notions of algebraic geometry, basic knowledge of convex analysis.