Polynomial optimisation

Programme theme

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

Preprints

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 dimensions Authors: Markus Schweighofer, Cordian Riener Download PDF	2013	POP	2 March 2017
Tractable approximations of sets defined with quantifiers Authors: Jean Bernard Lasserre Download PDF	2013	POP	21 October 2016
On robustness criteria and robust topology optimization with uncertain loads Authors: Michal Kocvara Download PDF	2013	POP	21 October 2016
Copositivity for second-order optimality conditions in general smooth optimization problems Authors: Immanuel Bomze Download PDF	2013	POP	21 October 2016
Weak orientability of matroids and polynomial equations Authors: Jesus De Loera, Jon Lee, S Margulies, J Miller Download PDF	2013	POP	21 October 2016
PENLAB: A MATLAB solver for nonlinear semidefinite optimization Authors: J Fiala, Michal Kocvara, M Stingl Download PDF	2013	POP	21 October 2016
Narrowing the difficulty gap for the Celis-Dennis-Tapia problem Authors: Immanuel Bomze, ML Overton Download PDF	2013	POP	21 October 2016
Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs Authors: Immanuel Bomze Download PDF	2013	POP	21 October 2016
On global optimization with indefinite quadratics Authors: Marcia Fampa, Jon Lee, W Melo Download PDF	2013	POP	21 October 2016
Approximate cone factorizations and lifts of polytopes Authors: J Gouveia, Pablo A Parrilo, Rekha Thomas Download PDF	2013	POP	21 October 2016
Cutting planes for RLT relaxations of mixed 0-1 polynomial programs Authors: F Djeumou Fomeni, Konstantinos Kaparis, Adam Letchford Download PDF	2013	POP	21 October 2016
From seven to eleven: completely positive matrices with high CP-rank Authors: Immanuel Bomze, W Schachinger, R Ullrich Download PDF	2013	POP	21 October 2016
Copositivity-based approximations for mixed-integra fractional quadratic optimization Authors: PA Amaral, Immanuel Bomze Download PDF	2013	POP	21 October 2016
New lower bounds and asymptotics for the cp-rank Authors: Immanuel Bomze, W Schachinger, R Ullrich Download PDF	2013	POP	21 October 2016
Augmentation algorithms for linear and integer linear programming Authors: Jesus De Loera, R Hemmecke, Jon Lee Download PDF	2013	POP	21 October 2016
The structure of completely positive matrices according to their CP-rank and CP-plus-rank Authors: Immanuel Bomze, Peter Dickinson, G Still Download PDF	2013	POP	21 October 2016

Workshops

POPW01

Polynomial optimisation: workshop and summer school

15 July 2013 to 19 July 2013

Seminars

Monday 22nd July 2013
10:00 to 11:00	Immanuel Bomze Technische Universität Wien A nasty cone with nice properties - recent advances in copositive optimisation.	Room 2

Tuesday 23rd July 2013
10:00 to 11:00	Claus Scheiderer Universität Konstanz Recent progress on questions of Nemirovsky and Sturmfels	Room 2

Wednesday 24th July 2013
10:00 to 11:00	Jiawang Nie University of California, San Diego Local and global optimality conditions for multivariate polynomial optimization.	Room 2
17:00 to 20:00	Social drinks reception	No Room Required

Thursday 25th July 2013
10:00 to 11:00	Mihai Putinar University of California, Santa Barbara Hermitian complexity of real ideals	Room 2
15:00 to 16:00	Dmitrii Pasechnik Nanyang Technological University Moments of measures on compact polyhedra, weighted triangulations, integral transforms, and multisymmetric polynomials.	Room 2

Friday 26th July 2013
10:00 to 11:00	Rekha Thomas University of Washington From approximate cone factorizations to approximate lifts of polytopes	Room 2

Monday 29th July 2013
10:00 to 11:00	Renata Sotirov Universiteit van Tilburg The graph partitioning problem: quick and dirty vs strong and long	Room 2

Tuesday 30th July 2013
10:00 to 11:00	Eden Chlamtac Ben-Gurion University Lift-and-project methods and relaxations for Knapsack	Room 2
15:00 to 16:00	David Steurer Cornell University The unique games conjecture and polynomial optimization	Room 2

