Linear optimization with cones of moments and nonnegative polynomials

• 成果类型: Article
• 署名作者: Nie, Jiawang
• 署名单位: University of California System; University of California San Diego
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0797-6
• 发表日期: 2015
• 页码: 247-274
• 关键词: positive polynomials; convex hulls; semidefinite

摘要

Let be a finite subset of and be the space spanned by monomials with . Let be a compact semialgebraic set of such that a polynomial in is positive on . Denote by the cone of polynomials in that are nonnegative on . The dual cone of is , the set of all truncated moment sequences in that admit representing measures supported in . First, we study geometric properties of the cones and (like interiors, closeness, duality, memberships), and construct a convergent hierarchy of semidefinite relaxations for each of them. Second, we propose a semidefinite algorithm for solving linear optimization problems with the cones and , and prove its asymptotic and finite convergence. Third, we show how to check whether and intersect affine subspaces; if they do, we show how to get a point in the intersections; if they do not, we prove certificates for the empty intersection.