Minimizing polynomial functions 论文

摘要

We compare algorithms for global optimization of polynomial functions in many variables.It is demonstrated that existing algebraic methods (Gröbner bases, resultants, homotopy methods) are dramatically outperformed by a relaxation technique, due to N.Z.Shor and the first author, which involves sums of squares and semidefinite programming.This opens up the possibility of using semidefinite programming relaxations arising from the Positivstellensatz for a wide range of computational problems in real algebraic geometry.