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 de Finetti’s theorem from probability as well as the recently identified phenomenon of representation stability from algebraic topology, we present a systematic approach to derive finite-sized semidefinite programming relaxations 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)
Back to Workshop III: Statistical and Numerical Methods for Non-commutative Optimal Transport
Copyright. All Rights Reserved.