Global optimization of rational functions: a semidefinite programming approach

• 成果类型: Article
• 署名作者: Jibetean, D; de Klerk, E
• 署名单位: Eindhoven University of Technology; Tilburg University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0589-0
• 发表日期: 2006
• 页码: 93-109
• 关键词: Polynomials; relaxations

摘要

We consider the problem of global minimization of rational functions on R-n (unconstrained case), and on an open, connected, semi-algebraic subset of R-n, or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [6]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].