Search

Workshop

Local minima in nonconvex sum-of-square optimization via syzygies

  • Shixuan Zhang
Felix-Klein-Hörsaal Universität Leipzig (Leipzig)

Abstract

We study spurious local minima in a nonconvex low-rank formulation of sum-of-squares optimization on a real variety $X$. We reformulate the problem of finding a spurious local minimum in terms of syzygies of the underlying linear series, and also bring in topological tools to study this problem. When the variety $X$ is of minimal degree, there exist spurious local minima if and only if both the dimension and the codimension of the variety are greater than one and $X$ is not the Veronese surface, answering a question by Legat, Yuan, and Parrilo. Moreover, for surfaces of minimal degree, we provide sufficient conditions to exclude points from being spurious local minima. In particular, all spurious local minima on the Veronese surface, corresponding to ternary quartics, lie on the boundary and can be written as a binary quartic, up to a linear change of coordinates, complementing work by Scheiderer on decompositions of ternary quartics as a sum of three squares. For general varieties of higher degree, we give examples and characterizations of spurious local minima in the interior, which can potentially lead to efficient low-rank sum-of-squares algorithms.

Links

conference
29.07.24 02.08.24

MEGA 2024

MPI für Mathematik in den Naturwissenschaften Leipzig (Leipzig) E1 05 (Leibniz-Saal)
Universität Leipzig (Leipzig) Felix-Klein-Hörsaal

Mirke Olschewski

Max Planck Institute for Mathematics in the Sciences Contact via Mail

Saskia Gutzschebauch

Max Planck Institute for Mathematics in the Sciences Contact via Mail

Christian Lehn

Ruhr-Universität Bochum

Irem Portakal

Max Planck Institute for Mathematics in the Sciences

Rainer Sinn

Universität Leipzig

Bernd Sturmfels

Max Planck Institute for Mathematics in the Sciences

Simon Telen

Max Planck Institute for Mathematics in the Sciences