Bilinear optimality constraints for the cone of positive polynomials

• 成果类型: Article; Proceedings Paper
• 署名作者: Rudolf, Gabor; Noyan, Nilay; Papp, David; Alizadeh, Farid
• 署名单位: Virginia Commonwealth University; Sabanci University; Northwestern University; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0458-y
• 发表日期: 2011
• 页码: 5-31
• 关键词: interior-point algorithms

摘要

For a proper cone K subset of R-n and its dual cone K* the complementary slackness condition < x, s > = 0 defines an n-dimensional manifold C(K) in the space R-2n. When K is a symmetric cone, points in C(K) must satisfy at least n linearly independent bilinear identities. This fact proves to be useful when optimizing over such cones, therefore it is natural to look for similar bilinear relations for non-symmetric cones. In this paper we define the bilinearity rank of a cone, which is the number of linearly independent bilinear identities valid for points in C(K). We examine several well-known cones, in particular the cone of positive polynomials P2n+1 and its dual, and show that there are exactly four linearly independent bilinear identities which hold for all (x, s) is an element of C(P2n+1), regardless of the dimension of the cones. For nonnegative polynomials over an interval or half-line there are only two linearly independent bilinear identities. These results are extended to trigonometric and exponential polynomials. We prove similar results for Muntz polynomials.