Schedule for: 19w5180 - Geometry of Real Polynomials, Convexity and Optimization

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

I will survey some topics about hyperbolic polynomials and their determinantal representations, and hyperbolicity cones and representations thereof by linear matrix inequalities (spectrahedral cones). Time permitting I will then discuss two neighbouring topics: (a) a generalization of hyperbolicity from hypersurfaces to higher codimensional subvarieties, and a related class of determinantal representations (that yield linear determinantal representations of the Chow form); (b) complex multivariate polynomials that are stable (i.e., zero free) with respect to the unit polydisc, and determinantal representation that witness stability.

Let C be a semi-algebraic curve in n-dimensional space. We will present obstructions and constructions for the conic hull of C to be a hyperbolicity cone. The tools we use are methods from complex and real algebraic geometry. This is joint work in progress with Rainer Sinn.

Recently Averkov showed that various convex cones related to nonnegative polynomials do not have K-lifts (representations as projections of linear sections of K) where K is a Cartesian product of positive semidefinite cones of "small" size. In this talk I'll discuss an extension of this result that says that convex bodies with certain neighborliness properties do not have K-lifts whenever K is a Cartesian product of cones, each of which does not have any long chains of faces (such as smooth cones, low-dimensional cones, and cones defined by hyperbolic polynomials of low degree).

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

The semialgebraic set $D_f$ determined by a noncommutative polynomial $f$ is the closure of the connected component of $\{(X,X^*): f(X,X^*)\succ0\}$ containing the origin. When $L$ is a linear pencil, the semialgebraic set $D_L$ is the feasible set of the linear matrix inequality $L(X,X^*)\succeq 0$ and is known as a free spectrahedron. Evidently these are convex and by a theorem of Helton \& McCullough, a free semialgebraic set is convex if and only it is a free spectrahedron. \\\\ In this talk we solve the basic problem of determining those $f$ for which $D_f$ is convex. The solution leads to an effective algorithm that not only determines if $D_f$ is convex, but if so, produces a minimal linear pencil $L$ such that $D_f=D_L$. Of independent interest is a subalgorithm based on a Nichtsingulärstellensatz: given linear pencils $L,L'$, it determines if $L'$ takes invertible values on the interior of $D_L.$ Finally, it is shown that if $D_f$ is convex for an irreducible noncommutative polynomial, then $f$ has degree at most two, and arises as the Schur complement of an $L$ such that $D_f=D_L$. This is based on joint work with Bill Helton, Scott McCullough and Jurij Volčič.

The cohomology groups (with rational coefficients) of semi-algebraic sets defined by symmetric polynomials inherit a structure of a finite dimensional module over the symmetric group (from the action of the symmetric group on the ambient space). The isotypic decomposition of these modules shed important information on the Betti numbers of such sets, via the multiplicities of the various irreducible representations (the so called Specht modules), and the well known ``hook formula'' that gives the dimensions of these irreducible representations. We prove new vanishing results on the multiplicities of these Specht modules in the cohomology groups of semi-algebraic sets defined by symmetric polynomials (in each dimension).

We bound the Pythagoras number of a real projective subvariety: the smallest positive integer $r$ such that every sum of squares of linear forms in its homogeneous coordinate ring is a sum of a most $r$ squares. We will describe three distinct upper bounds involving known invariants. In contrast, our lower bound depends on a new invariant called quadratic persistence. This talk is based on joint work with Greg Blekherman, Rainer Sinn, and Mauricio Velasco.

By the Toeplitz-Hausdorff theorem in convex analysis, the numerical range of a complex square matrix is a convex compact subset of the complex plane. Kippenhahn's theorem describes the numerical range as the convex hull of an algebraic curve that is dual to a hyperbolic curve. For the joint numerical range of several matrices, the direct analogue of Kippenhahn's theorem is known to fail. We discuss the geometry behind these results and prove a generalization of Kippenhahn's theorem that holds in any dimension. Joint work with Daniel Plaumann and Stephan Weis.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

In this talk, we will see how to approximately compute a multiaffine polynomial over the positive orthant, having only oracle access to its coefficients, as long as the polynomial is log-concave over this region. This algorithm can be used as part of discrete optimization methods introduced in the previous talk.

I discuss a framework that came to mind five years ago, in trying to solve an algorithmic problem in the context of hyperbolic programming. I never solved that problem, but the framework has proved to have interesting algorithmic consequences for convex optimization generally.

