Skip to content
# Events for February 17, 2017 from General and Seminar calendars

## Algebra and Combinatorics Seminar

**Abstract:** Deciding nonnegativity of real polynomials is a fundamental problem in real algebraic geometry and polynomial optimization. Since this problem is NP-hard, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. The standard certificates for nonnegativity are sums of squares (SOS). In practice, SOS based semidefinite programming (SDP) is the standard method to solve polynomial optimization problems.

In 2014, Iliman and I introduced an entirely new nonnegativity certificate based on sums of nonnegative circuit polynomials (SONC), which are independent of sums of squares. We successfully applied SONCs to global nonnegativity problems.

In Summer 2016, Dressler, Iliman, and I proved a Positivstellensatz for SONCs, which provides a converging hierarchy of lower bounds for constrained polynomial optimization problems. These bounds can be computed efficiently via relative entropy programming.

In this first of two talks on the topic I will give a brief overview about SONCs and Positivstellensätze in general and then introduce and prove our Positivstellensatz.

The second, corresponding talk will occur directly afterwards in the geometry seminar.

## Geometry Seminar

**Abstract:** Deciding nonnegativity of real polynomials is a fundamental problem in real algebraic geometry and polynomial optimization. Since this problem is NP-hard, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. The standard certificates for nonnegativity are sums of squares (SOS). In practice, SOS based semidefinite programming (SDP) is the standard method to solve polynomial optimization problems. In 2014, Iliman and I introduced an entirely new nonnegativity certificate based on sums of nonnegative circuit polynomials (SONC), which are independent of sums of squares. We successfully applied SONCs to global nonnegativity problems. In Summer 2016, Dressler, Iliman, and I proved a Positivstellensatz for SONCs, which provides a converging hierarchy of lower bounds for constrained polynomial optimization problems. These bounds can be computed efficiently via relative entropy programming. In this second of two talks on the topic I will give a brief overview about semidefinite, geometric, and relative entropy programming as well as Lasserre Relaxation. Afterwards, I will explain our converging hierarchy of lower bounds for constrained polynomial optimization and how they can be computed via relative entropy programming. The first, corresponding talk will occur directly before in the algebra and combinatorics seminar.

## Linear Analysis Seminar

**Abstract:** I will review the boundary theory of quantum random walks, which was initiated by Biane and Izumi in the 90s, and give some examples, generalizations and applications.

**Time:** 3:00PM - 3:50PM

**Location:** BLOC 628

**Speaker:** Timo de Wolff, Texas A&M University

**Title:** *A Positivstellensatz for Sums of Nonnegative Circuit Polynomials*

In 2014, Iliman and I introduced an entirely new nonnegativity certificate based on sums of nonnegative circuit polynomials (SONC), which are independent of sums of squares. We successfully applied SONCs to global nonnegativity problems.

In Summer 2016, Dressler, Iliman, and I proved a Positivstellensatz for SONCs, which provides a converging hierarchy of lower bounds for constrained polynomial optimization problems. These bounds can be computed efficiently via relative entropy programming.

In this first of two talks on the topic I will give a brief overview about SONCs and Positivstellensätze in general and then introduce and prove our Positivstellensatz.

The second, corresponding talk will occur directly afterwards in the geometry seminar.

**Time:** 4:00PM - 5:00PM

**Location:** BLOC 628

**Speaker:** Timo de Wolff, TAMU

**Title:** *Constrained Polynomial Optimization via SONCs and Relative Entropy Programming*

**Time:** 4:00PM - 5:00PM

**Location:** BLOC 220

**Speaker:** Sergey Neshveyev, University of Oslo

**Title:** *Probabilistic boundaries of quantum random walks*