Sums of squares approximations in polynomial optimization: performance analysis and degree bounds

By Monique Laurent

Appears in collection : 2023 - T3 - WS2 - Geometry of polynomial system solving, optimization and topology

Polynomial optimization deals with optimizing a polynomial function over a feasible region defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity. These hierarchies give bounds on the global minimum of the original problem with asymptotic convergence (under a minor compactness assumption). In this lecture we discuss recent results on the performance analysis of these hierarchies and related effective degree bounds for dedicated sums of squares representations of positive polynomials on some classes of compact semi-algebraic sets (including the hypercube, the sphere or the ball).

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS2.009
  • Cite this video Laurent Monique (10/19/23). Sums of squares approximations in polynomial optimization: performance analysis and degree bounds. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS2.009
  • URL


  • E. de Klerk and M. Laurent. Worst-case examples for Lasserre's measure--based hierarchy for polynomial optimization on the hypercube. Mathematics of Operations Research, 45(1):86-98, 2020.
  • L. Slot. Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel. SIAM Journal on Optimization, 32(4), 2022.
  • M. Laurent and L. Slot. An effective version of Schmüdgen's Positivstellensatz for the hypercube. Optimization Letters, 17:515-530, 2023.

Last related questions on MathOverflow

You have to connect your account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback