Professor Amir Ali Ahmadi will talk about; 'Disjunctive Sum of Squares'

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach, where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity using multiple algebraic identities. Our main result is a disjunctive Positivstellensatz showing that the degree of each algebraic identity can be kept as low as the degree of the polynomial whose nonnegativity is in question. Based on this result, we construct a semidefinite programming–based converging hierarchy of lower bounds for the problem of minimizing a polynomial over a compact basic semialgebraic set, in which the size of the largest semidefinite constraint remains fixed throughout the hierarchy. We further prove a second disjunctive Positivstellensatz, which leads to an optimization-free hierarchy for polynomial optimization. We specialize this result to the problem of proving copositivity of matrices. Finally, we describe how the disjunctive sum of squares approach can be combined with a branch-and-bound algorithm, and we present numerical experiments on polynomial, copositive, and combinatorial optimization problems. The talk is self-contained and assumes no prior background in sum of squares optimization.

TBA