Journal
MATHEMATICAL PROGRAMMING
Volume 106, Issue 1, Pages 93-109Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-005-0589-0
Keywords
-
Ask authors/readers for more resources
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].
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available