Applied Algebra Seminar: WiSe 2025-2026
Solution recovery in sparse polynomial optimization
Leif Niehe (TU Braunschweig)
Finding minimizers to polynomial optimization problems, i.e., points $\mathbf{x^*}\in\mathcal{G}_+\subseteq\mathbb{R}^n$ s.t. $f(\mathbf{x^*}) = f^* := \min_{\mathbf{x}\in \mathcal{G}_+} f(x)$ is of high interest in many applications. While there are ways to approximate the value $f^*$ like Sums Of Squares (SOS), Sums Of Nonnegative Circuit polynomials (SONC) and Sums of Arithmetic/Geometric mean Exponentials (SAGE), the corresponding approaches to recover solutions $\mathbf{x^*}$ often work only in special cases or are heuristic in nature. For this thesis, I developed, and implemented in Julia, a new heuristic to solution recovery in the unconstrained case $\mathcal{G}_+ = \mathbb{R}^n$, which leverages given SONC decompositions and the fact that the minimizers for individual nonnegative circuit polynomials can be computed efficiently. Despite the fact that this approach does not guarantee the recovery of the correct solutions, it yields promising results when compared to a lower bound from SOS, especially when combined with a local solver as refinement.
A Pythagoras Number for Sums of Nonnegative Circuit Polynomials
Birte Ostermann (TU Braunschweig)
This is ongoing work with Timo de Wolff.
Higher-order Rigidity of Geometric Contraint Systems
Matthias Adrian-Himmelmann (TU Braunschweig)
Geometric constraint systems (GCS) are used to model a wide variety of real-world objects whose movements are limited by natural, geometric constraints. These constraints are typically expressed by polynomial equations and include incidence, distance, tangency, volume, and coplanarity. As a result, the class of admissible geometric objects ranges from polytopes and sphere packings to simplicial complexes and hydraulic platforms.
Deciding whether a geometric constraint system is flexible - that is, whether it admits continuous deformations beyond ambient Euclidean isometries - or rigid is computationally challenging. For that reason, one often relies on weaker but computationally tractable sufficient conditions for rigidity. In regular points, the kernel of the system's Jacobian determines the dimension of the constraint variety. Comparing this dimension with that of the Lie group of Euclidean isometries yields a simple rigidity criterion. However, this criterion is not necessary.
In this talk, we develop a theory of higher-order rigidity for geometric constraint systems and discuss corresponding algorithmic approaches grounded in real algebraic geometry. By constructing explicit examples of second-order rigid systems - such as the regular dodecahedron - we demonstrate that these conditions are not only theoretically relevant but have concrete applications to the real world.
Sampling from convex sets using geometric random walks
Elias Tsigaridas (Inria Paris)
We present algorithmic, complexity, and implementation results on the problem of sampling points from convex bodies; with an emphasis on polytopes (the feasible regions of linear programs) and spectrahedra (the feasible regions of semidefinite programs). Our main tool is geometric random walks. We highlight (and analyze the complexity) of their realization based on certain primitive geometric operations, that in turn exploit the algebraic properties of the underlying convex body. We focus on sampling from log-concave distributions and, if time permits, we will present applications of independent interest, like approximating the volume and convex optimization. This is joint work with Apostolos Chalkis and Vissarion Fisikopoulos.
Elimination Algorithms for Differential Dynamical Systems
Yulia Mukhina (Institut Polytechnique Paris)
Differential algebra is the branch of algebra that studies differential equations from an algebraic standpoint, inspired by the way polynomial equations are studied using algebraic geometry. A key topic in this field is the elimination of variables. More precisely, given a system with several variables, we aim to describe the differential relations satisfied by a selected subset of those variables. Elimination is used to analyze systems of differential equations, especially in the context of dynamical systems models where data is available only for a subset of the variables. In this talk, we provide an overview of existing tools for differential elimination and discuss their potential applications. We present our main result: the characterization of the set of terms that can appear in the resulting polynomial after elimination. Based on this result, we introduce an algorithm and demonstrate that our implementation can handle problems that are beyond the capabilities of current state-of-the-art software for differential elimination. We also discuss a new approach to computing so-called mixed fiber polytopes in the context of polynomial elimination. We demonstrate the practical performance improvements of our algorithm compared to existing methods and highlight an application of this work to differential elimination.