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.
Click here to download the programme's final scientific report
Title | Year | Programme | |
---|---|---|---|
Optimization approaches to quadrature: new characterizations of Gaussian quadrature on the line and quadrature with few nodes on plane algebraic curves, on the plane and in higher dimensionsAuthors: Markus Schweighofer, Cordian Riener |
2013 | POP | 2 March 2017 |
Tractable approximations of sets defined with quantifiersAuthors: Jean Bernard Lasserre |
2013 | POP | 21 October 2016 |
On robustness criteria and robust topology optimization with uncertain loadsAuthors: Michal Kocvara |
2013 | POP | 21 October 2016 |
Copositivity for second-order optimality conditions in general smooth optimization problemsAuthors: Immanuel Bomze |
2013 | POP | 21 October 2016 |
Weak orientability of matroids and polynomial equationsAuthors: Jesus De Loera, Jon Lee, S Margulies, J Miller |
2013 | POP | 21 October 2016 |
PENLAB: A MATLAB solver for nonlinear semidefinite optimizationAuthors: J Fiala, Michal Kocvara, M Stingl |
2013 | POP | 21 October 2016 |
Narrowing the difficulty gap for the Celis-Dennis-Tapia problemAuthors: Immanuel Bomze, ML Overton |
2013 | POP | 21 October 2016 |
Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPsAuthors: Immanuel Bomze |
2013 | POP | 21 October 2016 |
On global optimization with indefinite quadraticsAuthors: Marcia Fampa, Jon Lee, W Melo |
2013 | POP | 21 October 2016 |
Approximate cone factorizations and lifts of polytopesAuthors: J Gouveia, Pablo A Parrilo, Rekha Thomas |
2013 | POP | 21 October 2016 |
Cutting planes for RLT relaxations of mixed 0-1 polynomial programsAuthors: F Djeumou Fomeni, Konstantinos Kaparis, Adam Letchford |
2013 | POP | 21 October 2016 |
From seven to eleven: completely positive matrices with high CP-rankAuthors: Immanuel Bomze, W Schachinger, R Ullrich |
2013 | POP | 21 October 2016 |
Copositivity-based approximations for mixed-integra fractional quadratic optimizationAuthors: PA Amaral, Immanuel Bomze |
2013 | POP | 21 October 2016 |
New lower bounds and asymptotics for the cp-rankAuthors: Immanuel Bomze, W Schachinger, R Ullrich |
2013 | POP | 21 October 2016 |
Augmentation algorithms for linear and integer linear programmingAuthors: Jesus De Loera, R Hemmecke, Jon Lee |
2013 | POP | 21 October 2016 |
The structure of completely positive matrices according to their CP-rank and CP-plus-rankAuthors: Immanuel Bomze, Peter Dickinson, G Still |
2013 | POP | 21 October 2016 |
15 July 2013 to 19 July 2013
Monday 22nd July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Immanuel Bomze Technische Universität Wien |
Room 2 |
Tuesday 23rd July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Claus Scheiderer Universität Konstanz |
Room 2 | |
Wednesday 24th July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Jiawang Nie University of California, San Diego |
Room 2 | |
17:00 to 20:00 | No Room Required |
Thursday 25th July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Mihai Putinar University of California, Santa Barbara |
Room 2 | |
15:00 to 16:00 |
Dmitrii Pasechnik Nanyang Technological University |
Room 2 |
Friday 26th July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Rekha Thomas University of Washington |
Room 2 |
Monday 29th July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Renata Sotirov Universiteit van Tilburg |
Room 2 | |
Tuesday 30th July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Eden Chlamtac Ben-Gurion University |
Room 2 | |
15:00 to 16:00 |
David Steurer Cornell University |
Room 2 | |
Wednesday 31st July 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Peter Dickinson Technische Universität Wien |
Room 2 |
Thursday 1st August 2013 | |||
---|---|---|---|
11:00 to 12:00 |
Franz Rendl Alpen-Adria-Universität Klagenfurt |
Room 2 | |
15:00 to 16:00 | Room 2 | |
Friday 2nd August 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Angelika Wiegele Alpen-Adria-Universität Klagenfurt |
Room 2 | |
15:00 to 16:00 |
David Steurer Cornell University |
Room 2 |
Monday 5th August 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Jon Lee University of Michigan |
Room 1 | |
Tuesday 6th August 2013 | |||
---|---|---|---|
14:00 to 15:00 |
Florian Jarre Heinrich-Heine-Universität Düsseldorf |
Room 1 | |
Wednesday 7th August 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Mohab Safey El Din Université Pierre et Marie Curie Paris |
Room 1 | |
Thursday 8th August 2013 | |||
---|---|---|---|
12:30 to 13:45 | No Room Required | ||
14:00 to 14:15 | Room 1 | ||
14:15 to 14:45 |
Miguel Anjos École Polytechnique de Montréal |
Room 1 | |
14:45 to 15:15 | Room 1 | |
|
15:15 to 15:45 |
Designing and tuning RF filters to a prescribed specification |
Room 1 | |
15:45 to 16:15 |
Jakub Marecek IBM Research |
Room 1 | |
16:15 to 16:45 | No Room Required | ||
16:45 to 17:15 | Room 1 | |
|
17:15 to 17:45 | Room 1 | |
|
17:45 to 18:30 | Room 1 | |
|
18:30 to 19:30 | No Room Required | ||
19:45 to 22:00 | No Room Required |
Friday 9th August 2013 | |||
---|---|---|---|
10:00 to 11:00 |
Houduo Qi University of Southampton |
Room 1 | |
Subscribe for the latest updates on events and news
Isaac Newton Institute for Mathematical Sciences, 20 Clarkson Road, Cambridge CB3 0EH United Kingdom
Tel: +44 1223 335999 Email: reception@newton.ac.uk
© 2023 Isaac Newton Institute for Mathematical Sciences. All Rights Reserved. Privacy Policy
INI is a creative collaborative space which is occupied by up to fifty-five mathematical scientists at any one time (and many more when there is a workshop). Some of them may not have met before and others may not realise the relevance of other research to their own work.
INI is especially important as a forum where early-career researchers meet senior colleagues and form networks that last a lifetime.
Here you can learn about all activities past, present and future, watch live seminars and submit your own proposals for research programmes.
Within this section of the website you should find all the information required to arrange and plan your visit to the Institute. If you have any further questions, or are unable to find the information you require, please get in touch with the relevant staff member or our Reception team via our contact pages.
INI and its programme participants produce a range of publications to communicate information about activities and events, publish research outcomes, and document case studies which are written for a non-technical audience. You will find access to them all in this section.
The Isaac Newton Institute aims to maximise the benefit of its scientific programmes to the UK mathematical science community in a variety of ways.
Whether spreading research opportunities through its network of correspondents, offering summer schools to early career researchers, or hosting public-facing lectures through events such as the Cambridge Festival, there is always a great deal of activity to catch up on.
Find out about all of these endeavours in this section of the site.
There are various ways to keep up-to-date with current events and happenings at the Isaac Newton Institute. As detailed via the menu links within this section, our output covers social media streams, news articles, a regular podcast series, an online newsletter, and more detailed documents produced throughout the year.
“A world famous place for research in the mathematical sciences with a reputation for efficient management and a warm welcome for visitors”
The Isaac Newton Institute is a national and international visitor research institute. It runs research programmes on selected themes in mathematics and the mathematical sciences with applications over a wide range of science and technology. It attracts leading mathematical scientists from the UK and overseas to interact in research over an extended period.
INI has a vital national role, building on many strengths that already exist in UK universities, aiming to generate a new vitality through stimulating and nurturing research throughout the country.During each scientific programme new collaborations are made and ideas and expertise are exchanged and catalysed through lectures, seminars and informal interaction, which the INI building has been designed specifically to encourage.
For INI’s knowledge exchange arm, please see the Newton Gateway to Mathematics.
The Institute depends upon donations, as well as research grants, to support the world class research undertaken by participants in its programmes.
Fundraising activities are supported by a Development Board comprising leading figures in academia, industry and commerce.
Visit this section to learn more about how you could play a part in supporting INI’s groundbreaking research.
In this section you can find contact information, staff lists, maps and details of how to find INI’s main building in Cambridge.
Our administrative staff can help you with any queries regarding a prospective or planned visit. If you would like to discuss a proposed a research programme or other event, our senior management team will be happy to help.