TAMING - Taming nonconvexity ?
European Research Council Advanced Grant

Project summary

In many important areas and applications of science one has to solve nonconvex optimization problems and ideally and ultimately one would like to find the global minimum. However in most cases, one is faced with NP-hard problems and therefore in practice one has been often satisfied with only a local optimum obtained with some ad-hoc (local) optimization algorithm.

TAMING intends to provide a systematic methodology for solving hard nonconvex polynomial optimization problems in all areas of science. Indeed the last decade has witnessed the emergence of polynomial optimization as a new field in which powerful positivity certificates from real algebraic geometry have permitted to develop an original and systematic approach to solve (at global optimality) optimization problems with polynomial (and even semi-algebraic) data. The backbone of this powerful methodology is the "moment-SOS" approach also known as "Lasserre hierarchy" which has attracted a lot of attention in many areas (e.g., optimization, applied mathematics, quantum computing, engineering, theoretical computer science) with important potential applications. It is now a basic tool for analyzing hardness of approximation in combinatorial optimization and the best candidate algorithm to prove/disprove the famous unique games conjecture. Recently it has become a promising new method for solving the important optimal power flow problem in the strategic domain of energy networks (as the only method that could solve to optimality certain types of such problems).

However in its present form this promising methodology inherits a high computational cost and a (too) severe problem size limitation which precludes from its application many important real life problems of significant size. Proving that indeed this methodology can fulfill its promises and solve important practical problems in various areas poses major theoretical and practical challenges.

Project keywords

ERC keywords: algorithms, distributed, parallel and network algorithms, algorithmic game theory, scientific computing, simulation and modeling tools, control theory and optimization, discrete mathematics and combinatorics

Free keywords: global optimization, nonlinear, discrete and combinatorial optimization, hierarchies of convex relaxations, sums-of-squares hierarchies, control, optimal control, computational geometry

Period

2015 - 2019

Participants

  • Jean-Bernard Lasserre, CNRS researcher, project leader
  • Didier Henrion, CNRS researcher
  • Tillmann Weisser, PhD. Student at LAAS-CNRS (September 2015-- August 2018).
  • Cédric Josz, Post-Doc at LAAS-CNRS (September 2016 -- August 2017).
  • Jeremy Rouot , Post-Doc at LAAS-CNRS (December 2016 -- November 2017).
  • Swann Marx, Post-Doc at LAAS-CNRS (September 2017 -- August 2018).

    Visitors sponsored by the ERC-TAMING:

  • M. Laurent , CWI, Amsterdam, Netherlands, June 20-- 21, 2016
  • E. de Klerk , Tilburg University, Netherlands, June 20-- 21, 2016
  • M. Sznaier, Northeastern University, Boston, USA, June 20-- 24, 2016
  • A.A. Ahmadi, Princeton University, Princeton, USA, June 20-- 24, 2016
  • G. Hall , Princeton University, Princeton, USA, June 20-- 24, 2016
  • Tien Son Pham , Dalat University, Dalta, Vietnam, April-May 2017

    PhD and post-doctoral fellowships

    Several PhD and post-doctoral fellowships are available for this project, see this description. Please contact Jean-Bernard Lasserre if you are interested.

    Related events

    Scientific Publications