A semidefinite programming approach to the generalized problem of moments (Q995783): Difference between revisions

Let \(K\) be a subset in the \(n\)-dimensional Euclidean space \(\mathbb{R}^n\), and \(M(K)\) a convex set of measures on \(K\). For a collection of functions \(\{f_j\mid j\in J\}\) integrable on \(K\) w.r.t. any \(\mu\in M(K)\), the Generalized Problem of Moments (GPM) is an (infinite-dimensional) minimization problem \(\min_{\mu\in M(K)} \int_K f_0 \,d\mu\) subject to \(\int_K f_j \,d\mu=b_j\) for \(j\in J\) and fixed \(b=\{b_j\in\mathbb{R}\mid j\in J\}\). Although discretization schemes can be defined to solve GPMs, they become numerically unstable for \(n\) larger than 2 or 3. The purpose of the present text is to show that the situation is much nicer for GPMs with polynomial data, i.e. when all the \(f_j\)'s are polynomials, and \(K\) is a semi-algebraic set. Semidefinite programming-based approximation schemes are shown to have good convergence properties in this case. In the second part of the text the authors present various applications of the technique to a range of problems in optimal control, probability, finance, etc.