Let $S\subset \mathbb{R}^n$ be a semi algebraic set defined by symmetric polynomials of degree $d$. We will discuss several examples where topological invariants of $S$ can be computed with a complexity that is polynomial in $n$ for fixed $d$. This is based on joint works with Saugata Basu.

A convex form of degree larger than one is always nonnegative since it vanishes together with its gradient at the origin. In 2007, Parrilo asked if convex forms are always sums of squares. A few years later, Blekherman answered the question in the negative by showing through volume arguments that for high enough number of variables, there must be convex forms of degree 4 that are not sums of squares. Remarkably, no examples are known to date. In this talk, we show that all convex forms in 4 variables and of degree 4 are sums of squares. We also show that if a conjecture of Blekherman related to the so-called Cayley-Bacharach relations is true, then the same statement holds for convex forms in 3 variables and of degree 6. These are the two minimal cases where one would have any hope of seeing convex forms that are not sums of squares (due to known obstructions). A main ingredient of the proof is the derivation of certain "generalized Cauchy-Schwarz inequalities" which could be of independent interest.

This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points, based on Lasserre's hierarchy of Moment-SOS relaxations. Under some genericity assumptions, we show that: i) if there exists a saddle point, the algorithm can get one by solving a finite number of relaxations; ii) if there is no saddle point, the algorithm can detect its nonexistence.

The feasible set in a conic program is the intersection of a convex cone with an affine space. In this talk, I will be interested in the feasibility problem of conic programming: How to decide whether an affine space intersects a convex cone or, conversely, that the intersection is empty? Can we compute certificates of infeasibility? The problem is harder than expected since in (non-linear) conic programming, several types of infeasibility might arise. In a joint work with R. Sinn we revisit the classical facial reduction algorithm from the point of view of projective geometry. This leads us to a homogenization strategy for the general conic feasibility problem. For semidefinite programs, this yields infeasibility certificates that can be checked in polynomial time. We also propose a refined type of infeasibility, which we call "stable infeasibility” for which rational infeasibility certificates exist.

Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalities are known, many more are conjectured. A standard tool to establish an inequality is to write the expression whose non-negativity needs to be certified as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. Joint work with Greg Blekherman, Annie Raymond and Mohit Singh.

We show how the Lasserre hierarchy can solve a class of non-linear partial differential equations (PDEs), with rigorous convergence guarantees. We use a weak formulation of the nonlinear PDE, resulting in a linear equation in the space of measures, to be solved numerically and approximately with the hierarchy. The entire approach is based purely on convex optimization and it does not rely on spatio-temporal gridding, even though the PDE addressed can be fully nonlinear.

We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy solutions to non-linear hyperbolic PDEs, or using numerical integration from finitely many evaluations of the function.

In this talk we give an introduction to infinite dimensional moment problems, i.e. for measures supported on infinite dimensional spaces. Although infinite dimensional moment problems have a long history, the theory is still not as well developed as in the finite dimensional case. We will focus on the following problem: when can a linear functional on a unital commutative real algebra A be represented as an integral w.r.t. a Radon measure on the character space X(A) of A equipped with the Borel σ-algebra generated by the weak topology? Our main idea is to construct X(A) as a projective limit of the character spaces of all finitely generated subalgebras of A, so to be able to exploit the classical finite dimensional moment theory in the infinite dimensional case. Thus, we obtain existence results for representing measures defined on the cylinder σ-algebra on X(A), carried by the projective limit construction. If in addition the well-known Prokhorov (ε-K) condition is fulfilled, then we can solve our problem by extending such representing measures from the cylinder to the Borel σ-algebra on X(A). These results allow us to establish infinite dimensional analogues of the classical Riesz-Haviland and Nussbaum theorems as well as a representation theorem for linear functionals nonnegative on a “partially Archimedean” quadratic module of A. Our work applies to the case when A is the algebra of polynomials in infinitely many variables or the symmetric tensor algebra of a real infinite dimensional vector space, providing alternative proofs of some recent results for these instances of the moment problem and offering at the same time a unified setting which enables comparisons. (This is a joint work with Salma Kuhlmann, Tobias Kuna and Patrick Michalski)

