Isaac Newton Institute for Mathematical Sciences

Polynomial Optimisation

15 July - 9 August 2013

Organisers: Joerg Fliege (Southampton), Jean-Bernard Lasserre (Toulouse), Adam Letchford (Lancaster) and Markus Schweighofer (Konstanz)

Scientific Advisors: Monique Laurent (CWI, Amsterdam & Tilburg) and Kurt Anstreicher (Iowa)

Programme Theme

POP programme identifier - the six-hump camel back polynomial: f(x,y)= x^2(4-2.1x^2+x^4/3)+xy+y^2(-4+4y^2)Optimisation problems involving polynomials arise in a wide variety of contexts, including operational research, statistics, probability, finance, computer science, structural engineering, statistical physics, combinatorial chemistry, computational biology and algorithmic graph theory. They are however extremely challenging to solve, both in theory and practice. Existing algorithms and software are capable of solving only very small instances to proven optimality, unless they have some amenable structure, such as sparsity or convexity.

A fascinating feature of polynomial optimisation is that it can be approached from several different directions. In addition to traditional techniques drawn from operational research, computer science and numerical analysis, new techniques have recently emerged based on concepts taken from algebraic geometry, commutative algebra and moment theory. In this regard, polynomial optimisation provides a valuable opportunity for researchers from previously unrelated disciplines to work together.

The plan for this four-week programme is as follows. During the first week (15th-19th July 2013), there will be a "summer school" and "workshop", which are open not only to official programme participants, but also to other interested academics, PhD students and post-doctoral researchers.

The following three weeks will be open only to invited persons. Each of the three weeks will focus on a specific sub-topic:

1. Algebraic Approaches (22nd-26th July 2013). This will concern the development of new theory and algorithms based on techniques from relevant areas of pure mathematics, such as real algebraic geometry, commutative and noncommutative algebra, moment theory and the theory of sums-of-squares representations.

2. Convex Relaxations and Approximations (29th July-2nd August). This will be devoted to the study of convex relaxations (and hierarchies of relaxations) of certain important specially-structured problem classes, along with associated approximation algorithms (and inapproximability results).

3. Algorithms and Software (5th-9th August). This will be devoted to the development of new algorithms and their implementation as software. This may include, for example, algorithms for computing lower and upper bounds, algorithms for generating strong valid inequalities, and algorithms for solving instances to proven optimality.

Please Note: The list of Invited Participants only includes people who plan to attend during the last three weeks of the programme. For a list of participants in the summer school and workshop, please see the event's Participants page.