Algebra and Combinatorics Seminar

Date: November 17, 2023

Time: 3:00PM - 4:00PM

Location: BLOC 302

Speaker: Shixuan Zhang, TAMU (ISEN)

Title: Certification of sums of squares via low-rank optimization

Abstract: To certify a sum of k squares on a real projective variety, one can minimize the distance of the sum of squares of k linear forms from it in the space of quadrics. When k is smaller than the dimension of linear forms, the certification problem can be applied in low-rank semidefinite relaxation of polynomial optimization, similar to the Burer-Monteiro method. We discuss the existence of spurious local minima in this nonconvex certification problems, and show that in some interesting cases, there is no spurious local minima, or any spurious local minimum would lie on the boundary of the sum-of-square cone. These characterizations could potentially lead to efficient algorithms for polynomial and combinatorial optimization.