The univariate moment problem for the real polynomial ring is an old problem with origins tracing back to work of Stieltjes. The multivariate moment problem has been considered more recently. Even more recently, there has been considerable interest, for both pure theory and applications, in the infinite-variate moment problem, dealing with the moment problem in (possibly not finitely generated) real commutative unital algebras. In this talk we focus on a real (commutative unital) locally multiplicatively convex topological algebra and the representation of continuous linear functionals by Radon measures on its character space. We first prove a general representation theorem by measures supported on the Gelfand Spectrum of a real sub-multiplicative semi-normed real algebra. To this end, we exploit the Archimedean Positivstellensatz, which holds in its (Banach) completion, and then proceed to handle an arbitrary locally multiplicatively convex topology. We will illustrate the methods by examples. In particular, we apply our results to the symmetric tensor algebra of a locally convex real topological space. This talk is based on joint work with Ghasemi, Infusino and Marshall.

A novel, harmonic analysis proof, of Laguerre’s lemma which is the key ingredient in Grace apolarity theorem and Walsh coincidence theorem. Joint work with the late Serguei Shimorin.

sing subresultants, we modify a recent real-algebraic proof due to Eisermann of the Fundamental Theorem of Algebra ([FTA]) to obtain the following quantitative information: in order to prove the [FTA] for polynomials of degree d, the Intermediate Value Theorem ([IVT]) is requested to hold for real polynomials of degree at most d^2. We also explain that the classical proof due to Laplace requires [IVT] for real polynomials of exponential degree. These quantitative results highlight the difference in nature of these two proofs. See arXiv:1803.04358v3

Let $S\subset \R^n$ be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We present an algorithm which takes as input a polynomial system defining $S$ and an integer $p\geq 0$ and returns the $n$-dimensional volume of $S$ at absolute precision $2^{-p}$. Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations. The algorithm runs in essentially linear time w.r.t.~$p$. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. The arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in $n$ and polynomial in the maximum degree of the input. Joint work with Pierre Lairez and Marc Mezzarobba

Recall that given two complex polynomials $f$ and $g$, the Bezout matrix $B(f,g) = (b_{ij})$ of $f$ and $g$ is defined by $\frac{f(t)g(s) - f(s)g(t)}{t-s} = \sum_{i,j} b_{ij} t^i s^j$. It is a classical result of Hermite that given a polynomial $p(z)$, the Bezout matrix of $p(z)$ and $p^{\tau}(z) = \overline{p(\bar{z})}$ is skew self-adjoint. The number of common zeroes of $p$ and $p^{\tau}$ is the dimension of the kernel of $-i B(p,p^{\tau})$. Additionally, $p$ has $n_+$ roots in the upper half-plane and $n_-$ in the lower half-plane. Here $n-+$ and $n_-$ stand for the number of positive and negative eigenvalues of $-i B(p,p^{\tau})$, respectively. In this talk, I will describe how one can extend the notion of the Bezout matrix to a pair of meromorphic functions on a compact Riemann surface. If the surface is real and dividing the matrix $-i B(f,f^{\tau})$ is $J$-selfadjoint, for a certain signature matrix $J$. We the study the signature of the Bezoutian and obtain an extension of Hermite’s theorem to quadrature domains. This talk is based on joint work with V. Vinnikov.

There are many types of noncommutative polynomials and many definitions of the zero set for each type, so there are many possible generalizations of Hilbert's Nullstellensatz and Real Nullstellensatz. I will survey my recent work on noncommutative nullstellensätze for Weyl algebras and universal enveloping algebras of some Lie algebras. I will also survey known results for free algebras and matrix polynomials.

A multivariate polynomial is stable if it is nonzero whenever all its variables have positive imaginary parts. Lorentzian polynomials generalize homogeneous and stable polynomials. We discuss the spaces of stable and Lorentzian polynomials, their tropicalizations, and the connection to discrete convexity. This is based on joint work with June Huh.

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube H. One particularly successful way to prove complexity bounds for these types of problems are based on sums of squares (SOS) as nonnegativity certificates. We initiate optimization over H via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube H with constraints of degree at most d there exists a SONC certificate of degree at most n+d. Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over H, then there also exists a short degree d SONC certificate, that includes at most n^O(d) nonnegative circuit polynomials. Joint work with Timo de Wolff and Adam Kurpisz.

The Sums-of-AM/GM-Exponential (SAGE) approach to signomial and polynomial nonnegativity is a powerful proof system based on convex duality and the relative entropy function. In this talk I provide a brief derivation of SAGE certificates for signomials, and review some recent results for SAGE signomials and SAGE polynomials. I will conclude with a small preview of upcoming work: how the "signomial representatives" underlying SAGE polynomials lead to an effective algorithm for solution recovery to moment-SAGE relaxations in polynomial optimization.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.