An exact Jacobian SDP relaxation for polynomial optimization

• 成果类型: Article
• 署名作者: Nie, Jiawang
• 署名单位: University of California System; University of California San Diego
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0489-4
• 发表日期: 2013
• 页码: 225-255
• 关键词: positive polynomials; global optimization; REPRESENTATIONS; complexity; bounds

摘要

Given polynomials f(x), g (i) (x), h(j)(x), we study how to minimize f(x) on the set S = {x is an element of R-n : h(1)(x) = ... = h(m1)(x) = 0, g(1)(x) >= 0, ... , g(m2)(x) >= 0}. Let f(min) be the minimum of f on S. Suppose S is nonsingular and f(min) is achievable on S, which are true generically. This paper proposes a new type semidefinite programming (SDP) relaxation which is the first one for solving this problem exactly. First, we construct new polynomials phi(1), ... , phi(r), by using the Jacobian of f, h(i), g(j), such that the above problem is equivalent to min(x is an element of Rn) f(x) s.t. h(i)(x) = 0, phi(j)(x) = 0, 1 <= i <= m(1), 1 <= j <= r, g(1)(x)(nu 1) ... g(m2)(x)(nu m2) >= 0, for all nu is an element of {0, 1}(m2). Second, we prove that for all N big enough, the standard N-th order Lasserre's SDP relaxation is exact for solving this equivalent problem, that is, its optimal value is equal to f(min). Some variations and examples are also shown.