Spring 2019

Certificates of Polynomial Non-Negativity via Hyperbolic Optimization

Tuesday, April 30th, 2019 9:30 am10:15 am

Add to Calendar


James Saunderson (Monash University) 

I will discuss a way to construct, from a hyperbolic polynomial and a direction of hyperbolicity, families of nonnegative polynomials that can be optimized over via hyperbolic programming. We call a hyperbolic polynomial "SOS-hyperbolic" if all the nonnegative polynomials produced by this construction are sums of squares. Of most interest are the hyperbolic polynomials that are not SOS-hyperbolic, since these could lead to hyperbolic programming relaxations of optimization problems that are, in some sense, more powerful than semidefinite relaxations. After introducing these general ideas, this talk will mostly focus on the case of hyperbolic cubics, discussing what is known (as well as open questions) about when they are, and are not, SOS-hyperbolic. On the way, we establish NP-hardness of deciding hyperbolicity of cubics, and give an example of an explicit hyperbolic cubic for which no power has a definite determinantal representation.