Optimization

Authors: Matteo Bechere, Sami Halase, Francesco Maria Mascarin

Tensors and polynomial optimization

Optimization means solving problems of the form

$$\underset{x\in S}{\inf }f(x)$$

Optimization means solving problems of the form

$$\underset{x\in S}{\inf }f(x).$$

An important special class is polynomial optimization (POP): the objective $f$ is a polynomial and the feasible set is a basic closed semialgebraic set

$$S=\{x\in {\mathbb{R}}^n:g_1(x)\ge 0,\dots ,g_m(x)\ge 0\},$$

where $g_1,\dots ,g_m$ are polynomials as well. This class is very expressive: it contains, for instance, combinatorial problems such as max-cut, and is therefore hard in general. Its algebraic structure, however, allows for powerful approximation schemes.

Two dual points of view

Sums of squares. The minimum $f_{\min }$ is the largest $\lambda$ such that $f-\lambda$ is nonnegative on $S$. Nonnegativity is hard to check, so one asks instead for an algebraic certificate

$$f-\lambda ={\sigma }_0+\sum _{j=1}^m{\sigma }_j{g}_j,$$

where each ${\sigma }_j$ is a sum of squares of polynomials. Once the degrees are bounded, finding such a certificate is a semidefinite program.

Moments. Equivalently, $f_{\min }$ is the minimum of $\int fd\mu$ over all probability measures $\mu$ supported on $S$. A measure is replaced by its sequence of moments up to some degree, and the condition that it comes from a measure on $S$ is relaxed to the positive semidefiniteness of the associated moment and localizing matrices. This is again a semidefinite program.

Increasing the degree gives the moment–SOS hierarchy (or Lasserre hierarchy) of lower bounds on $f_{\min }$. Under a mild compactness assumption these bounds converge to $f_{\min }$ (Lasserre, 2001).

Where tensors enter

The moments of degree $d$ of a measure $\mu$ form a symmetric tensor,

$$M_d(\mu )=\int {\tilde{x}}^{\otimes d}d\mu (x),\tilde{x}=(1,x),$$

so the moment side of the hierarchy is an optimization over symmetric tensors. When the problem has finitely many minimizers ${\xi }_1,\dots ,{\xi }_r$, an optimal measure is $\mu ={\sum }_i{\omega }_i{\delta }_{{\xi }_i}$ and its moment tensor has the decomposition

$$M_d(\mu )=\sum _{i=1}^r{\omega }_i{\tilde{\xi }}_i^{\otimes d},{\omega }_i>0.$$

Recovering the minimizers from the output of the relaxation is therefore a symmetric tensor decomposition problem, with the extra requirement that the weights be positive.

Tensors with positive representation

Optimization on Lissajous varieties

Lissajous varieties are affine algebraic varieties parametrized by sine and cosine functions. They generalize algebraic Lissajous planar curves to higher dimensions by applying a component-wise trigonometric map to a rational affine complex subspace. Concretely, for an integer matrix $A\in {\mathbb{Z}}^{d\times n}$ and a shift $b\in {\mathbb{C}}^n$,

$${\mathcal{L}}_{A,b}=\cos (\mathrm{Row}(A)-\frac{\pi }{2}b),$$

with the cosine applied coordinate-wise. For instance, $A=(11)$ and $b=(0,1)$ give the circle $t\mapsto (\cos t,\sin t)$. The degree of ${\mathcal{L}}_{A,b}$ is, up to a combinatorial factor, the volume of a polytope built from the columns of $A$. A first example is Cayley’s cubic surface, the algebraic boundary of the $3\times 3$ elliptope.

Equations from tensor product algebras

The defining equations of Lissajous varieties have a natural tensor structure. Substituting $x_j=\frac{1}{2}(y_j+y_j^{-1})$ leads to the algebra

$$\mathcal{A}=\underset{j=1}{\overset{n}{⨂}}K[y_j^{\pm 1}]/⟨2x_j-y_j-y_j^{-1}⟩,$$

a tensor product of $n$ two-dimensional algebras, one for each coordinate, so $\dim \mathcal{A}=2^n$. Equations of ${\mathcal{L}}_{A,b}$ are obtained as rank conditions on multiplication maps acting on $\mathcal{A}$. These are $2^n\times 2^n$ matrices with polynomial entries in $x$, built from Kronecker products of $2\times 2$ blocks. When ${\mathcal{L}}_{A,b}$ is a hypersurface, it is the zero set of the determinant of a single multiplication map, which is a power of its defining polynomial.

Positive points and convex optimization

The positive points ${\mathcal{L}}_{A,b}^{+}=\cos ((\mathrm{Row}(A)-\frac{\pi }{2}b)\cap (0,\pi {)}^n)$ can be computed by convex optimization: $x^{\ast }$ lies in ${\mathcal{L}}_{A,b}^{+}\cap \{Ax=\omega \}$ if and only if it is the unique minimizer of

$$\underset{x\in (-1,1{)}^n}{\min }-\frac{\pi }{2}{b}^{\top }x-\sum _{j=1}^n(x_j\arccos (x_j)-\sqrt{1-x_j^2})\text{subject to}Ax=\omega .$$

This applies to the Kuramoto model of coupled oscillators on a graph $G$. Its steady states are the points of a sine Lissajous variety on an affine slice $Ax=\omega /K$, with $A$ the reduced incidence matrix of $G$. The degree of this variety bounds the number of isolated equilibria. Whenever a positive point exists on this slice, it is unique and corresponds to a linearly stable equilibrium, which is found by solving the convex program above.

Graph elliptopes

For a graph $G=([n],E)$, the graph elliptope $\mathcal{E}(G)\subset {\mathbb{R}}^E$ is the set of partial correlation matrices supported on $E$ that admit a positive semidefinite completion. For the complete graph it is the elliptope, the feasible set of the Goemans–Williamson relaxation of max-cut.

For cycle-completable graphs, the algebraic boundary of $\mathcal{E}(G)$ is a union of determinantal hypersurfaces and Lissajous varieties. The latter come from the cycles of $G$ and are defined by the cycle polynomial, obtained by rationalizing $x_1=\cos \left({\sum }_{i=2}^n\arccos x_i\right)$. It can be computed recursively as a resultant of smaller cycle polynomials, and its degree answers a question of Sturmfels and Uhler. Moreover, $\mathcal{E}(G)$ is a spectrahedron exactly when its algebraic boundary avoids the interior, which happens precisely when $G$ is chordal.

References

• F. M. Mascarin, S. Telen. Lissajous varieties. Advances in Geometry 26(2), 263–282, 2026.
• M. Laurent, F. M. Mascarin, S. Telen. The algebraic boundary of graph elliptopes. Preprint, 2026.

Courses

• Semidefinite approximations for polynomial optimization, with applications to quantum information|Monique Laurent (CWI)
  • Lecture Notes (POP and QI) Hand-out Part 1 Hand-out Part 2
  • Recording 1/2 Recording 2/2
• Introduction to tropical geometry Mateusz Skomra (LAAS-CNRS)
  • Hand-out Recording (Part 1) Recording (Part 2)
• Algebraic Varieties and Regularization - Simon Telen