Cours spécialisé ()

Algebraic and geometric techniques in optimization

Elias Tsigaridas

Contact : etsigarid à imj-prg.fr

Pas de notes de cours prévues.

Langue du cours : anglais

Présentation

We present algebraic and geometric methods to handle polynomial optimization problems, with a special emphasis on semidefinite programming. Our focus is on convexity, complexity, and the development of efficient algorithms.

Contenu

• Introduction to polytopes, convexity, and convex cones.
• The geometry of the cone of positive semidefinite matrices.
• Univariate polynomials, resultants and discriminants, binomial equations, Newton polytopes, and BKK bound.
• Non-negative polynomals and sum of squares, duality and moments.
• Ideals, varieties and monomial ordering, Groebner bases, zero dimensional systems and SOS on quotients.
• Variations of the Real Nullstellensatz. Certificates of positivity. Representation of positive polynomials.

Prérequis

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. URL, a rehttps://sites.math.washington.edu/~thomas/frg/frgbook/SIAMBookFinalvNov12-2012.pdfmplacer
• 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
• Theobald. Real Algebraic Geometry and Optimization. Graduate Studies in Mathematics, American Mathematical Society, 2024
• Netzer, Plaumann. Geometry of Linear Matrix Inequalities. Springer International Publishing, 2023
• Cox, Little, O'Shea. Ideals, varieties, and algorithms.. Springer 1997
• Cox, Little, O'Shea. Using algebraic geometry. . Springer 2005