We consider the problem of global minimization of rational functions on $mathbb{R}^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $mathbb{R}^n$, or the (partial) closure of such a set (const rained 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].

, ,
Modelling, Analysis and Simulation [MAS]

Jibetean, D., & de Klerk, E. (2003). Global optimization of rational functions: a semidefinite programming approach. Modelling, Analysis and Simulation [MAS]. CWI.