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.
Bibliographie
- Blekherman, Parrilo, and Thomas, eds.. Semidefinite Optimization and Convex Algebraic Geometry. MOS-SIAM Series on Optimization. Philadelphia: Society for Industrial and Applied Mathematics : Mathematical Programming Society, 2013.
https://sites.math.washington.edu/~thomas/frg/frgbook/SIAMBookFinalvNov12-2012.pdf
- Cox, Little, O'Shea. Ideals, varieties, and algorithms. Springer 1997
- Cox, Little, O'Shea. Using algebraic geometry. Springer 2005
- Michalek, Sturmfels. Invitation to nonlinear algebra. AMS 2020
https://math.berkeley.edu/~bernd/gsm211.pdf
- Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, M. Putinar and S. Sullivant (eds.), 2010
https://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf