##### Department of Mathematics,

University of California San Diego

****************************

### Math 278C: Optimization and Data Science Seminar

## Igor Klep

#### The University of Auckland

## Linear Matrix Inequalities, PositivstellensÃ¤tze and Coin Tossing

##### Abstract:

Given a tuple $A=(A_1,\ldots,A_g)$ of symmetric matrices of the same size, the affine linear matrix polynomial $L(x):=I-\sum A_j x_j$ is a monic linear pencil. The solution set $S_L$ of the corresponding linear matrix inequality (LMI), consisting of those $x$ in $\mathbb R^g$ for which $L(x)$ is positive semidefinite (PsD), is called a spectrahedron. It is a convex semialgebraic subset of $\mathbb R^g$, and LMIs are ubiquitous in many areas: mathematical optimization, control theory, statistics, etc. We study the question whether inclusion holds between two spectrahedra. Most of our results concern the case where the included spectrahedron is a hypercube, an NP-hard problem introduced and studied by Ben-Tal and Nemirovskii, who identified a tractable relaxation of the original problem. This relaxation is obtained by considering the inclusion problem for the corresponding ``matricial'' spectrahedra. To estimate the error inherent in the relaxation we employ probabilistic methods and an old result of Rev. Simmons on flipping biased coins to obtain an elegant scalar optimization formula. This is based on joint work with Bill Helton, Scott McCullough and Markus Schweighofer.

Host: Jiawang Nie

### January 17, 2018

### 2:00 PM

### AP&M 5829

****************************