Minimizing polynomial functions
Minimizing polynomial functions
We compare algorithms for global optimization of polynomial functions in many variables. It is demonstrated that existing algebraic methods (Gr\obner 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 …