Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere

preprint2021arXivOpen access

Abstract

We consider the generalized moment problem (GMP) over the simplex and the sphere. This is a rich setting and it contains NP-hard problems as special cases, like constructing optimal cubature schemes and rational optimization. Using the Reformulation-Linearization Technique (RLT) and Lasserre-type hierarchies, relaxations of the problem are introduced and analyzed. For our analysis we assume throughout the existence of a dual optimal solution as well as strong duality. For the GMP over the simplex we prove a convergence rate of O(1/r)O(1/r) for a linear programming, RLT-type hierarchy, where rr is the level of the hierarchy, using a quantitative version of Pólya's Positivstellensatz. As an extension of a recent result by Fang and Fawzi [Math. Program., 2020, https://doi.org/10.1007/s10107-020-01537-7] we prove the Lasserre hierarchy of the GMP [Math. Program., Vol. 112, 65-92, 2008] over the sphere has a convergence rate of O(1/r2)O(1/r^2). Moreover, we show the introduced linear RLT-relaxation is a generalization of a hierarchy for minimizing forms of degree dd over the simplex, introduced by de Klerk, Laurent and Parrilo [J. Theoretical Computer Science, Vol. 361, 210-225, 2006].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.