skip to content

Polynomial Optimisation

Participation in INI programmes is by invitation only. Anyone wishing to apply to participate in the associated workshop(s) should use the relevant workshop application form.

15th July 2013 to 9th August 2013
Jean Bernard Lasserre [Toulouse], Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS)
Adam Letchford [Lancaster], Lancaster University
Markus Schweighofer [Konstanz], Universität Konstanz
Jörg Fliege [Southampton], University of Southampton

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.

Final Scientific Report: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons