Spurious local minima in nonconvex sum-of-squares optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929575151271936 |
|---|---|
| author | Blekherman, Grigoriy Sinn, Rainer Velasco, Mauricio Zhang, Shixuan |
| author_facet | Blekherman, Grigoriy Sinn, Rainer Velasco, Mauricio Zhang, Shixuan |
| contents | We study spurious second-order stationary points and 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 second-order stationary points if and only if both the dimension and the codimension of the variety are greater than one, 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 second-order stationary points associated with infinite Gram matrices 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 second-order stationary points in the interior, together with a restricted path algorithm that avoids such points with controlled step sizes, and numerical experiment results illustrating the empirical successes on plane cubic curves and Veronese varieties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02208 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spurious local minima in nonconvex sum-of-squares optimization Blekherman, Grigoriy Sinn, Rainer Velasco, Mauricio Zhang, Shixuan Optimization and Control Primary 90C22, 90C26, 14P99, 14M99, Secondary 13D02 We study spurious second-order stationary points and 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 second-order stationary points if and only if both the dimension and the codimension of the variety are greater than one, 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 second-order stationary points associated with infinite Gram matrices 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 second-order stationary points in the interior, together with a restricted path algorithm that avoids such points with controlled step sizes, and numerical experiment results illustrating the empirical successes on plane cubic curves and Veronese varieties. |
| title | Spurious local minima in nonconvex sum-of-squares optimization |
| topic | Optimization and Control Primary 90C22, 90C26, 14P99, 14M99, Secondary 13D02 |
| url | https://arxiv.org/abs/2411.02208 |