3:00pm - 5:00pmAlgebraic methods for convex sets
Chair(s): Rainer Sinn (Freie Universität Berlin, Germany), Greg Blekherman (Georgia Institute of Technology), Daniel Plaumann (Technische Universität Dortmund), Yong Sheng Soh (Institute of High Performance Computing, Singapore), Dogyoon Song (Massachusetts Institute of Technology)
Convex relaxations are extensively used to solve intractable optimization instances in a wide range of applications. For example, convex relaxations are prominently utilized to find solutions of combinatorial problems that are computationally hard. In addition, convexity-based regularization functions are employed in (potentially ill-posed) inverse problems, e.g., regression, to impose certain desirable structure on the solution.
In this mini-symposium, we discuss the use of convex relaxations and the study of convex sets from an algebraic perspective. In particular, the goal of this minisymposium is to bring together experts from algebraic geometry (real and classical), commutative algebra, optimization, statistics, functional analysis and control theory, as well as discrete geometry to discuss recent connections and discoveries at the interfaces of these fields.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
The slack variety of a polytope
Antonio Macchia
Freie Universität Berlin
The slack variety of a polytope is an algebraic model for the realization space of a combinatorial class of a polytope. We establish a correspondence between realizations of a given polytope and points in the positive part of a variety of matrices of constrained rank. This allows us to apply the tools of computational algebra to a number of problems in polytope theory, such as rational realizability, projectively uniqueness, non-prescribability of faces and realizability of combinatorial polytopes. We then discuss the relationship between slack varieties, Grassmannians and Gale transforms.
Cones of Locally Non-Negative Polynomials
Christoph Schulze
Universität Konstanz, Germany
We study the convex structure of the set of polynomials in n variables which are non-negative in some neighbourhood of the origin (which may depend on the polynomial). This is motivated by the fact that the (algebraic relative interiors of the) faces of this cone give appropriate equivalence classes for a classification of the local behaviour of polynomials with respect to positivity. We use methods of singularity theory to investigate the facial structure of this cone (especially for n=2) leading to a coarsified study of "positive" real singularities with similarities to the theory of complex plane curve singularities (if n=2). The derived classification of faces of low codimension presents "the most frequent types of local behaviours of non-negative polynomials". Connections to cones of polynomials non-negative on some semi-algebraic set (in the truncated/projective setting) are made, giving information about faces of low codimension of these cones. We also generalize implications of Scheiderer's local-global principle concerning the Schmüdgen setting.
Sums of squares and quadratic persistence
Gregory G. Smith
Queen's University
How does one effectively recognize sums of squares? We will focus on new bounds on the number of terms in a sum-of-squares representation for a quadratic form on a real projective subvariety. This talk is based on joint work with G. Blekherman, R. Sinn, and M. Velasco.
Semialgebraic Vision
Rekha Thomas
University of Washington, Seattle
In this talk I will discuss examples of problems in computer vision that are inherently semialgebraic but have not been studied from that angle thus far. This leads to interesting gaps between algebraic results and their semialgebraic versions.
