Solving moment problems by dimensional extension

We consider a generic basic semi-algebraic subset $\mathcal{S}$ of the space of generalized functions, that is a set given by (not necessarily countably many) polynomial constraints. We derive necessary and sufficient conditions for an infinite sequence of generalized functions to be realizable on $\mathcal{S}$, namely to be the moment sequence of a finite measure concentrated on $\mathcal{S}$. Our approach combines the classical results about the moment problem on nuclear sp...

Putinar's Positivstellensatz is a central theorem in real algebraic geometry. It states the following: If you have a set $S= \{ x \in R^n \ | \ g_1 (x) \geq 0, ... , g_m(x) \geq 0\}$ described by some real polynomials $g_i$, then every real polynomial $f$ that is positive on $S$ can be written as a sum of squares weighted by the $g_i$ and $1$. Consider such an identity $f= \sum_{i=1}^{m} g_i s_i + s_0$. For the applications in polynomial optimization, especially semidefinite ...

A truncated moment sequence (tms) of degree d is a vector indexed by monomials whose degree is at most d. Let K be a semialgebraic set.The truncated K-moment problem (TKMP) is: when does a tms y admit a positive Borel measure supported? This paper proposes a semidefinite programming (SDP) approach for solving TKMP. When K is compact, we get the following results: whether a tms y of degree d admits a K-measure or notcan be checked via solving a sequence of SDP problems; when y...

Recent breakthroughs have been made in the use of semidefinite programming and its application to real polynomial solving. For example, the real radical of a zero dimensional ideal, can be determined by such approaches as shown by Lasserre and collaborators. Some progress has been made on the determination of the real radical in positive dimension by Ma, Wang and Zhi. Such work involves the determination of maximal rank semidefinite moment matrices. Existing methods are compu...

In a broad sense, positivstellens\"atze are results about representations of polynomials which are strictly positive on a given set. We give constructive and, to a large extent, elementary proofs of some known positivstellens\"atze for compact semialgebraic subsets of $\mathbb{R}^d$. The presented proofs extend and simplify arguments of Berr, W\"ormann (2001) and Schweighofer (2002, 2005).

We describe algebraic certificates of positivity for functions belonging to a finitely generated algebra of Borel measurable functions, with particular emphasis to algebras generated by semi-algebraic functions. In which case the standard global optimization problem with constraints given by elements of the same algebra is reduced via a natural change of variables to the better understood case of polynomial optimization. A collection of simple examples and numerical experimen...

We investigate the problem of representing moment sequences by measures in the context ofPolynomial Optimization Problems. This consists in finding the infimum of a real polynomial ona real semialgebraic set defined by polynomial inequalities. We analyze the exactness of MomentMatrix (MoM) relaxations, dual to the Sum of Squares (SoS) relaxations, which are hierarchiesof convex cones introduced by Lasserre to approximate measures and positive polynomials. Weinvestigate in par...

We consider the problem of finding a (non-negative) measure $\mu$ on $\mathfrak{B}(\mathbb{C}^n)$ such that $\int_{\mathbb{C}^n} \mathbf{z}^{\mathbf{k}} d\mu(\mathbf{z}) = s_{\mathbf{k}}$, $\forall \mathbf{k}\in\mathcal{K}$. Here $\mathcal{K}$ is an arbitrary finite subset of $\mathbb{Z}^n_+$, which contains $(0,...,0)$, and $s_{\mathbf{k}}$ are prescribed complex numbers (we use the usual notations for multi-indices). There are two possible interpretations of this problem. A...

Consider a semi-algebraic set A in R^d constructed from the sets which are determined by inequalities p_i(x)>0, p_i(x)\ge 0, or p_i(x)=0 for a given list of polynomials p_1,...,p_m. We prove several statements that fit into the following template. Assume that in a neighborhood of a boundary point the semi-algebraic set A can be described by an irreducible polynomial f. Then f is a factor of a certain multiplicity of some of the polynomials p_1,...,p_m. Special cases when A is...

This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be...