Séminaire de Probabilités

Mini-course: Sum-of-squares optimization on finite sets (1/2)

by Prof. Mauricio VELASCO (Uni de los andes)

Europe/Paris
Salle F. Pellos, Room 207, Building 1R2 (IMT)

Salle F. Pellos, Room 207, Building 1R2

IMT

Description

Title: Sum-of-squares optimization on finite sets


Abstract: If $X \subseteq R^n$ is a finite set then every function on 
$X$ can be written as the restriction of a polynomial in n-variables. As 
a result, polynomial optimization on finite sets is literally the same 
as general (nonlinear) optimization on such sets. Thinking of functions 
as polynomials however, provides us with plenty of additional structures 
which can be leveraged for constructing better (or at least different) 
optimization algorithms such as the sum-of-squares approach.

In this short course I will focus on explaining how sparsity, symmetry 
and kernel methods can be leveraged for solving nonlinear optimization 
problems on finite sets and will prove the recent definite results on 
the hypercube due to Blekherman, Gouveia, Laurent, Nie, Parrilo, 
Saunderson, Thomas and others.

The lectures will be a self-contained introduction to this very active 
research area.

Times and locations:
- Monday 12th of june: 10:00 -> 12:00
Salle F. Pellos, Room 207, Building 1R2
- Tuesday 13th of june: 14:00 -> 16:00
Salle R. Huron, Room 106, Building 1R1

From the same series
2