Venkat Chandrasekaran: Any-dimensional polynomial optimization

Abstract.

Optimization problems commonly arise as sequences indexed by dimension. For example, in extremal combinatorics the sequences of problems may be indexed by graph size, while in information theory the sequences are indexed by the number of channel uses. In such “any-dimensional” problems, it is of interest to obtain bounds on the limiting optimal value. We study any-dimensional optimization problems in which the constraints and objective are specified by polynomials. By leveraging the recently identified phenomenon of representation stability from algebraic topology along with a generalization of de Finetti’s theorem from probability, we present a systematic approach to derive finite-sized programs that bound the limiting optimal value of any-dimensional polynomial optimization problems. We illustrate our framework with examples from several applications. (Joint work with Eitan Levin)