Global optimization of rational functions: a semidefinite programming approach |
| |
Authors: | D Jibetean E de Klerk |
| |
Institution: | (1) Dept. Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600, MB, Eindhoven, The Netherlands;(2) Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000, LE, Tilburg, The Netherlands |
| |
Abstract: | We consider the problem of global minimization of rational functions on
(unconstrained case), and on an open, connected, semi-algebraic subset of
, 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 16]. 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]. |
| |
Keywords: | 90C22 90C26 49M20 |
本文献已被 SpringerLink 等数据库收录! |
|