Unconstrained polynomial integer minimisation Event as iCalendar

(Engineering Science, Research seminar)

11 March 2015

3 - 4pm

Venue: Room 439.201

Location: Level 2, UniServices House, 70 Symonds Street

Host: Dr Richard Clarke

Contact email: rj.clarke@auckland.ac.nz

 

A Department of Engineering Science seminar by Soenke Behrends of the University of Goettingen, Germany.

 

Abstract:

Suppose you are given a polynomial in several variables, how do you find its minimum value over the integers? By a famous result from complexity theory, this problem cannot be solved in full generality. We thus consider polynomials with special properties to make the problem solvable. Such a tractable case is present if the leading form of the polynomial - given by its highest order terms - attains positive values only (except at 0). Once we know this condition holds, we can compute the radius of a ball that must contain all optimal integer solutions. We could now simply enumerate all solutions and compare their function values to find the optimal ones. However, this soon gets prohibitive for more than a few variables or a large radius. A technique known in the literature as branch and bound in conjunction with tight lower bounds can help to speed up the solution process. To this end, we present a new class of lower bounds and some results on random instances. In this talk I will also address the computational techniques involved as well as the corresponding software implementations. I intend a running example that illustrates the concepts.

This is joint work with Ruth Huebner and Anita Schoebel.

 

About the speaker:

Soenke Behrends is a member of the Optimization Research Group of Professor Anita Schoebel at the Institute for Numerical and Applied Mathematics, Goettingen, where he currently works on his PhD. He is interested in nonlinear integer programming and methods of nonlinear continuous optimisation, especially techniques from real algebraic geometry.