Abstract:
We consider the problem of global minimization of rational functions on R^n (unconstrained case), or on a connected semi-algebraic subset of R^n. We show that in the univariate case (n=1), these problems have exact reformulations as semidefinite programming problems (SDP), by using reformulations introduced by Jibetean (2001). This extends the analogous results by Nesterov (2000) 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 (2002).
For the NP-hard multivariate case, we discuss semidefinite programming-based heuristics for obtaining lower bounds on the infimum, by using results by Lasserre (2001).
References
E. de Klerk, D.V. Pasechnik (2002). Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms. European J. of Operational Research, to appear.
D. Jibetean. Global optimization of rational multivariate functions. Technical Report PNA-R0120, CWI, Amsterdam, 2001.
J. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J.Optim., 11(3):796--817, 2001.
Y. Nesterov. Squared functional systems and optimization problems. In H. Frenk, K. Roos, and T. Terlaky, editors, High Performance Optimization, pages 405--439, Dordrecht, 2000. Kluwer Academic Publishers.