Wednesday 31st July 2013
10:00 to 11:00	Peter Dickinson Technische Universität Wien On the set-copositive cone.	Room 2

Thursday 1st August 2013
11:00 to 12:00	Franz Rendl Alpen-Adria-Universität Klagenfurt Eigenvalue optimization in connection with vertex separators (and bandwidth)	Room 2
15:00 to 16:00	Moments and SDP for multiobjective linear programming	Room 2

Friday 2nd August 2013
10:00 to 11:00	Angelika Wiegele Alpen-Adria-Universität Klagenfurt Semidefinite relaxations for various non-convex quadratic optimization problems.	Room 2
15:00 to 16:00	David Steurer Cornell University Multiplicative Update Methods and Semidefinite Programming	Room 2

Monday 5th August 2013
10:00 to 11:00	Jon Lee University of Michigan Engineering Hilbert's Nullstellensatz for Combinatorial Problems	Room 1

Tuesday 6th August 2013
14:00 to 15:00	Florian Jarre Heinrich-Heine-Universität Düsseldorf Numerical issues in semidefinite and convex conic optimization	Room 1

Wednesday 7th August 2013
10:00 to 11:00	Mohab Safey El Din Université Pierre et Marie Curie Paris Polynomial Optimization and Symbolic Computation: From Theory to Practice and Vice Versa	Room 1

Thursday 8th August 2013
12:30 to 13:45	Buffet Lunch	No Room Required
14:00 to 14:15	Welcome from John Toland and Adam Letchford	Room 1
14:15 to 14:45	Miguel Anjos École Polytechnique de Montréal Applications of linear and nonlinear optimisation in the electricity sector	Room 1
14:45 to 15:15	Current space optimisation challenges	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 Polynomial optimisation in power systems at IBM Research	Room 1
16:15 to 16:45	Coffee Break	No Room Required
16:45 to 17:15	Semidefinite programming at NAG	Room 1
17:15 to 17:45	Solving conic optimization problems with MOSEK	Room 1
17:45 to 18:30	Panel Discussion	Room 1
18:30 to 19:30	Wine Reception	No Room Required
19:45 to 22:00	Dinner at Gonville and Caius College for invited guests	No Room Required

Friday 9th August 2013
10:00 to 11:00	Houduo Qi University of Southampton Spherical Euclidean Distance Embedding and the Unit-Distance Respresentation of a Graph on a Hypersphere	Room 1

Organisers

Jörg Fliege University of Southampton
Jean Bernard Lasserre Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS)
Adam Letchford Lancaster University
Markus Schweighofer Universität Konstanz

Speakers

Miguel Anjos École Polytechnique de Montréal
Immanuel Bomze Technische Universität Wien
Eden Chlamtac Ben-Gurion University
Peter Dickinson Technische Universität Wien
Florian Jarre Heinrich-Heine-Universität Düsseldorf
Jon Lee University of Michigan
Jakub Marecek IBM Research
Jiawang Nie University of California, San Diego
Dmitrii Pasechnik Nanyang Technological University
Mihai Putinar University of California, Santa Barbara
Houduo Qi University of Southampton
Franz Rendl Alpen-Adria-Universität Klagenfurt
Mohab Safey El Din Université Pierre et Marie Curie Paris
Claus Scheiderer Universität Konstanz
Renata Sotirov Universiteit van Tilburg
David Steurer Cornell University
Rekha Thomas University of Washington
Angelika Wiegele Alpen-Adria-Universität Klagenfurt

Show All

Programme theme

Preprints

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 dimensions

Tractable approximations of sets defined with quantifiers

On robustness criteria and robust topology optimization with uncertain loads

Copositivity for second-order optimality conditions in general smooth optimization problems

Weak orientability of matroids and polynomial equations

PENLAB: A MATLAB solver for nonlinear semidefinite optimization

Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

On global optimization with indefinite quadratics

Approximate cone factorizations and lifts of polytopes

Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

From seven to eleven: completely positive matrices with high CP-rank

Copositivity-based approximations for mixed-integra fractional quadratic optimization

New lower bounds and asymptotics for the cp-rank

Augmentation algorithms for linear and integer linear programming

The structure of completely positive matrices according to their CP-rank and CP-plus-rank

Workshops

Polynomial optimisation: workshop and summer school

Seminars

Organisers

Speakers

Supported By

Register for updates