Global optimization of rational functions: a semidefinite programming approach

Dorina Jibetean (D.Jibeteancwi.nl)
Etienne De Klerk (E.deKlerkits.tudelft.nl)

Abstract: We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^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. This extends the analogous results by Nesterov 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. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo, and Lasserre.

Keywords: Semidefinite programming, global optimization, rational functions, positive polynomials

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization

Citation: CWI report CWI, Amsterdam, The Netherlands

Download: [Postscript][PDF]

Entry Submitted: 05/13/2003
Entry Accepted: 05/13/2003
Entry Last Modified: 05/13/2003

Modify/Update this entry