Global minimization of a polynomial function using algebraic methods

Dorina Jibetean (CWI, Amsterdam)

The problem of minimizing a polynomial function in several variables over Rn is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimum and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm can compute its infimum. No assumption is made on the polynomial. The method is based on the Stetter-Möller matrix method from the theory of constructive algebra, which translates problems in polynomial algebra into linear algebra problems. The minimization problem is in fact reduced to a generalized eigenvalue problem.

back to TU/e Combinatorial Theory Seminar announcements