Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization

• 成果类型: Article
• 署名作者: de Klerk, Etienne; Laurent, Monique; Sun, Zhao
• 署名单位: Tilburg University; Centrum Wiskunde & Informatica (CWI); Tilburg University; Centrum Wiskunde & Informatica (CWI); Universite de Montreal; Polytechnique Montreal
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1043-1
• 发表日期: 2017
• 页码: 363-392
• 关键词: error analysis; fixed-degree; complexity; minimization; simplex

摘要

We consider the problem of minimizing a continuous function f over a compact set . We analyze a hierarchy of upper bounds proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), obtained by searching for an optimal probability density function h on which is a sum of squares of polynomials, so that the expectation is minimized. We show that the rate of convergence is no worse than , where 2r is the degree bound on the density function. This analysis applies to the case when f is Lipschitz continuous and is a full-dimensional compact set satisfying some boundary condition (which is satisfied, e.g., for convex bodies). The rth upper bound in the hierarchy may be computed using semidefinite programming if f is a polynomial of degree d, and if all moments of order up to of the Lebesgue measure on are known, which holds, for example, if is a simplex, hypercube, or a Euclidean ball.